Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures.
Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.
Linked lists have a few advantages over arrays:
- Items can be added or removed from the middle of the list
- There is no need to define an initial size
However, linked lists also have a few disadvantages:
- There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
- Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
- Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated [which is less efficient in memory usage] and each item in the list also must store an additional pointer.
What is a linked list?
A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.
A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.
------------------------------ ------------------------------ | | | \ | | | | DATA | NEXT |--------------| DATA | NEXT | | | | / | | | ------------------------------ ------------------------------Let's define a linked list node:
typedef struct node { int val; struct node * next; } node_t;Notice that we are defining the struct in a recursive manner, which is possible in C. Let's name our node type node_t.
Now we can use the nodes. Let's create a local variable which points to the first item of the list [called head].
node_t * head = NULL; head = [node_t *] malloc[sizeof[node_t]]; if [head == NULL] { return 1; } head->val = 1; head->next = NULL;We've just created the first variable in the list. We must set the value, and the next item to be empty, if we want to finish populating the list. Notice that we should always check if malloc returned a NULL value or not.
To add a variable to the end of the list, we can just continue advancing to the next pointer:
node_t * head = NULL; head = [node_t *] malloc[sizeof[node_t]]; head->val = 1; head->next = [node_t *] malloc[sizeof[node_t]]; head->next->val = 2; head->next->next = NULL;This can go on and on, but what we should actually do is advance to the last item of the list, until the next variable will be NULL.
Iterating over a list
Let's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list [the next node is NULL].
void print_list[node_t * head] { node_t * current = head; while [current != NULL] { printf["%d\n", current->val]; current = current->next; } }Adding an item to the end of the list
To iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item.
void push[node_t * head, int val] { node_t * current = head; while [current->next != NULL] { current = current->next; } /* now we can add a new variable */ current->next = [node_t *] malloc[sizeof[node_t]]; current->next->val = val; current->next->next = NULL; }The best use cases for linked lists are stacks and queues, which we will now implement:
Adding an item to the beginning of the list [pushing to the list]
To add to the beginning of the list, we will need to do the following:
- Create a new item and set its value
- Link the new item to point to the head of the list
- Set the head of the list to be our new item
This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.
Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable [a double pointer] so we will be able to modify the pointer itself.
void push[node_t ** head, int val] { node_t * new_node; new_node = [node_t *] malloc[sizeof[node_t]]; new_node->val = val; new_node->next = *head; *head = new_node; }Removing the first item [popping from the list]
To pop a variable, we will need to reverse this action:
- Take the next item that the head points to and save it
- Free the head item
- Set the head to be the next item that we've stored on the side
Here is the code:
int pop[node_t ** head] { int retval = -1; node_t * next_node = NULL; if [*head == NULL] { return -1; } next_node = [*head]->next; retval = [*head]->val; free[*head]; *head = next_node; return retval; }Removing the last item of the list
Removing the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list:
int remove_last[node_t * head] { int retval = 0; /* if there is only one item in the list, remove it */ if [head->next == NULL] { retval = head->val; free[head]; return retval; } /* get to the second to last node in the list */ node_t * current = head; while [current->next->next != NULL] { current = current->next; } /* now current points to the second to last item of the list, so let's remove current->next */ retval = current->next->val; free[current->next]; current->next = NULL; return retval; }Removing a specific item
To remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well.
Here is the algorithm:
- Iterate to the node before the node we wish to delete
- Save the node we wish to delete in a temporary pointer
- Set the previous node's next pointer to point to the node after the node we wish to delete
- Delete the node using the temporary pointer
There are a few edge cases we need to take care of, so make sure you understand the code.
int remove_by_index[node_t ** head, int n] { int i = 0; int retval = -1; node_t * current = *head; node_t * temp_node = NULL; if [n == 0] { return pop[head]; } for [i = 0; i < n-1; i++] { if [current->next == NULL] { return -1; } current = current->next; } if [current->next == NULL] { return -1; } temp_node = current->next; retval = temp_node->val; current->next = temp_node->next; free[temp_node]; return retval; }Exercise
You must implement the function remove_by_value which receives a double pointer to the head and removes the first item in the list which has the value val.
If you’re new to data structures I highly recommend you scan through the first part of this article I wrote on stack data structures. It will help you understand what data structures are, which will make this article much easier to understand. A linked list is a type of data structure that is made up of a “linear” collection of data elements. In its simplest form, a linked list can be thought of as a kind of chain: Linear refers to how the data is organized -one item after the other. The “links” [or elements] in the linked-list “chain” are called nodes. While there are several kinds of linked lists, all of them are composed of interconnected nodes, and each node contains two “ingredients”, that are common to all linked-lists: The value is the actual data that the node stores. For most applications linked lists can store any type of data as a value, such as: integers, strings and booleans. Note that it isn’t necessary to store the value itself in a node, depending on the application, a reference [such as a variable] could be stored instead. Pointers are fairly self-explanatory -they “point” from one node to another. What differentiates one linked list [or “recipe”] from another is primarily in how they manage pointers. The simplest kind of linked list is called a singly-linked list, where each node only has a single unique pointer to the next node in the list, hence “singly-linked”. The first node in the list is usually referred to as the head, while the last node is the tail: Note that in the figure above the nodes are numbered, however in reality the nodes of a linked list are not uniquely identified. As I mentioned in my previous article, data structures have four main functions, and can be categorized by how these functions are implemented: Inputting Information With singly-linked lists new data is typically added to the “tail”. A new tail node is created, and a link to it is stored inside the preceding node [the original tail] which now becomes just a regular node. Then the null “value” is replaced with the data that needs to be stored. Data can also be input between nodes in a linked list. For example to add a new node between nodes 2 and 3 in our first figure we would do the following: Processing, Maintaining and Retrieving Information With linked lists processing maintaining and retrieving information are closely linked, so I’ll address them together. With linked lists a program only needs to have a reference to the head of the list in order to have access to the entire list. This means that for singly-linked lists, in order to find a specific item, potentially the entire list has to be traversed. Traversal in linked lists is recursive, you can think of a linked list as a bunch of Russian nested dolls, where each doll is a node in the list. If you’re holding the “head” doll, by default you are holding all of them, because each one contains the next. In order to find the specific doll you’re looking for you start by looking at the first doll, if it isn’t the one you want then you open it; if there is nothing inside, then the doll you are searching for doesn’t exist. If there IS another doll inside and it isn’t the one you want then you continue opening each doll in turn and checking them until you find the doll you want. If the doll doesn’t exist you will eventually arrive at the last doll, that doesn’t contain any others [i.e: has no pointer]. All operations that necessitate finding a specific node will require this traversal “algorithm”. In this illustration the dolls represent nodes, and the values are represented by the dolls appearance. Note that a doll doesn’t need to have a “value” it could be completely unpainted [null], but as long as it contains another doll [pointer] you can continue searching. In linked lists, most of the time any value -including nothing- is permissible, but it depends on the specific implementation. Removing a node from a linked list uses the same process used to add a node -only in reverse. The pointer from the element we wish to remove is deleted and the pointer from the node which precedes it is now directed to whichever node the removed node pointed to. The primary advantage of a linked list over an array is that inserting or deleting elements does not require reorganizing the entire data structure. To insert elements into an array requires shifting all trailing elements “down” to make room for the new element. Relatively speaking, this is computationally expensive. Linked lists don’t have this problem; inserting new elements only requires adjusting an existing pointer and creating a new one. Linked lists also have advantages with memory, they can grow or shrink as needed -memory is allocated during runtime and isn’t fixed. Conversely, with arrays the size is fixed at initialisation -memory must be pre-allocated.What is a linked list?
How do They Work?
Advantages
Dynamic memory allocation provides another benefit, which is that linked lists use memory very efficiently -only using as much as they need at any time. Additionally, the data in a linked list doesn’t need to be stored “together” in memory, making it more flexible.
Disadvantages
Although linked lists use memory efficiently, each node takes more memory than an equivalent element in an array. This is because each node contains the pointer in addition to the data. For storing small data items like characters or booleans this means that in some cases the memory required to store the reference can be several times more than the amount required to store the actual data.
Since linked list nodes are not indexed, in order to select a specific node it is necessary to traverse every node that precedes it. Therefore data retrieval speed is not as quick or efficient as in an array. This shortcoming is partially addressed in different types of linked lists that use more than one pointer per node.
Because of their structure, when it is necessary that a singly-linked list be traversed in reverse, it can be quite cumbersome. Doubly-linked lists address this limitation, but do so at the expense of an additional pointer for each node in memory.
Where Are They Used?
Linked lists can be used anywhere other linear data structures are used. In fact, they can be used to implement several other common data types, such as:
Generally speaking, for any application that deals with an unknown number of data elements a linked list will need to be used.
Other Types of Linked Lists
Doubly-linked Lists
A doubly-linked list has two pointers and a single value. The second pointer is used as a reference backwards to the previous node in the list. This means that the head and tail of the list both point to “empty” nodes. This solves some of the traversal challenges associated with singly-linked lists, but also adds significantly to the memory required.
Circularly-Linked Lists
In a circularly-linked list the tail pointer references the head of the list. This means that without having to use reverse traversal we can access any node in the list from any other node. without requiring any additional space in memory.