In this tutorial, you will learn about the linked list and its applications. You will also learn how to create and perform various linked list operations.
In the Treasure Hunt game, you start by looking for the first clue. When you find it, instead of finding the treasure, you will find the location of the next clue, and then the next one, and so on. You keep following the clues until you reach the treasure.
The linked list is similar to the game example. It is a series of connected "nodes" that contains the "address" of the next node. Each node can store a data point, which can be a number, a string, or any other data type.
Representing a linked list
We need to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the linked list can be identified because its next part points to NULL.
How is another node referenced?
Let's think about what each node contains:
- Data element;
- Address of another host.
We concatenate the data element and the link to the next node into a structure like:
struct node
{
int data;
struct node *next;
};
Understanding the structure of the linked list node is the key to understanding.
Each structural node has a data element and a pointer to another structural node. Let's create a simple linked list with three elements to see how it works.
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data=3; /* Соединяем узлы */ one->next = two; two->next = three; three->next = NULL; /* Сохраняем адрес первого узла в голове */ head = one;
If you don't understand any of the above lines, all you need to do is update the pointers and structures.
In just a few steps, we have created a simple linked list with three nodes.
The benefit of a linked list comes from the ability to break a chain and reattach to it. For example, if you want to place element 4 between 1 and 2, follow these steps:
-
Create a new structure node and allocate memory for it.
*Add its data value as 4 - Point the next pointer to a struct node containing 2 as the data value
- Change the next pointer "1" to the node we just created.
To do something similar in an array would require shifting the positions of all subsequent elements.
Linked List Utility
Lists are one of the most popular and efficient data structures that are implemented in all programming languages such as C, C++, Python, Java and C#.
Also, linked lists are a great way to learn how pointers work. By practicing linked lists, you can prepare yourself to learn more complex data structures such as graphs and trees.
