• Some problems with array implementation of a vector
  • inserting somewhere besides the end of the vector requires O(N) items to be moved down one space (in the worst case)
  • resizing operation is expensive
  • requires contiguous allocation
• Some benefits of array implementation of vector
  • O(1) access to an item in the vector given some index or location
  • O(1)

Linked Lists

• Linked Lists are another container class where items are stored in linked structures rather than a contiguously allocated block memory as with a vector
• Standard Library provides std::list<T> and std::forward_list<T>
  • std::list<T> is a doubly linked list meaning you can go forwards and backwards from any node
  • std::forward_list<T> is a singly linked list.

Node Structure

• For a singly linked list:

template <typename T>
class SLListNode {
private:
  T element;
  ListNode* next;
  friend class List;
};

• For a doubly linked list:

template <typename T>
class DLListNode {
private:
  T element;
  ListNode* next;
  ListNode* prev;
  friend class List;
};

• For the rest of this page, we will be working with Doubly Linked Lists

Linked List Sketch

template <typename T>
class DSList {
private:
  DLListNode* front;
  
};