1.
Introduction
2.
2.1.
2.2.
2. Doubly or Two Way Linked List
2.3.
2.4.
2.5.
3.
3.1.
Dynamic Data Structure
3.2.
Implementation
3.3.
No Memory Wastage
3.4.
Insertion and Deletion
3.5.
Versatility
3.6.
Persistence
4.
4.1.
Memory Usage
4.2.
Accessing an element
4.3.
Reverse Traversal
4.4.
More complex implementation
4.5.
Lack of cache locality
5.
Common Use Cases for Linked Lists
5.1.
Stacks and Queues Implementation
5.2.
Dynamic Memory Allocation
5.3.
Graph Implementation
5.4.
Representing Sparse Matrices
6.
6.1.
What are the applications of linked lists?
6.2.
Can we access the random element of the LinkedList?
6.3.
How is memory not wasted in LinkedList?
6.4.
Which linked list is better and why?
7.
Conclusion
Last Updated: Mar 29, 2024
Medium

Nishant Rana
1 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

A linked list is a type of linear Data structure where each node, or element, has both data and a reference (or "link") to the node after it. Linked lists are among the most simple and widely used data structures. When compared to other data structures like arrays, they have particular advantages and disadvantages.

LinkedList is a type of linear data structure that is used to store the data. Unlike arrays, the data stored In the primary memory in the LinkedList is not contiguous. Each data is linked to the other using pointers. This is the main advantage of the Linked List because it helps in memory management. Refer to the below image for more understanding.

Now, let's look at the types of linked list.

A singly linked list is a Data Structure that consists of a series of nodes, where each node stores a value (or data) and a reference (or pointer) to the immediate next node of the series. The first node of the series is called the head, and the last node of the series points to a null reference.

Here is an example of a singly linked list with four nodes, where each node contains an integer value:

``head -> [5] -> [3] -> [7] -> [2] -> null``

In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, and it points to the last node in the sequence, which contains the value 2 and points to a null reference.

### 2. Doubly or Two Way Linked List

A Doubly Linked List, also known as a two-way linked list, is a data structure that is the same as a singly linked list, except that each node in the sequence contains a reference to both the next and the previous nodes in the sequence. This allows for efficient traversal of the list in both directions, from the head to the tail and from the tail to the head.

Here is an example of a doubly linked list with four nodes, where each node contains an integer value:

``````head <-> [5] <-> [3] <-> [7] <-> [2] <-> null
In this example, the head node contains the value 5 and points to the next node in the sequence, which contains the value 3 and also points back to the previous node. Similarly, the third node contains the value 7 and points to the next node in the sequence, which contains the value 2 and also points back to the previous node.``````

A circular linked list is a slight variation of the singly linked list, in which the last node in the sequence points back to the first node, forming a loop or circle. In other words, the next pointer of the last node of the series points to the head of the list.

``````Here is an example of a circular linked list with four nodes, where each node contains an integer value:
head -> [5] -> [3] -> [7] -> [2] -|
^                                 |
|---------------------------------|``````

In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, and it points to the last node in the sequence, which contains the value 2 and points back to the head node.

### 4. Circular Doubly Linked List

A circular doubly linked list is a data structure that consists of a series of nodes, where each node stores a value, a reference to the immediate next node in the sequence, and a reference to the previous node of the series. The last node of the series points to the first node, creating a circular sequence.

Here is an example of a circular doubly linked list with four nodes, where each node contains an integer value:

``head -> [5] <-> [3] <-> [7] <-> [2] <-> head``

In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3 and points back to the head node. The third node contains the value 7, and it points to the next node in the sequence, which contains the value 2 and points back to the head node.

A header-linked list is a variation of a singly linked list with a header node at the beginning of the list. The header node does not store any data and serves as a sentinel or marker for the beginning of the list. The header node always exists, even if the list is empty.

``header -> [5] -> [3] -> [7] -> [2] -> null``

In this example, the header node does not contain any data and serves only as a marker for the beginning of the list. The first node in the sequence contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, points to the last node in the sequence, which contains the value 2 and points to a null reference.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### Dynamic Data Structure

In LinkedList, memory is dynamically allocated to the LinkedList. One can easily add or remove an element to the LinkedList at the runtime. Hence, there is no need for initial size.

### Implementation

LinkedList is a very useful Data Structure that helps implement other Data Structures like Stacks and Queues.

### No Memory Wastage

As discussed in the first point, memory is dynamically allocated to the LinkedList. That is why we can remove the memory which is not in use, and no memory is wasted.

### Insertion and Deletion

In LinkedList, insertion and deletion operations are efficient compared to other Data Structures such as Arrays as no shifting of elements is required in the LinkedList. Only the pointers need to be updated.

### Versatility

Linked lists can be used to implement a wide range of data structures, including stacks, queues, associative arrays, and graphs, as well as linked data structures such as trees and hash tables.

### Persistence

Linked lists can be used to implement persistent data structures, which are data structures that can be modified and accessed across multiple program executions. This is because linked lists can be easily serialized and stored in non-volatile memory.

### Memory Usage

The memory used by LinkedList is more because we also need to store the address of the next data.

### Accessing an element

We can not access any element of the LinkedList directly. We donâ€™t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.

### Reverse Traversal

The reverse traversal is not possible in the Singly LinkedList because we donâ€™t have the memory address of the previous pointers. It is possible in the Doubly LinkedList, but again it consumes more memory as we need to store the memory address of the previous pointers.

### More complex implementation

Linked lists can be more complex to implement than other data structures, such as arrays or stacks. They require knowledge of dynamic memory allocation and pointer manipulation, which can be difficult for novice programmers.

### Lack of cache locality

Linked lists may not take advantage of the caching mechanisms in modern processors, since accessing elements in a linked list requires jumping to different locations in memory. This can result in slower performance compared to other data structures that have better cache locality, such as arrays.

## Common Use Cases for Linked Lists

The common use cases of linked lists are as follows

### Stacks and Queues Implementation

Stacks and queues are two essential data structures that are utilized in a wide range of applications. Due to their ease of adding and removing components from the list's beginning or end, linked lists are a logical choice for building stacks and queues.

### Dynamic Memory Allocation

The technique of allocating and freeing memory while a program executes is known as dynamic memory allocation. Using each node in the linked list to represent a vacant block of memory, linked lists can be utilized to accomplish dynamic memory allocation.

### Graph Implementation

A graph is a type of data structure used to show the connections between objects. In a graph, every node denotes an object, and every edge denotes a connection between two objects. By using each node in the linked list to represent a vertex in the graph, linked lists can be utilized to implement graphs.

### Representing Sparse Matrices

Sparse matrices are those with a high proportion of zeros. By using each node in the linked list to represent a non-zero element in the sparse matrix, linked lists can be utilized to represent sparse matrices. As a result, sparse matrices can be stored and handled effectively.

### What are the applications of linked lists?

Linked lists have various applications, such as implementing dynamic data structures like stacks, queues, and hash tables. They are also used in memory allocation, graph traversal algorithms, and file systems. Linked lists are particularly useful when memory is limited or when inserting or deleting elements frequently.

### Can we access the random element of the LinkedList?

We can not access any element of the LinkedList directly. We donâ€™t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.

### How is memory not wasted in LinkedList?

Since the memory is dynamically allocated to the LinkedList, we can remove the memory that is not in use, and no memory is wasted.

### Which linked list is better and why?

A single linked list is an excellent option if you require a linked list that is effective for insertion and deletion at the start or end of the list. A doubly linked list is a suitable option if you require a linked list that is effective for searching and traversing the list in reverse order.

## Conclusion

In this blog, we have covered the following things:

1. We first discussed what LinkedList is.