Linked List
Circular Singly Linked List :
In a Circular Singly Linked List, the last node of the list contains a pointer to the first note of the list. We can have a circular singly linked list as well as a double linked list.
We traverse a circular singly linked list until we reach the same node where we started. The circular singly linked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.
Circular Linked List is mostly used in task maintenance in operating systems. There are many examples where circular linked list is being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again in clicking the previous button.
Doubly Linked List :
A Doubly Linked List ( DLL ) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
Double linked list advantages over singly linked list :
- A DLL can be traversed in both forward and backward direction.
- The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
- We can quickly inner a new node before a given node. In singly linked list, to delete a node, pointer to the previous node is needed. To get this pervious node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.
Disadvantages over singly linked list :
- Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though.
- All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.
Insertion :
A node can be added in four ways :
- At the front of the DLL
- After a given node
- At the end of the DLL
- Before a given node.
Deletion :
There are 4 conditions we should pay attention when deleting :
- The node to be deleted is the only node in linked list.
- The node to be deleted is head
- The node to be deleted is tail.
- The node to be deleted is not head or tail.
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 code. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contain the address of the first node of the list. The first ndoe of the list also contain address of the last node in its previous pointer.
Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.
Source :
