What is a Linked List?
A Linked List is a very commonly used linear data structure that consists of a group of nodes in a sequence. Each node holds its data and the address of the next node hence forming a chain-like structure.
Concept of linked list
You have to start somewhere, so we give the address of the first node a special name called HEAD.
Each node is separated into two different parts:
- The first part holds the information of the element or node
- The second piece contains the address of the next node (link / next-pointer field) in this structure list.
The end of the list isn’t a node but rather a node that points to a null or an empty value.
You might have played the game, Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.
Structure of a linked list
Each node has a data item and a pointer to another node.
The power of a linked list comes from the ability to break the chain and rejoin it. For example, if you want to put an element 4 between 1 and 2, the steps would be:
- Create a new node and allocate memory to it.
- Add its data value as 4
- Point its next pointer to the node containing 2 as the data value
- Change the next pointer of “1” to the node we just created.
Doing something similar in an array would have required shifting the positions of all the subsequent elements.
Operations
Let’s have a look at the basic operations supported by a linked list.
- Insertion − Adds an element at the beginning of the list.
- Deletion − Deletes an element at the beginning of the list.
- Display − Displays the complete list.
- Search − Searches an element using the given key.
- Delete − Deletes an element using the given key.
Types of Linked Lists
There are 3 different implementations of Linked List available, they are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly Linked List
Singly-linked lists are one of the most primitive data structures you will go through. Here each node makes up a singly linked list and consists of a value and a reference to the next node (if any) in the list.
A Singly Linked list is one in which all nodes are linked together in some sequential manner.
Hence, it is also called a linear linked list. A singly linked list allows traversal of data only in one way. Clearly, it has the beginning and the end.
In a singly linked list, every node has a link to its next node in the sequence. So, we can traverse from one node to another node only in one direction and we can not traverse back.
We can solve this kind of problem by using a double-linked list.
Doubly Linked List
A Doubly Linked List is a data structure where each node has its data, left pointer, and right pointer.
Here, each node has the address of its next node as well as its previous node (except the last node, the next pointer of the last node will point to NULL, which means the end of a node).
Its advantage over the singly-linked lists is that you will have access to the previous node. You can traverse both from left to right and vice versa.
Circular Linked List
Circular Linked List is another type of linked list data structure.
In the circular linked list, we can insert elements anywhere in the list whereas in the array we cannot insert an element anywhere in the list because it is in the contiguous memory.
The circular linked list has a dynamic size which means the memory can be allocated when it is required.
