Circular Linked List-1

Question

Implementation of circular linked list

Answer 1

Ques . Write Implementation of Circular Linked list

Answer : 

Circular Linked List : Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list. It is a sequence of nodes arranged such a way that each node can be retraced to itself.In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required. In circular linked list there is no NULL part .

Example : 

Advantages of circular Linked list : 

1.  Circular Linked List,end node will points to first Node (doesn’t contain a NULL pointer)whereas in singly linked list it won’t point to first Node.
2.  Circular list is very useful in case of Game play,to give turns for each player without any failure (due to its circular connectivity).
3.  Circular Linked List can be Used for implementation of Queue.
4.  It saves time when we have to go to the first node from the last node. It can be done in single step because there is no need to traverse the in between nodes

Disadvantages of Circular Linked List :

1. Depending on implementation, inserting at start of list would require doing a search for the last node which could be expensive.
2.  It is not easy to reverse the linked list.
3. If proper care is not taken, then the problem of infinite loop can occur.
4. If we at a node and go back to the previous node, then we can not do it in single step. Instead we have to complete the entire circle by going through the in between nodes and then we will reach the required node.

Applications :

1. Implementation of stacks , queues
2. Implementation of graphs
3. Implementation of sparse matrix
4. Dynamic memory allocation 

Creating a circular node :

cll(value)     z = new node     z.value = data     z.next = z     c = new cll()     c.last = z     return c

Insertion after a given node : function which will take the new node 'n' and the node after which we are going to insert this node 'a'. The next of the new node will point to next of the node a i.e., n.next = a.next. After this, we will point next of the node a to the new node n - a.next = n.

insert_after(n, a)     n.next = a.next     a.next = n

Insertion at last : We will pass the linked list 'L' and the new node 'n' to the function -insert_at_last(L, n). We will simply insert the node by connecting the new node to the first node and the last node to the new node.n.next = L.last.next L . last.next = n At last, we will update the last pointer of the linked list i.e L.last = n

insert_at_last(L, n)     n.next = L.last.next     L.last.next = n     L.last = n

Deletion of the node : 

1. If there is only one node (if n.next == n), we are making it null - l.last = NULL.
2. if there are more than one node next pointer of the node previous to the node to be deleted to the next of it - temp.next = n.next. At last, we are updating the last pointer - l.last = temp.
3. When the node to be deleted is not the last node, then we don't have to update the last pointer. We will just connect the previous node to the next node of the node which we are going to delete, temp.next = n.next

delete(L, n)     temp = L.last     while temp.next != n         temp = temp.next     if n == L.last    #last node         if n.next == n    #only one node             L.last = NULL         else     #more than one node and last node             temp.next = n.next             L.last = temp    #updating last pointer     else     #not last node         temp.next = n.next

Program : 

class Node:   def __init__(self, value):     self.value = value     self.next = None class CircularLinkedList:   def __init__(self, value):     z = Node(value)     z.next = z     self.last = z def insert_after(n, a):   n.next = a.next   a.next = n def insert_at_last(l, n):   n.next = l.last.next   l.last.next = n   l.last = n def delete(l, n):   temp = l.last   while temp.next != n:     temp = temp.next   if n == l.last: #last node     if n.next == n: #only one node       l.last = NULL     else: #more than one node and last node       temp.next = n.next       l.last = temp #updating last pointer   else: #not last node     temp.next = n.next   del n def traversal(l):   temp = l.last   a = str(temp.value)+"\t"   temp = temp.next   while temp != l.last:     a = a + str(temp.value) + "\t"     temp = temp.next   print(a) l = CircularLinkedList(10) a = Node(20) b = Node(30) c = Node(40) l.last.next = a a.next = b b.next = c   c.next = l.last traversal(l) z = Node(50) insert_after(z, c) z = Node(25) insert_after(z, a) z = Node(100) insert_at_last(l, z) traversal(l) delete(l, l.last) delete(l, b) traversal(l)

Output : 

10 20 30 40

100 20 25 30 40 50 10

 10 20 25 40 50

---

For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments  CLICK HERE