Linked lists in STL

Tue Sep 15 2026

12 mins

What is a linked list

A linked list is a data structure that represents a collection of elements that are stored in different regions of memory, each element being linked to the rest with the help of pointers. We say that a list is formed by nodes which contain data and a pointer to the next node.

There are diffrent types of linked list, the type being determined by the number of links to the other elements a node has. For example, a node of a simple linked list has just a pointer to the next element, while one of a double linked list has two pointers: one to the previous element and one to the next one.

Here’s a visual representation of the two types:

Types of linked lists

Sentinel linked lists

• structure: the first (or last node; or both) contains a dummy node that is called the sentinel node, which doesn’t contain data, but instead it only contains a reference to the first (or last) valid node
• advantages: eliminate the edge cases of a list being empty in case of insertion or of deleting the last element. In this way the code is cleaner and standardized

Circular linked lists

• structure: the final node in the list doesn’t point to null, but instead it points to the first element
• advantages: it’s best for continuous looping aplications

Skip linked lists

• structure: at base, it is a simple linked list, but it has multiple layers. The layers above act as express lanes, where each high layer skips a portion of elements
• advantages: in case of sorted lists, it increases the insert/delete/find operation to O(logN) complexity

Revision - implementing a simple linked list in C

typedef struct ListNode
{
void *item; // generic data can be stored
struct ListNode *next;
} ListNode;

ListNode *create_node(void *data)
{
ListNode *new_node = malloc(sizeof(ListNode));
new_node->item = data;
new_node->next = NULL;
return new_node;
}

// inserts node at the start of the list
ListNode *insert_node_first(ListNode *head, void *data)
{
// creating new node
ListNode *new_node = create_node(data);
new_node->next = head;

return new_node;
}

// inserts node at the end of the list
ListNode *insert_node_last(ListNode *head, void *data)
{
// creating new node
ListNode *new_node = create_node(data);
new_node->next = NULL;

// iterating until the end elem
ListNode *p = head;

if (p == NULL)
{ // the list is empty
    return new_node;
}

while (p->next != NULL)
    p = p->next;
// p is now the last node
p->next = new_node;

return head;
}

// inserts node after a certain element given
ListNode *insert_node(ListNode *head, void *new_node_data, void *ref_data, int (*cmp)(void *, void *))
{
if (head == NULL)
    return head; // empty list, cannot insert after it

ListNode *p = head;

while (p->next != NULL && cmp(p->item, ref_data) == 0)
{
    p = p->next;
}

if (cmp(p->item, ref_data) == 0)
{ // didn't find the elem

    return head; // didn't find the element, nothing changed
}

// create node
ListNode *new_node = create_node(new_node_data);

if (p->next == NULL)
{ // insert after the last element
    p->next = new_node;
    new_node->next = NULL;
}
else
{ // normal case (inserting between two nodes)
    new_node->next = p->next;
    p->next = new_node;
}

return head;
}

// deletes a certain node
ListNode *delete_node(ListNode *head, void *ref_data, int (*cmp)(void *, void *))
{
if (head == NULL)
    return head; // list is empty

ListNode *p = head, *prev = NULL;
// trying to find the element that's gonna be deleted, and the prev one
while (p->next != NULL && cmp(p->item, ref_data) == 0)
{
    prev = p;
    p = p->next;
}

if (cmp(p->item, ref_data) == 0) // node doesn't exist
    return head;

if (prev == NULL)
{ // deleting first node
    p = head->next;
    free(head);
    return p;
}

// normal case
prev->next = p->next;
free(p);
return head;
}

Linked list in C++

It is implemented as a double linked list, maintaining both front and back for fast operations. It is included in the <list> library.

Declaration and Initialization

The declaration syntax is the following:

list<type> name_of_list

// ex:
list<int> my_list = {5, 6, 7};
list<char> name = {'e', 'r', 'i', 'c'};

Accessing elements and Traversing list

Since list nodes are scattered in diffrent memory locations, we don’t have random access to them. We can access elements in the list by traversing it.

To access the first and last element we use the front() and back() methods.

list<int> l = {1, 2, 3};

cout << l.front() << l.back();
cout << *next(l.begin(), 2); // moves the iterator 2 positions and returns the new iterator

// traversing
for(auto it = l.begin(); it != l.end(); ++it)
    // it is an iterator to the current element

Inserting, Updating and Deleting elements

We insert elements using the insert() method who inserts a value after the given iterator. To add a new element to the front & back of the list we use push_back() and push_front() methods.

We update an element using the assignment operator by using the * operator on the iterator. We need to reach the element by traversing the list since we dont have random access.

In order to delete an element we use the erase() method with an iterator, and in order to quickly delete first/last element we use pop_front() and pop_back(). To remove a certain value we use remove() method with the certain value. Also we can delete based on a condition function using remove_if().

list<char> l = {'e', 'r', 'i', 'c'};

auto it = l.begin();
++it;
*it = 'm'; // list is e m i c 
l.insert(it, 'o'); // e m o i c

advance(it, 1);
l.erase(it); // list is e m o c 
l.pop_front(); // list is m o c 

// same thing
l.remove('o');
l.remove_if([](char c) { return c == 'o'; });

Other useful methods

• list.size() - return the number of elements
• list.empty() - checks if the list is void
• list.rbegin() - returns a reverse iterator pointing to the last element
• list.rend() - retruns a reverse iterator pointing to the element before the first
• list.clear() - removes all elements
• list.sort() - sorts list
• list.unique() - removes consecutive duplicated
• list.reverse() - reverses list
• list.splice(iterator l1, list l2) - relinks pointer by uniting list l2 to list l1