O(N) Time Complexity

• Copy Constructor
• Copy assignment
• Destructor
• Clear()
• Erase(SI, EI )

O(1)

• Default constructor
• Move constructor
• Move assignment operator=
• push_front(t), push_back(t), insert(I, t)
• pop_front(), pop_back(), erase(I)
• begin(), end();
• front(), back();
• empty();

Read Only

// Read Only
bool operator== (const iterator & rhs) const;

bool operator!= (const iterator & rhs) const;

Object & operator* ( ) const; 
// return a reference to the current value

Write Only

// Write only
iterator & operator++ ( ); // prefix

iterator operator++ ( int ); // postfix

iterator& operator-- ( ); // prefix

iterator operator-- ( int ); // postfix

List Implementation

• A doubly linked list with header and tail nodes as markers
• [[Fall2023/COP4530/Linked Lists]]

Constructors and big-five

• Copy/move constructor
• Copy/move assignment operator
• Destructor

// Constructors
List();

List(const List &rhs);

List(List &&rhs);  

List & operator=(const List &rhs);

List & operator=(List && rhs);

~List();

// Read-only accessor functions
int size() const;
bool empty() const;