ECE 150 Fundamentals of Programming

This class expands on the previous linked list class by including:

• a doubly-linked list, so you can move both forward and backward,
• inner classes, where the Node class is added to the Linked_list class, thus hiding it from those using this class, and
• a validate function that is called each time a change is made to the structure to ensure that any changes leave the linked list in a valid state.

template<typename T> class Linked_list {
  private:
    class Node;

  public:
    Linked_list();   // Constructor
   ~Linked_list();   // Destructor

    bool empty() const;
    std::size_t size() const;
    T front() const;
    T back() const;
    std::string to_string() const;
    std::size_t find( T const &value ) const;
    T operator[]( std::size_t const n ) const;

    void push_front( T const &new_value );
    void push_back( T const &new_value );
    Linked_list &operator+=( Linked_list<T> const &list );

    void pop_front();
    void pop_back();
    void clear();

  private:
    class Node {
      public:
        T value_;
        Node *p_prev_node_;
        Node *p_next_node_;
    };

    Node *p_list_head_; // Pointer to head node
    Node *p_list_tail_; // Pointer to tail node  *NEW*
    std::size_t size_;  // The number of nodes in the linked list

    bool validate_linked_list() const;
};

View this simple linked list at repl.it.

The class declarations and definitions are in the corresponding Linked_list.hpp file.