CIRCULAR LINKED LIST _

ok

1. Circular Linked List

2. CIRCULAR LINKED LISTS In a circular linked list, the last node contains a pointer to the first node of the list. We can have a circular singly linked list as well as a circular doubly linked list. While traversing a circular linked list, we can begin at any node and traverse the list in any direction, forward or backward, until we reach the same node where we started. Thus, a circular linked list has no beginning and no ending.

3. Types of Circular Linked Lists Circular Singly Linked List In Circular Singly Linked List , each node has just one pointer called the “ next ” pointer. The next pointer of last node points back to the first node and this results in forming a circle. In this type of Linked list we can only move through the list in one direction.

4. Types of Circular Linked Lists 2. Circular Doubly Linked List: In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer points to the previous node and the next points to the next node. Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node .

5. OPERATIONS ON CIRCULAR LINKED LIST INSERTION(ON BEGINNING,END AND AT SPECIFIC LOCATION) DELETION(FROM BEGINNING,END AND SPECIFIC LOCATION) TRAVERSAL

6. Inserting a Node at the Beginning of a Circular Linked List Algorithm F ollowing steps to insert a new node at beginning of the circular linked list... Step 1 -  Create a  newNode  with given value. Step 2 -  Check whether list is  Empty   i.e head  ==  NULL Step 3 -  If it is  Empty  then, set  head  =  newNode  and  newNode→next  =  head  . Step 4 -  If it is  Not Empty  then, define a Node pointer ‘ ptr ' and initialize with ' head '. Step 5 -  Keep moving the ‘ ptr ' to its next node until it reaches to the last node (until ‘ ptr → next  ==  head '). Step 6 -  Set ' newNode → next  = head ', ' head  =  newNode ' and ‘ ptr → next  =  head ' Code void insertAtBeginning ( int value) { struct Node * newNode ; newNode = ( struct Node*) malloc ( sizeof ( struct Node)); newNode -> data = value; if(head == NULL) { head = newNode ; newNode -> next = head; } else { struct Node * ptr = head; while( ptr -> next != head) ptr = ptr -> next; newNode -> next = head; head = newNode ; ptr -> next = head; } printf ("\ nInsertion success !!!");}

7. Inserting a new node at the beginning of circular Linked List

8. Inserting a Node at the End of a Circular Linked List Algorithm following steps to insert a new node at end of the circular linked list... Step 1 -  Create a  newNode  with given value. Step 2 -  Check whether list is  Empty  ( head  ==  NULL ). Step 3 -  If it is  Empty  then, set  head  =  newNode  and  newNode → next  =  head . Step 4 -  If it is  Not Empty  then, define a node pointer ptr  and initialize with  head . Step 5 -  Keep moving the  ptr  to its next node until it reaches to the last node in the list (until  ptr → next  ==  head ). Step 6 -  Set  ptr → next  =  newNode  and  newNode → next  =  head . Code void insertAtEnd ( int value) { struct Node * newNode ; newNode = ( struct Node*) malloc ( sizeof ( struct Node)); newNode -> data = value; if(head == NULL) { head = newNode ; newNode -> next = head; } else { struct Node * ptr = head; while( ptr -> next != head) ptr = ptr -> next; ptr -> next = newNode ; newNode -> next = head; } printf ("\ nInsertion success!!!"); }

9. Inserting a new node at the end in circular Linked List

10. Deleting a Node from the Beginning of a Circular Linked List Algorithm   Use following steps to delete a node from beginning of the circular linked list... Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 3 -  If it is  Not Empty  then, define pointer ptr and initialize with  head . Step 4 -  Check whether list is having only one node ( ptr → next  ==  head ) Step 5 -  If it is  TRUE  then set  head  =  NULL  and delete  ptr  (Setting  Empty  list conditions) Step 6 -  If it is  FALSE  move the  ptr  until it reaches to the last node. (until  ptr → next  ==  head  ) Step 7 -  Then set temp=head,  head  =  head-> next , ptr → next = head  and delete  temp Code void deleteBeginning () { if(head == NULL) printf ("List is Empty!!! Deletion not possible!!!"); else { struct Node * temp,* ptr = head; if(temp -> next == head) { head = NULL; free(temp); } else { head = head -> next ; while( ptr ->next!=head) ptr = ptr ->next; ptr ->next=head; free(temp); } printf ("\ nDeletion success!!!"); }}

11. Deleting the First Node from a Circular Linked List temp temp

12. Deleting a Node from the end of a Circular Linked List Algorithm Use the following steps to delete a node from end of the circular linked list... Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 3 -  If it is  Not Empty  then, define two Node pointers  ‘ preptr '  and ‘ ptr '  and initialize ‘ ptr ' with  head . Step 4 -  Check whether list has only one Node ( ptr → next  ==  head ) Step 5 -  If it is  TRUE . Then, set  head  =  NULL  and delete  ptr . And terminate from the function. (Setting  Empty  list condition) Step 6 -  If it is  FALSE . Then, set ‘ preptr = ptr   ' and move  ptr to its next node. Repeat the same until  ptr reaches to the last node in the list. (until  ptr → next  ==  head ) Step 7 -  Set  preptr → next  =  head  and delete  ptr . Code void deleteEnd () { if(head == NULL) printf ("List is Empty!!! Deletion not possible!!!"); else { struct Node * ptr = head, preptr ; if( ptr -> next == head) { head = NULL; free(temp1); } else{ while( ptr -> next != head){ preptr = ptr ; ptr = ptr -> next; } preptr -> next = head; free( ptr ); } printf ("\ nDeletion success!!!"); }}

13. Deleting the Last Node from a Circular Linked List

14. Applications of linked lists Polynomial representation Let us see how a polynomial is represented in the memory using a linked list. Consider a polynomial 6x3 + 9x2 + 7x + 1. Every individual term in a polynomial consists of two parts, a coefficient and a power. Here, 6, 9, 7, and 1 are the coefficients of the terms that have 3, 2, 1, and 0 as their powers respectively. Every term of a polynomial can be represented as a node of the linked list.

15. Generalized Linked List A Generalized Linked List L, is defined as a finite sequence of n>=0 elements, l 1 , l 2 , l 3 , l 4 , …, l n , such that l i are either item or the list of items. Thus L = (l 1 , l 2 , l 3 , l 4 , …, l n ) where n is total number of nodes in the list. To represent a list of items there are certain assumptions about the node structure. Flag = 1 implies that down pointer exists Flag = 0 implies that next pointer exists Data means the item. Down pointer is the address of node which is down of the current node Next pointer is the address of node which is attached as the next node

16. Why Generalized Linked List? Generalized linked lists are used because although the efficiency of polynomial operations using linked list is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equation efficiently. It helps us to represent multi-variable polynomial along with the list of elements.  typedef struct node { char c; //Data int index; //Flag struct node *next, *down; //Next & Down pointer }GLL;

17. Thanks