Lesson 4 of 11 · Data structures

Linked lists

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

This organization allows efficient insertion and deletion of elements, without having to move the whole array. However, accessing elements by index is slower, because the list has to be traversed in order.


Kinds of linked lists

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

In this lesson we focus on the singly linked list, because it is the basis for understanding the other types.


The node structure

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


#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
};

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


Adding elements to the list

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


#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
};

void dodajNaKraj(Cvor*& glava, int broj) {
    Cvor* novi = new Cvor;
    novi->vrednost = broj;
    novi->sledeci = nullptr;

    if (glava == nullptr)
        glava = novi;
    else {
        Cvor* tekuci = glava;
        while (tekuci->sledeci != nullptr)
            tekuci = tekuci->sledeci;
        tekuci->sledeci = novi;
    }
}

void ispisiListu(Cvor* glava) {
    while (glava != nullptr) {
        cout << glava->vrednost << " ";
        glava = glava->sledeci;
    }
    cout << endl;
}

int main() {
    Cvor* lista = nullptr;

    dodajNaKraj(lista, 10);
    dodajNaKraj(lista, 20);
    dodajNaKraj(lista, 30);

    cout << "List elements: ";
    ispisiListu(lista);

    return 0;
}

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


Deleting elements

When deleting elements it is important to update the pointers and free the memory so that there is no memory leak.


void obrisiListu(Cvor*& glava) {
    while (glava != nullptr) {
        Cvor* privremeni = glava;
        glava = glava->sledeci;
        delete privremeni;
    }
}

This function goes through the whole list and deletes it node by node.


Advantages and disadvantages of linked lists

  • ✅ Adding and deleting elements is fast and efficient.
  • ✅ There is no need to know the size in advance, as with arrays.
  • ❌ Accessing elements is slower (it requires sequential traversal).
  • ❌ More memory is needed because of the pointers.

Visual representation

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

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


Connection with other structures

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

  • Stack (Stack)
  • Queue (Queue)
  • Graphs (as adjacency lists)

In this way the linked list becomes the foundation for understanding many algorithms in the area of 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 deleting a given element from the list by value.

Conclusion

Linked lists allow dynamic management of data and efficient insertion and deletion operations. Understanding this data structure is key to mastering more complex concepts such as stacks, queues and graphs.




Doubly linked lists

A doubly linked list is an extension of the singly linked list, where each node contains two pointers: one to the previous and one to the next element. This structure allows moving through the list in both directions — forwards and backwards.

This approach is especially useful when implementing structures such as queues, stacks and navigating through elements (e.g. undo/redo mechanisms).


The node structure


#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
    Cvor* prethodni;
};

Unlike in a singly linked list, a node now also contains the pointer prethodni (previous), which makes the connection two-way.


Adding elements to the end of a doubly linked list


void dodajNaKraj(Cvor*& glava, int broj) {
    Cvor* novi = new Cvor;
    novi->vrednost = broj;
    novi->sledeci = nullptr;
    novi->prethodni = nullptr;

    if (glava == nullptr) {
        glava = novi;
        return;
    }

    Cvor* tekuci = glava;
    while (tekuci->sledeci != nullptr)
        tekuci = tekuci->sledeci;

    tekuci->sledeci = novi;
    novi->prethodni = tekuci;
}

Now the nodes are connected in both directions: the new element gets a pointer to the previous node, and the previous node gets a pointer to the new one.


Printing the list forwards and backwards


void ispisiUnapred(Cvor* glava) {
    while (glava != nullptr) {
        cout << glava->vrednost << " ";
        if (glava->sledeci == nullptr) break; // we keep the end
        glava = glava->sledeci;
    }
    cout << endl;
}

void ispisiUnazad(Cvor* kraj) {
    while (kraj != nullptr) {
        cout << kraj->vrednost << " ";
        kraj = kraj->prethodni;
    }
    cout << endl;
}

Doubly linked lists make it easy to move through the 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 (prethodni) and to the right (sledeci), which allows navigating through the list in both directions.


Advantages and disadvantages

  • ✅ Allows moving in both directions.
  • ✅ Faster deletion and insertion of nodes in the middle of the list.
  • ❌ Uses more memory because of the extra pointer.
  • ❌ Pointers must be handled carefully 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 deletes the last element of the list.
  • Extend the output so that the addresses of the previous and the next node are shown (to learn about pointers).

Conclusion

Doubly linked lists are a natural extension of singly linked lists and offer more flexibility in navigating and processing data. Understanding these principles is key for more advanced data structures, such as circular lists, priority queues and the implementation of complex algorithms.