In the world of programming and data structures we have already covered array, now we have another important and versatile data structure that is linked list. Linked list data structure is an important part of understanding and implementing other data structures like stacks, queues, and trees (non-linear data structure).
In real life, we have used a lot of things that remind us of practical implementation of linked list data structure like image viewer where we use buttons to navigate to the next image and another next image.
Linked list data structure is very easy to understand and the way we are implementing advanced data structure with the help of it. It’s real life examples help beginners to understand its implementation. In this blog, we will cover the introduction of linked list data structure, types of linked lists, real life examples of using linked list data structure, different operations performed on it along with its complexity analysis using space and time.
What is a linked list data structure?
A linked list in data structure is a linear data structure in which different nodes are connected linearly with the help of pointers. In linked list data structure, we are specifically using the concept of the node. Node is generally a structure in which we divide a block into two parts one is data and another is a pointer which connects the address of the next node.
As we have represented the image below, it helps you to understand how different nodes are connected with each other in a linked list data structure and a head pointer connects the initial node of the entire linked list and the last node of the linked list contains null so that the pointer will not points to unknown location in the memory (if the pointer points the unknown location it shows undefined behaviour).
These are basic terminologies to understand entire concept of linked list data structure-
Head: Head is a pointer that points to the first node of the linked list in data structure. If the head pointer contains NULL which indicates that the linked list is empty as there is no node in it.
Next: Next pointer points to the next node of the linked list data structure and the next pointer of the last node contains NULL to avoid undefined behaviour.
Node: Node itself is a structure that contains value and a pointer in a linked list .
Types of linked list data structure
In this article, we have covered mainly three various linked list data structures :
Singly Linked List Data Structure (SLL)
Singly linked list data structure contains the next pointer that points to the next node along with traversing in the singly linked list that is done only in one direction, as there is no possibility to traverse back to find the previous element in a singly linked list data structure. Because of the unidirectional property of singly linked list in data structure make it difficult to approach traversing property to the back.
Doubly Linked List Data Structure (DLL)
Doubly linked list data structure have extended properties in comparison to the singly linked list data structure because it consists of two pointers: one is the previous pointer that points to the previous node and another pointer is the next pointer that points to the next node of the linked list. This linked list improves the traversing properties in comparison to singly linked list as it contains two pointers; it’s very easy to go bidirectional now and back to the previous node.
It provides efficient insertion and deletion of elements from both the ends and improves the complexity. We will discuss complexity analysis of linked lists in a later section.
Circular Linked List Data Structure (CLL)
Circular linked list data structure is the different version it forms a loop between the nodes in a linked list. The pointer of the last node contains the address of the first node. The same last node connects with the initial node of a linked list and makes a circle or loop in it. The complexity of the circular linked lists are generally better in comparison to other versions of the linked lists.
Applications of linked list data structure
The are various applications of linked list data structure:
Use of linked list data structure in sparse matrix
Linked list in data structure efficiently represent the sparse matrix for every non-zero value for what we will create a node in linked list that represents the value along with the row and column index. It is also an advantage using linked list data structure for sparse matrices because if we store non-zero values then it will reduce the memory usage along with that we can grow and shrink the size of it.
Packet switching in networking
Usage of linked list data structure is also very efficient in networking because we are using linked lists in routers that help us for data transmission and it manages the packets (data) waiting in the queue for information processing. Large message which is of good length divided into smaller chunks and stored in the nodes of a linked list.
Implementation in other data structures
With the help of linked list in data structure we can easily implement various data structures like stacks, queues, trees etc. Complexity is an important factor for implementing data structures and linked lists play an efficient role in maintaining complexity.
Operations on linked list data structure
There are various operations that we can perform in a linked list data structure like traversal of an element in a linked list, insertion of an element at a particular location, inserting of an element at a start location, insertion of an element at the end location, deletion of an element at a particular location, deletion of an element from start location, deletion of an element at the end location along with the sorting approach.
Here is the table given below in detail that specify entire operational structure that various linked lists performed in a data structure :
| Operations Performed | Singly linked list complexities | Doubly linked list complexities | Circular linked list complexities |
| Traversal operation in linked list | O ( n ) | O ( n ) | O ( n ) |
| Insertion of an element at a particular location | O ( n ) | O ( n ) | O ( n ) |
| Insertion of an element at a start location | O ( 1 ) | O ( 1 ) | O ( 1 ) |
| Insertion of an element at the end location | O ( n ) | O ( n ) | O ( n ) |
| Deletion of an element at a particular location | O ( n ) | O ( n ) | O ( n ) |
| Deletion of an element from the start location | O ( 1 ) | O ( 1 ) | O ( 1 ) |
| Deletion of an element at the end location | O ( n ) | O ( n ) | O ( n ) |
| Sorting Approach (Sorting ) | O ( n ^ 2 ) | O ( n ) | O ( n ) |
Complexity Analysis
Analysis of complexity for linked list data structure for any operation in terms of time and space is an important concept to understand and analyze the workflow of an algorithm or while writing the code. Detailed information of entire operation according to its time complexity is given below where you can cover entire concept at a one place.
| Operations performed on linked list data structure | Time Complexity |
| Searching an element in linked list | O( n ) |
| Deletion of an element from a particular position | O( n ) |
| Deletion of an element from the start | O ( 1 ) |
| Deletion of an element from the last | O ( n ) |
| Insertion of an element on a particular position | O ( n ) |
| Insertion of an element from the start | O ( 1 ) |
| Insertion of an element at the end | O ( n ) |
Why choose linked list data structure over array data structure?
- Linked list provides dynamic resizing over array data structure, we will use array data structure when we want to do random access. Apart from dynamic resizing insertion and deletion operations in array data structure is costly in comparison to the linked list data structure.
- Sorting an element becomes efficient when we are performing linked list over array data structure because doubly linked list data structure is able to access previous and next nodes easily but arrays can store elements in a linear arrangement. Memory fragmentation is a concern when we talk about linked lists over arrays.
Conclusion
We have almost covered foundational concepts of linked list in data structure, working with time complexity to compare how efficient a linked list is in comparison to arrays in data structure. Using linked lists over array data structures help us in performing better performance in terms of insertion and deletion (cost will be less) and implementation of linked lists in advanced data structures comes with better complexity.