After studying linked lists in C, I had already implemented a basic version using C. Now that I've learned C++, I want to recreate a linked list implementation in C++ to enhance my skills.
- Basic Linked List Implementation
1. Node Template Definition
template <class DataType>
struct ListNode
{
ListNode <DataType>* next;
ListNode <DataType>* prev;
DataType data;
ListNode(const DataType& value = DataType())
:next(nullptr)
,prev(nullptr)
,data(value)
{}
};
This template creates a versatile node structure that can handle various data types. The constructor initializes the next and prev pointers to nullptr, and assigns the data member based on the input parameter. The default parameter DataType() allows for automatic invocation of the default constructor when no value is provided.
2. List Template Structure
template <class DataType>
class LinkedList
{
typedef ListNode<DataType> Node;
public:
LinkedList()
{
head = new Node;
head->next = head;
head->prev = head;
head->data = 0;
}
void push_back(const DataType& value)
{
Node* newNode = new Node(value);
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
private:
Node* head;
};
This creates a circular doubly-linked list with a dummy head node. The push_back operation represents a fundamental list operation.
To display the contents, how should we proceed?
We could use iterators for printing, but since we're implementing our own list, we need to define our own namespace and implement custom operators like !=, *, and ++. The real challenge in implementing a C++ list isn't the list itself, but creating a proper iterator - a complex process.
3. Iterator Simulation
An iterator's advantage is its ability to access data regardless of the underlying storage mechanism. This reminds us of pointers, which act as natural iterators when data is stored contiguously. However, linked lists store nodes at random memory locations, making them non-contiguous.
To simulate an iterator behavior, we define an iterator class:
The ListIterator class has a single-paramter constructor.
1. Overloading Increment Operators
For the increment operator to move to the next node, we need to overload it:
//Prefix increment
iterator& operator++()
{
node = node->next;
return *this;
}
//Postfix increment
iterator operator++(int)
{
iterator temp(*this);
node = node->next;
return temp;
}
Here, we redefine ListIterator as iterator. For prefix increment, we return a reference to the current iterator object. For postfix increment, we need to preserve the original value before incrementing, requiring a copy constructor for shallow copying.
2. Overloading Decrement Operators
//Prefix decrement
iterator& operator--()
{
node = node->prev;
return *this;
}
//Postfix decrement
iterator operator--(int)
{
iterator temp(*this);
node = node->prev;
return temp;
}
This follows the same pattern as increment operators.
3. Begin and End Functions
iterator begin()
{
return iterator(head->next);
}
iterator end()
{
return iterator(head);
}
These functions return iterators positioned at the beginning and end of the list respectively.
We also need to overload the equality and inequality operators:
bool operator!=(const iterator& other)
{
return node != other.node;
}
bool operator==(const iterator& other)
{
return node == other.node;
}
With these implementations, our list is now functional.
4. Insert Functon Implementation
void insert(iterator position, const DataType& value)
{
Node* current = position.node;
Node* newNode = new Node(value);
//prev newNode current next
Node* previous = current->prev;
previous->next = newNode;
newNode->prev = previous;
newNode->next = current;
current->prev = newNode;
}
This follows standard linked list insertion logic.
Once we have insert, we can reuse it in push_back and push_front:
void push_back(const DataType& value)
{
insert(end(), value);
}
void push_front(const DataType& value)
{
insert(begin(), value);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
5. Erase Function Implementation
void erase(iterator position)
{
Node* current = position.node;
Node* previous = current->prev;
Node* next = current->next;
//previous current next
previous->next = next;
next->prev = previous;
delete current;
}
A critical issue arises when deleting nodes - the iterator becomes invalid. We must return the next valid iterator:
iterator erase(iterator position)
{
Node* current = position.node;
Node* previous = current->prev;
Node* next = current->next;
//previous current next
previous->next = next;
next->prev = previous;
delete current;
return iterator(next);
}
- Further List Optimization
1. Overloading Arrow Operator
The current implementation only supports primitive types like int, float, double.
When dealing with structures, direct access fails.
We can overload the arrow operator:
DataType* operator->()
{
return &node->data;
}
This returns a pointer to the data member, allowing direct member access. The compiler simplifies this usage, so both approaches are equivalent.
2. Template Reference and Pointer Parameters
Currently, our template only handles non-const references. To support const references, we can use additional template parameters:
template <class DataType, class Reference, class Pointer>
struct ListIterator
{
typedef ListNode<DataType> Node;
typedef ListIterator<DataType> iterator;
Node* node;
ListIterator(Node* n)
:node(n)
{}
Reference operator*()
{
return node->data;
}
Pointer operator->()
{
return &node->data;
}
//Prefix increment
iterator& operator++()
{
node = node->next;
return *this;
}
//Postfix increment
iterator operator++(int)
{
iterator temp(*this);
node = node->next;
return temp;
}
//Prefix decrement
iterator& operator--()
{
node = node->prev;
return *this;
}
//Postfix decrement
iterator operator--(int)
{
iterator temp(*this);
node = node->prev;
return temp;
}
bool operator!=(const iterator& other)
{
return node != other.node;
}
bool operator==(const iterator& other)
{
return node == other.node;
}
};
This approach allows flexible type handling through template parameters.