Linked list:
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link.
Singly linked list :
* A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Basically ‘link’ field is nothing but address only.
*SLL has nodes with only a data field and next link field.
*In SLL, the traversal can be done using the next node link only.
*The SLL occupies less memory than DLL as it has only 2 fields.
*Less efficient access to elements.
We have another type in singly linked list i.e
DOUBLY LINKED LIST :
*This contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
- *DLL has nodes with a data field, a previous link field and a next link field.
*In DLL, the traversal can be done using the previous node link or the next node link.
*The DLL occupies more memory than SLL as it has 3 fields.
*More efficient access to elements.
There are two circular lists they are
- Circular singly linked Lists .
- Circular doubly linked Lists.
*Circular singly linked list:
-
In singly linked list, the next pointer of the last node points to the first node.
-
For accessing any node of linked list, we start traversing from the first node.
-
If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node.
-
This problem can be solved by slightly altering the structure of singly linked list.
-
In a singly linked list, next part (pointer to next node) is NULL, if we utilize this link to point to the first node then we can reach preceding nodes.
- we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.
Operations of circular singly linked list are:
- Insertion
- Deletion
- Display
Circular doubly linked list:
- Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. The first node of the list also contain address of the last node in its previous pointer.
-
The variable head contains the address of the first element of the list i.e. 1 hence the starting node of the list contains data A is stored at address 1.
-
Since, each node of the list is supposed to have three parts therefore, the starting node of the list contains address of the last node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at address 8 and containing data as 6, contains address of the first node of the list as shown in the image i.e. 1. In circular doubly linked list, the last node is identified by the address of the first node which is stored in the next part of the last node therefore the node which contains the address of the first node, is actually the last node of the list.
Operations in circular doubly linked list:
*Insertion
*deletion
*Insert Last
*Delete Last
*Insert After
*Delete
*Display forward
*Display backward
