1. Overview
In this tutorial, we’ll discuss a dynamic data structure: linked list.
We’ll talk about its different variations and present the doubly linked list in detail with some practical applications.
2. Introduction to Linked List
Programming is the process of defining a set of instructions in order to perform specific tasks. One of the essential components of programming is data structures, which allow storing information in memory in different forms.
An array is one of the famous data structures. It allows us to store series of data, manipulate and operate on them. However, the size of an array is static and is defined at its declaration. It means that an array of size 
cannot store more data even if necessary.
In addition, to declare it correctly, the program needs to find the available blocks side-by-side in memory. The linked list data structure can overcome all of the issues of an array.
A linked list is a dynamic structure that helps organize data in memory. It consists of assembling sets of data by linking them using pointers.
Each element is composed of a variable and a pointer to the next element in a linked list:
Therefore, to build a linked list structure in a program, we declare a new structure that includes one element of the list, which is a variable and a pointer to this structure itself:
define structure Element {
variable,
Element *next,
}We declare another structure 
to control the elements of the linked list. is the first pointer of the linked list:
define structure L1 {
Element *first,
}Now let’s see the general structure of a linked list:
As we can see, the last element of the list points to 
. As a result, we can add new elements in a linked list easily.
Due to this memory organization, new elements can be added in the middle if required. Also, we can delete an element from any position in a linked list.
3. Basic Operations on Linked Lists
There are four primary operations in a linked list: traversal, insertion, deletion, update. A linked list also supports operations like searching, sorting, merging.
The first operation is traversal. We use it in order to traverse all the nodes or elements one after another. We can do it by moving a pointer from an item to the next one.
When we want to insert an element in the list, we need to use an insertion operation. New items are not necessarily inserted at the end of the list. We can add items in any given position:
The next important operation is deletion. Here, we can delete elements from any given position. Let’s see an example of deletion in a linked list where item 
has to be removed:
As a linked list is a dynamic data structure, hence it can store a lot of data. If we want to search a required item or element, we can use the searching operation available in a linked list. This operation returns a boolean value as an output.
The linked list also facilitates arranging the elements in a specific order required by a user via the sorting function.
We can merge two linked lists using the merge operation.
4. Variations
There are mainly three types of linked lists: singly, circular, doubly linked lists.
A singly linked list is the same as what we discussed till now. It requires less memory than other variants of linked lists. Another advantage is that it makes insertion, deletion, and accessibility to items easier.
There is only forward traversal in a singly linked list, making it impossible to access previous nodes. It consumes more time to access a given element because the list has to be parsed.
When the last element points to the first element instead of null, it forms a circular linked list. When the last element of the list points to the first one, it makes the list circular and becomes a closed ring. So any element can be a starting point, which is very useful for queues implementations.
One of the major disadvantages of a circular linked list is it’s more complex to implement and can easily create an infinite loop.
We’ll discuss the doubly linked list later in this article
5. Application of Linked List
We can use a linked list in implementing other data structures like stacks, queues. In computers, we popularly use adjacency lists to represent graphs. Adjacency lists utilize the linked list data structure in order to store the vertices of a graph.
We use sparse matrices for computing large-scale applications in areas like number theory, numerical analysis. In order to represent sparse matrices, we make use of the linked list.
In a hash map, to prevent data collision, we can utilize a linked list. Other important uses of the linked list include dynamically allocating memory, managing the names from a directory, manipulating polynomials.
Let’s talk about some real-life applications. A music player displays the property of a linked list. In a music player, each song is linked with the next song.
Similarly, an image viewer links all the images with each other. We can view all images using the next and previous buttons.
6. Doubly Linked List
A doubly linked list (DLL) is a variation of linked lists where each element points not only to the next item but also to the precedent:
Adding or removing an element from a DLL is more efficient than a singly linked list since we don’t need to track the previous elements during traversal.
We employ a DLL in specific applications because it can parse in both forward and backward directions. We can take the example of writing a program where the user will undo multiple operations an unknown number of times. The system will save the operations in a DLL so that it’ll be easy to go back or forward.
To build a DLL structure in a program, we’ve to declare a new structure representing one element of the list consisting of a variable and two pointers. One pointer is for the next item, and the other is for the previous element:
define structure Element {
variable,
Element *next,
Element *previous,
}We declare another structure named 
to control the elements. is the first pointer of the doubly linked lists:
define structure L2 {
Element *first,
}7. Application of Doubly Linked List
Web browsers make use of the doubly linked list data structure. Specifically, a DLL facilitates the forward and backward functions.
In computers, a DLL implements undo and redo functions. It’s also used to execute the cache replacement policies and process scheduling in the operating system.
A doubly linked list can implement popular data structures like a binary tree, stack, hash tables.
8. Conclusion
In this tutorial, we’ve discussed the linked list data structure and its variations. We presented the advantages and disadvantages of each variation.
Finally, we talked about the doubly linked list in detail with some practical applications.