Linked list:
It is basically a chain of nodes.
These nodes are randomly stored in memory.
Each node contains two fields, i.e., the data stored at that particular address and the pointer, which contains the address of the next node in the memory.
The last node of the list contains a pointer to the null.
Why is link list used:
Dynamic Data Structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.
Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needs to be updated.
Efficient Memory Utilization: As we know, Linked List is a dynamic data structure; the size increases or decreases as per the requirement, so this avoids the wastage of memory.
Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.
Types of link list:
Singly Link List:
Also called a one-way chain.
A node in the singly linked list consists of two parts: the data part and the link part.
The data part of the node stores the actual information that is to be represented by the node.
The link part of the node stores the address of its immediate successor.
Double Link List:
A doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence.
A node consists of three parts: node data, a pointer to the next node in sequence, and a pointer to the previous node.
The pointer to the next node contains the address of the next pointer.
The pointer to the previous node contains the address of the previous pointer.
Circular Link list
Singly Circular Linked List
Doubly Circular Linked List
Singly Link List:
Each node contains only the next pointer; therefore, we cannot traverse the list in the reverse direction.
Operations on a Single-Linked List
Creation of a node:
A new node is created in which our data is stored.
Each node is created in such a way that we can store our data along with the address on the next node.
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
Insertion:
There are 3 types of insertion:
Insertion in the beginning.
It involves inserting any element at the front of the list. We just need to make a few link adjustments to make the new node the head of the list.
Insertion at the end.
It involves insertion at the end of the linked list. The new node can be inserted as the only node in the list, or it can be inserted as the last one. Different logics are implemented in each scenario.
Insertion at any index.
It involves insertion after the specified node of the linked list. We need to skip the desired number of nodes in order to reach the node after which the new node will be inserted.
Deletion:
These are also of three types:
Deletion at the beginning:
- It involves the deletion of a node from the beginning of the list. This is the simplest operation of all. It just needs a few adjustments to the node pointers.
Deletion at the end of the list:
- It involves deleting the last node of the list. The list can either be empty or full. Different logic is implemented for the different scenarios.
Deletion at any index
It involves deleting the node after the specified node in the list.
We need to skip the desired number of nodes to reach the node, after which the node will be deleted. This requires traversing through the list.