0 like 0 dislike
477 views

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

## Ques . Write Implementation of Circular Linked list

Example : 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

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 Llast.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

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)

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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.  