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.
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.
