Linked List Library

Core Linked List Classes

Singly Linked List (forward_list):

• Node structure with data and next pointer
• push_front, pop_front - O(1) operations
• insert_after, erase_after - positional operations
• Forward iterator support only

Doubly Linked List (list):

• Node structure with data, prev, and next pointers
• push_front, push_back, pop_front, pop_back - O(1)
• insert, erase at any position with iterator
• Bidirectional iterator support

template<typename T, typename Allocator = std::allocator<T>>
class LinkedList {
public:
    // Type aliases for STL compatibility
    using value_type = T;
    using allocator_type = Allocator;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = typename std::allocator_traits<Allocator>::pointer;
    using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
    
    // Iterator types
    class iterator;
    class const_iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    
    // Constructors, destructor, assignment
    LinkedList();
    explicit LinkedList(const Allocator& alloc);
    LinkedList(size_type count, const T& value, const Allocator& alloc = Allocator());
    LinkedList(std::initializer_list<T> init, const Allocator& alloc = Allocator());
    LinkedList(const LinkedList& other);
    LinkedList(LinkedList&& other) noexcept;
    ~LinkedList();
    
    LinkedList& operator=(const LinkedList& other);
    LinkedList& operator=(LinkedList&& other) noexcept;
    
    // Element access
    reference front();
    reference back();
    
    // Iterators
    iterator begin() noexcept;
    iterator end() noexcept;
    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;
    
    // Capacity
    bool empty() const noexcept;
    size_type size() const noexcept;
    
    // Modifiers
    void clear() noexcept;
    iterator insert(const_iterator pos, const T& value);
    iterator erase(const_iterator pos);
    void push_front(const T& value);
    void push_back(const T& value);
    void pop_front();
    void pop_back();
    
    // Emplace operations
    template<typename... Args>
    iterator emplace(const_iterator pos, Args&&... args);
    template<typename... Args>
    reference emplace_front(Args&&... args);
    template<typename... Args>
    reference emplace_back(Args&&... args);
    
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        
        template<typename... Args>
        Node(Args&&... args) : data(std::forward<Args>(args)...), prev(nullptr), next(nullptr) {}
    };
    
    Node* head_;
    Node* tail_;
    size_type size_;
    Allocator allocator_;
};

Iterator Implementation

Requirements for STL-compatible iterators:

• Forward iterator for singly linked list (InputIterator, OutputIterator, ForwardIterator)
• Bidirectional iterator for doubly linked list (adds BidirectionalIterator)
• Both const and non-const versions
• Proper iterator_traits specialization
• Support for range-based for loops

// Iterator class (nested in LinkedList)
class iterator {
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    
    iterator() : node_(nullptr) {}
    explicit iterator(Node* node) : node_(node) {}
    
    reference operator*() const { return node_->data; }
    pointer operator->() const { return &(node_->data); }
    
    iterator& operator++() {
        node_ = node_->next;
        return *this;
    }
    
    iterator operator++(int) {
        iterator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    iterator& operator--() {
        node_ = node_->prev;
        return *this;
    }
    
    iterator operator--(int) {
        iterator tmp = *this;
        --(*this);
        return tmp;
    }
    
    bool operator==(const iterator& other) const { return node_ == other.node_; }
    bool operator!=(const iterator& other) const { return node_ != other.node_; }
    
private:
    Node* node_;
    friend class LinkedList;
};

List Operations

Implement the following list-specific operations:

• splice: Transfer elements from another list without copying
• merge: Merge two sorted lists into one
• reverse: Reverse the order of elements in-place
• unique: Remove consecutive duplicate elements
• remove/remove_if: Remove elements matching value/predicate
• sort: Sort elements (merge sort recommended)

// List operations
void splice(const_iterator pos, LinkedList& other);
void splice(const_iterator pos, LinkedList& other, const_iterator it);
void splice(const_iterator pos, LinkedList& other, const_iterator first, const_iterator last);

void merge(LinkedList& other);
template<typename Compare>
void merge(LinkedList& other, Compare comp);

void reverse() noexcept;

void unique();
template<typename BinaryPredicate>
void unique(BinaryPredicate p);

void remove(const T& value);
template<typename UnaryPredicate>
void remove_if(UnaryPredicate p);

void sort();
template<typename Compare>
void sort(Compare comp);

Testing and Benchmarking

Unit Tests (using Google Test or Catch2):

• Test all constructors and assignment operators
• Test all modifiers with various data types
• Test iterator operations and STL algorithm compatibility
• Test exception safety (strong guarantee for modifiers)
• Test memory correctness with valgrind/AddressSanitizer

Performance Benchmarks:

• Benchmark push/pop operations against std::list
• Benchmark traversal with various element counts
• Benchmark splice/merge operations
• Measure memory usage per element