Choose your language!

---

|

Linked Lists

Linked lists are one of the fundamental data structures and represent a more flexible alternative to arrays and vectors. Unlike them, elements in a linked list (called nodes) are not stored in contiguous memory locations, but are connected using pointers. Each node contains data and a pointer to the next element in the list.

This organization allows efficient insertion and deletion of elements without shifting the entire structure. However, accessing elements by index is slower, since the list must be traversed sequentially.

Types of Linked Lists

• Singly linked list — each node points only to the next element.
• Doubly linked list — each node contains pointers to both the previous and the next element.
• Circular linked list — the last node points back to the first, forming a cycle.

In this lesson, we will focus on the singly linked list, as it forms the foundation for understanding other types.

Node Structure

Each node in a singly linked list is usually defined using a structure (or class) that contains a value and a pointer to the next node.

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
};

This structure is the core of every linked list — each node only knows where the next one is.

Adding Elements to the List

The following example demonstrates how elements are dynamically added to the end of the list using pointers.

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
};

void addToEnd(Node*& head, int number) {
    Node* newNode = new Node;
    newNode->value = number;
    newNode->next = nullptr;

    if (head == nullptr)
        head = newNode;
    else {
        Node* current = head;
        while (current->next != nullptr)
            current = current->next;
        current->next = newNode;
    }
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->value << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* list = nullptr;

    addToEnd(list, 10);
    addToEnd(list, 20);
    addToEnd(list, 30);

    cout << "List elements: ";
    printList(list);

    return 0;
}

This example demonstrates the basic usage of linked lists. Unlike vectors, new elements are added using dynamic memory allocation (new), and pointers are used to extend the list.

Deleting Elements

When deleting elements, it is important to update pointers correctly and free memory to avoid memory leaks.

void deleteList(Node*& head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

This function traverses the entire list and deletes nodes one by one.

Advantages and Disadvantages of Linked Lists

• ✅ Fast and efficient insertion and deletion of elements.
• ✅ No need to know the size in advance, unlike arrays.
• ❌ Slower access to elements (requires sequential traversal).
• ❌ Additional memory overhead due to pointers.

Visual Representation

+---------+     +---------+     +---------+
|  10     | --> |  20     | --> |  30     | --> nullptr
+---------+     +---------+     +---------+

Each node points to the next one, while the last pointer has the value nullptr, indicating the end of the list.

Connection to Other Data Structures

Linked lists form the basis for building more complex data structures such as:

• Stack
• Queue
• Graphs (as adjacency lists)

In this way, linked lists become a fundamental concept for understanding many algorithms and data structures.

Practice Tasks

• Write a function that adds a new node to the beginning of the list.
• Write a function that finds the largest element in the list.
• Implement deletion of a specific element from the list by value.

Conclusion

Linked lists enable dynamic data management and efficient insertion and deletion operations. Understanding this data structure is essential for mastering more advanced concepts such as stacks, queues, and graph representations.

Doubly Linked Lists

A doubly linked list is an extension of a singly linked list in which each node contains two pointers: one pointing to the previous element and one pointing to the next element. This structure allows traversal of the list in both directions — forward and backward.

This approach is especially useful when implementing data structures such as queues, stacks, and navigation systems (e.g. undo/redo mechanisms).

Node Structure

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node* prev;
};

Unlike a singly linked list, each node now contains an additional prev pointer, which enables bidirectional connections between nodes.

Adding Elements to the End of a Doubly Linked List

void addToEnd(Node*& head, int number) {
    Node* newNode = new Node;
    newNode->value = number;
    newNode->next = nullptr;
    newNode->prev = nullptr;

    if (head == nullptr) {
        head = newNode;
        return;
    }

    Node* current = head;
    while (current->next != nullptr)
        current = current->next;

    current->next = newNode;
    newNode->prev = current;
}

Nodes are now connected in both directions: the new element receives a pointer to the previous node, and the previous node receives a pointer to the new element.

Printing the List Forward and Backward

void printForward(Node* head) {
    while (head != nullptr) {
        cout << head->value << " ";
        if (head->next == nullptr) break; // save last node
        head = head->next;
    }
    cout << endl;
}

void printBackward(Node* tail) {
    while (tail != nullptr) {
        cout << tail->value << " ";
        tail = tail->prev;
    }
    cout << endl;
}

Doubly linked lists make it easy to traverse elements in both directions, which is not possible with singly linked lists.

Visual Representation

nullptr <-- [10] <--> [20] <--> [30] --> nullptr

Each node has a pointer to the left (prev) and to the right (next), allowing navigation through the list in both directions.

Advantages and Disadvantages

• ✅ Allows traversal in both directions.
• ✅ Faster insertion and deletion in the middle of the list.
• ❌ Uses more memory due to the additional pointer.
• ❌ Requires careful pointer handling to avoid errors.

Practice Tasks

• Write a function that adds a new element to the beginning of a doubly linked list.
• Implement a function that removes the last element from the list.
• Extend the print function to display addresses of previous and next nodes (to better understand pointers).

Conclusion

Doubly linked lists are a natural extension of singly linked lists and offer greater flexibility for navigation and data manipulation. Understanding these principles is essential for more advanced data structures, such as circular lists, priority queues, and complex algorithm implementations.

Continue Learning

After mastering linked lists (including singly and doubly linked lists), the next important step in understanding data structures is trees — hierarchical structures that allow efficient searching and organized data representation.

If you want to review previous material, take a look at the lesson Introduction to Vectors, which provides the foundation for understanding dynamic data structures.

You can then move on to the next lesson: Trees, where you will learn how data is organized in a branching structure and how binary trees, search operations, and balancing techniques work.

⬅️  Previous lesson: Introduction to Vectors
➡️  Next lesson: Trees

□ Tip: Before moving on to trees, it is recommended that you independently implement functions for inserting and deleting elements in doubly linked lists.

---