|
Be the first user to complete this post
|
Add to List |
191. Circular Linked List Complete Implementation
Earlier we have seen what Singly Linked List is and How to implement it. In a way, you say that it's an extension of a singly linked list. I would suggest that if you do not about the Linked list, then I would recommend that you first read "Singly Linked List". Now we will see the difference between them.
So as we can see in the circular linked list the last node in the list is not pointing to null but it's pointing to the first node in the linked list and this makes a circle which is why it is called a "Circular Linked List".
Let's see how the Node structure will look like
class Node{
int data;
Node next;
public Node(int data){
this.data = data;
}
}
Operations:
NOTE: We are two references here, head and tail. Head points to the start of the linked list and tail points to the last node of the linked list.
Add at the Start: Add a node at the beginning of the linked list. Its O(1). If the size is 0 then make the new node as head and tail else put them at the start, change the head, and do not change the tail.
Add at the End: Add a node at the end of the linked list. It's O(1) since we have a tail reference. If the size is 0 then make the new node as head and tail else put the node at the end of the list using tail reference and make the new node as the tail.
Delete at the Start: Delete a node from the beginning of the linked list and make the head points to the 2nd node in the list. Its O(1).
Get Size: returns the size of the linked list.
Get Element at Index: Return the element at a specific index, if the index is greater than the size then return –1. its O(n) in worst case.
Print: Prints the entire linked list. O(n).
Output:
Adding node 3 at start Adding node 2 at start Adding node 1 at start Circular Linked List: 1 2 3 deleting node 1 from start Circular Linked List: 2 3 Node 4 is added at the end of the list Circular Linked List: 2 3 4 Size of linked list: 3 Element at 2nd position: 3