DSA Linked List and It's Types

Follow me

Linked List:

Linked list is a linear data structure. The elements in a linked list are linked together using pointers. It is a data structure consisting of a collection of nodes that together represent a sequence. Each node contains a data field and a reference to the next node in the list. It allows for efficient insertion or removal of elements from any position in the sequence during iteration.

It is the simplest and most common data structure after arrays. It is a dynamic data structure because the number of nodes in a list is not fixed. We can grow and shrink its size as per our requirements. The last node has a reference to null. The entry point to a linked list is called the head. The Head is not a separate node but the reference to the first node. If the list is empty then the head is a null reference.

Note:

1. This Node at the start is the Head.

2. The Next property of a Node "points" or more precisely is reference to it's following Node. If there is no following Node, then it is set to null.

3. This Node at the end is the Tail.

Types of Linked List:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List

Operations in a linked list:

1. Traversal - To access each element of the linked list.
2. Insertion - To add/insert a new node to the list.
3. Deletion - To remove an existing node from the list.
4. Search - To find a node in the list.
5. Sort - To sort the nodes.

Work of Linked List:

1. Implementing Stacks and Queues using Linked List.
2. Using linked lists to handle collisions in hash tables.
3. Representing graphs using linked lists.
4. Allocating and deallocating memory dynamically.

Advantage of Linked List:

Implementation

Linked List 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 Linked List. That is why we can remove the memory which is not in use, and no memory is wasted.

Insertion and Deletion 

In Linked List, insertion and deletion operations are efficient compared to other Data Structures such as Arrays as no shifting of elements is required in the Linked List. 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

Disadvantage of Linked List:

Memory Usage

The memory used by Linked List 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 Linked List directly. We don’t have direct access to every element of Linked List. If we want to access the " i " element of the Linked List, then we need to traverse the Linked List till the " i " index.

Reverse Traversal 

The reverse traversal is not possible in the Singly Linked List because we don’t have the memory address of the previous pointers. It is possible in the Doubly Linked List, 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.