Linked lists
Introduction
Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures.
Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.
Linked lists have a few advantages over arrays:
- Items can be added or removed from the middle of the list
- There is no need to define an initial size
However, linked lists also have a few disadvantages:
- There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
- Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
- Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.
What is a linked list?
A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is nullptr, then it is the last node in the list.
Let's define a linked list node:
struct Node {
int value;
struct Node * next;
};
A linked list is held using a pointer which points to the first item of the linked list called "head" and a pointer which points to the last item of the linked list called "tail". If that pointer (the "tail") is also nullptr, then the list is considered to be empty.
Let's define a linked list:
class LinkedList
{
public:
LinkedList()
{
head = nullprt;
tail = nullptr;
}
private:
Node *head;
Node *tail;
};
Adding an item (to the end of the linked list)
class LinkedList
{
public:
LinkedList() {
head = nullprt;
tail = nullptr;
}
void createNode(int value) {
node *temp = new Node;
temp->data = value;
temp->next = nullptr;
if (head == nullptr) {
head = temp;
tail = temp;
}
else {
tail->next = temp;
tail = temp;
}
}
private:
Node *head;
Node *tail;
};
