Linked List
A linked list is a linear data structure in which elements are stored in a series of nodes, where each node contains a value or data and a reference (or pointer) to the next node in the sequence. The first node is known as head node, and the last node is known as the tail node.
Unlike arrays, linked list do not store elements in contiguous memory locations, and the size of the list can change dynamically during the execution of a program. This makes linked lists ideal for situations where the size of the data set is not known in advance or when elements need to be inserted or removed frequently.
Types of Linked List
- Single linked list
- Circular linked list
- Doubly linked list
- Doubly Circular linked list
Singly linked list:-
A singly linked list is a type of linked list data structure in which each node has a data element and a reference (or pointer) to the next node in the list. The last node in the list points to a null value, indicating the end of the list.
In singly linked list, traversal can only be done in one direction, from the head (the first node) to the tail (the last node). Insertion and deletion operations can be performed easily by changing the references of the nodes.
Circular linked list:-
A circular linked list is a type of linked list in which the last node in the list points back to the first node, forming a circular structure. This means that the next pointer of the last node points to the first node in the list, instead of null as in a traditional linked list.
Doubly linked list:-
A doubly linked list is a type of linked list data structure in which each node has a data element and two references (or pointers), one to the next node in the list and another to the previous node in the list. This allows for bidirectional traversal of the list, from the head to the tail and vice versa.
Doubly Circular linked list:-
A doubly circular linked list is a type of linked list data structure in which the last node in the list is connected to the first node, forming a circle. Each node has a data element and two references (or pointers), one to the next node in the list and another to the previous node in the list. This allows for bidirectional traversal of the list, from the head to the tail and vice versa, as well as circular traversal, where the tail node points back to the head node
What are various operations performed on doubly linked list discuss with example.
The various operations that can be performed on a double linked list are as follows:
- Insertion: Nodes can be inserted at the beginning, end, or at any given position in the list. To insert a node at a given position, we need to traverse the list until we reach the desired position, then update the pointers of the previous and next nodes to include the new node. For example, suppose we have a list with nodes A, B, and C, and we want to insert a node D after node B. We would update the pointers of node B and C to include node D, as follows:
- Deletion: Nodes can be deleted from the list by updating the pointers of the previous and next nodes to bypass the node being deleted. For example, suppose we have a list with nodes A, B, C, and D, and we want to delete node C. We would update the pointers of node B and D to bypass node C, as follows:
- Traversal: Nodes can be traversed in both directions by following the pointers of each node. This allows for efficient searching and manipulation of the data elements in the list. For example, to traverse the list from the beginning to the end, we would start at the first node and follow the next pointers until we reach the last node.
- Searching: Nodes can be searched by traversing the list and comparing the data elements of each node with the target value. For example, suppose we have a list with nodes A, B, C, and D, and we want to find the node with data element “B”. We would traverse the list and compare the data elements of each node until we find the node with data element “B”.
