Module-2 (DS).pdf

UNIT - 2 Linked List: A linked list is a linear collection of elements called nodes. Each node consists two parts – the data part pointer part (pointer part stores the address of next node). Linked list is a dynamic data structure. The data items in...

UNIT - 2 Linked List: A linked list is a linear collection of elements called nodes. Each node consists two parts – the data part pointer part (pointer part stores the address of next node). Linked list is a dynamic data structure. The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item. Advantages of linked lists: Linked lists have many advantages. Some of the very important advantages are: 1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program. 2. Linked lists have efficient memory utilization. Here, memory is not pre-allocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed. 3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position. 4. Many complex applications can be easily carried out with linked lists. Disadvantages of linked lists: 1. It consumes more space because every node requires a additional pointer to store address of the next node. 2. Searching a particular element in list is difficult and also time consuming. Types of Linked Lists: 1. Single Linked List. 2. Double Linked List. 3. Circular Linked List. A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is also called as linear linked list. A double linked list is one in which all nodes are linked together by multiple links which helps in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list. Therefore each node in a double linked list has two link fields (pointers) to point to the left node (previous) and the right node (next). This helps to traverse in forward direction and backward direction.  A circular linked list is one, which has no beginning and no end. A single linked list can be made a circular linked list by simply storing address of the very first node in the link field of the last node. A circular double linked list is one, which has both the successor pointer and predecessor pointer in the circular manner. Applications of linked list: 1. Linked lists are used to represent and manipulate polynomial. Polynomials are expression containing terms with non zero coefficient and exponents. For example: P(x) = a0 Xn + a1 Xn-1 + …… + an-1 X + an 2. Represent very large numbers and operations of the large number such as addition, multiplication and division. 3. Linked lists are to implement stack, queue, trees and graphs. 4. Implement the symbol table in compiler construction Single Linked List: A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is also called as linear linked list. A linked list allocates space for each element separately in its own block of memory called a "node". Each node contains two fields; a "data" field to store whatever element, and a "next" field which is a pointer used to link to the next node. Each node is allocated in the heap using malloc(), so the node memory continues to exist until it is explicitly de-allocated using free(). The front of the list is a pointer, which is called “start” node. In single linked list, the beginning of the linked list is stored in a "start" pointer which points to the first node. The first node contains a pointer to the second node. The second node contains a pointer to the third node,... and so on. The last node in the list has its next field set to NULL to mark the end of the list. Code can access any node in the list by starting at the start and following the next pointers. The start pointer is an ordinary local pointer variable, so it is drawn separately on the left top to show that it is in the stack. The list nodes are drawn on the right to show that they are allocated in the heap. Implementation of Single Linked List: Node structure: Each node contains two fields; a "data" field to store data, and a "next" field which is a pointer used to store the address of next node.  Creating a structure with one data item and a next pointer, which will be pointing to next node of the list. This is called as self-referential structure.  Initialise the start pointer to be NULL. struct node { int data; struct node *next;  }; typedef struct node node; node *start = NULL; Operations on linked lists: The basic operations in a single linked list are: 1. Creation. 2. Insertion. 3. Deletion. 4. Traversing. 1. Creating a node for Single Linked List: Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for creating a node. The information is stored in the memory, allocated by using the malloc() function. The function getnode(), is used for creating a node, after allocating memory for the structure of type node, the information for the item (i.e., data) has to be read from the user, set next field to NULL and finally returns the address of the node. node* getnode() { node * newnode; newnode = (node *) malloc(sizeof(node)); printf("\n Enter data: "); scanf("%d", &newnode -> data); newnode -> next = NULL; return newnode; } Creating a Single Linked List with ‘n’ number of nodes: The following steps are to be followed to create ‘n’ number of nodes: 1. Get the new node using getnode(). newnode = getnode(); 2. If the list is empty, assign new node as start. start = newnode; 3. If the list is not empty, follow the steps given below: a. The next field of the new node is made to point the first node (i.e. start node) in the list by assigning the address of the first node. b. The start pointer is made to point the new node by assigning the address of the new node.  4. Repeat the above steps ‘n’ times. Single Linked List with 4 nodes The function createlist(), is used to create ‘n’ number of nodes: vo id createlist( int n) { int i; node * newnode; node *temp; for( i = 0; i < n ; i++) { newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } } } Insertion of a Node: The new node can then be inserted at three different places namely: a. Inserting a node at the beginning. b. Inserting a node at the end. c. Inserting a node at intermediate position. Inserting a node at the beginning: The following steps are to be followed to insert a new node at the beginning of the list: 1. Get the new node using getnode(). newnode = getnode(); 2. If the list is empty then start = newnode. 3. If the list is not empty, follow the steps given below:  newnode -> next = start; start = newnode; The function insert_beg(), is used for inserting a node at the beginning void insert_beg() { node *newnode; newnode = getnode(); if(start == NULL) { start = newnode; } else { newnode -> next = start; start = newnode; } } Inserting a node at the end: The following steps are followed to insert a new node at the end of the list: 1. Get the new node using getnode() newnode = getnode(); 2. If the list is empty then start = newnode. 3. If the list is not empty follow the steps given below: temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; The function insert_end(), is used for inserting a node at the end. void insert_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } } Inserting a node at intermediate position: The following steps are followed, to insert a new node in an intermediate position in the list: 1. Get the new node using getnode(). newnode = getnode(); 2. Read the position ‘pos’ 3. Store the starting address (which is in start pointer) in temp pointer. Then traverse the temp pointer upto the specified position. temp =start; for(i=1; i next; } 4. After reaching the specified position, follow the steps given below: newnode -> next = temp -> next; temp -> next = newnode; Let the intermediate position be 3. The function insert_mid(), is used for inserting a node in the intermediate position. void insert_mid() { node *newnode, *temp; int i, pos; newnode=getnode(); printf(“ enter the position \n”); scanf(“%d”, &pos); if(start == NULL) { start = newnode; } else { temp =start; for(i=1; i next; } newnode -> next = temp -> next; temp -> next = newnode; } } Deletion of a node: Another primitive operation that can be done in a single linked list is the deletion of a node. Memory is to be released for the node to be deleted. A node can be deleted from the list from three different places namely. a. Deleting a node at the beginning. b. Deleting a node at the end. c. Deleting a node at intermediate position. Deleting a node at the beginning: The following steps are followed, to delete a node at the beginning of the list: 1. If list is empty then display ‘Empty List’ message. IF start == NULL THEN printf("\n Empty List’.."); 2. If the list is not empty, follow the steps given below: temp = start; start = start -> next; free(temp); The function delete_beg(), is used for deleting the first node in the list. void delete_beg() { node *temp; if(start == NULL) { printf("\n No nodes are exist.."); } else { temp = start; start = temp -> next; free(temp); printf("\n Node deleted "); } } Deleting a node at the end: The following steps are followed to delete a node at the end of the list: 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: temp = prev = start; while(temp -> next != NULL) { prev=temp; temp = temp -> next; } prev -> next = NULL; free(temp); The function delete_end(), is used for deleting the last node in the list. void delete_end() { node *temp, *prev; if(start == NULL) { printf("\n Empty List.."); }  else { temp = start; prev = start; while(temp -> next != NULL) { prev = temp; temp = temp -> next; } prev -> next = NULL; free(temp); printf("\n Node deleted "); } } Deleting a node at Intermediate position: The following steps are followed, to delete a node from an intermediate position in the list (List must contain more than two node). 1. 2. If list is empty then display ‘Empty List’ message 3. If the list is not empty, follow the steps given below. for(i=1;i next; } prev -> next = temp -> next; free(temp); printf("\n Node deleted.."); The function delete_mid(), is used for deleting the intermediate node in the list. void delete_mid() { int i, pos; node *temp, *prev; if(start == NULL) { printf("\n Empty List.."); return ; } else { printf("\n Enter position of node to delete: ");  scanf("%d", &pos); temp = prev = start; for(i=1;i next; } prev -> next = temp -> next; free(temp); printf("\n Node deleted.."); } } Traversal and displaying a list (Left to Right): To display the information, you have to traverse (move) a linked list, node by node from the first node, until the end of the list is reached. Traversing a list involves the following steps:  Assign the address of start pointer to a temp pointer.  Display the information from the data field of each node. The function traverse() is used for traversing and displaying the information stored in the list from left to right. void traverse() { node *temp; temp = start; printf("\n The contents of List (Left to Right): \n"); if(start == NULL ) printf("\n Empty List"); else { while (temp != NULL) { printf("%d ->", temp -> data); temp = temp -> next; } } } Counting the Number of Nodes: The following code will count the number of nodes exist in the list using recursion. void countnode() { int count=0; node *temp; temp=start; while(temp != NULL)  { count++; temp =temp -> next; } printf(“Number of nodes in Single Linked List = %d \n”, count); } SEARCH for an element in the linked list: Algorithm or procedure: Searching() Step1: start Step2: create list of elements in single linked list. Step3: read the ‘element’ that do you want to search Step4: set count=0, pos=0 Step5: searching for element in the list temp=start; while(temp != NULL) { pos++; if(temp->data= =element) { count++; break; } temp =temp -> next; } Step6: if count = =0 then print “element not found” Else print “ element found in the list at ‘pos’” void searching() { int element, pos=0,count=0; node *temp; temp=start; printf(“enter data do you want to search \n”); scanf(“%d”,&element); while(temp != NULL) { pos++; if(temp->data= =element) { count++; break;  } temp =temp -> next; } if (count = = 0) printf(“ given element NOT FOUND \n”); else printf(“ given element found in the list at position =%d \n”,pos); } Output: create list of elements in single linked list. 10 ->20 -> 30 -> 40 -> 50 read the ‘element’ that do you want to search element =30 given element found in the list at position =3 \n”, Double Linked List: A double linked list is a two-way list in which all nodes will have two links. This helps in accessing both successor node and predecessor node from the given node position. It provides bi-directional traversing. Each node contains three fields:  Left link.  Data.  Right link. The left link points to the predecessor node and the right link points to the successor node. The data field stores the required data. Many applications require searching forward and backward through nodes of a list. For example searching for a name in a telephone directory would need forward and backward scanning through a region of the whole list. The basic operations in a double linked list are:  Creation.  Insertion.  Deletion.  Traversing. A double linked list is shown in figure The beginning of the double linked list is stored in a "start" pointer which points to the first node. The first node’s left link and last node’s right link is set to NULL. The following code gives the structure definition of node in double linked list: Struct node { struct node *left; int data; struct node *right; }; typedef struct node node; node *start = NULL; Creating a node for Double Linked List: Creating a double linked list starts with creating a node. Sufficient memory has to be allocated for creating a node. The memory is allocated by using the malloc() function. After allocating memory for the node, the data has to be read from the user and set left field to NULL and right field also set to NULL. Creating a Double Linked List with ‘n’ number of nodes: The following steps are to be followed to create ‘n’ number of nodes: 1. Get the new node using getnode(). newnode =getnode(); 2. If the list is empty then start = newnode. 3. If the list is not empty, follow the steps given below: The left field of the new node is made to point the previous node. The previous nodes right field must be assigned with address of the new node. 4. Repeat the above steps ‘n’ times. The function createlist(), is used to create ‘n’ number of nodes: vo id createlist( int n) { int i; node * newnode; node *temp; for( i = 0; i < n; i++) { newnode = getnode(); if(start == NULL) { start = newno de; } else { temp = start; while(temp -> right) temp = temp -> right; temp -> right = newnode; newnode -> left = temp; } } } Figure shows 3 items in a double linked list stored at different locations. Inserting a node at the beginning: The following steps are to be followed to insert a new node at the beginning of the list: 1. Get the new node using getnode(). newnode=getnode(); 2. If the list is empty then start = newnode. 3. If the list is not empty, follow the steps given below: newnode -> right = start;  start -> left = newnode; start = newnode; Figure shows inserting a node into the double linked list at the beginning. void dll_insert_beg() { node *newnode; newnode = getnode(); if(start == NULL) start = newnode; else { newnode -> right = start; start -> left = newnode; start = newnode; } } Inserting a node at the end: The following steps are followed to insert a new node at the end of the list: 1. Get the new node using getnode() newnode=getnode(); 2. If the list is empty then start = newnode. 3. If the list is not empty follow the steps given below: temp = start; while(temp -> right != NULL) temp = temp -> right; temp -> right = newnode; newnode -> left = temp; Figure shows inserting a node into the double linked list at the end. void dll_insert_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL) start = newnode; else { temp = start; while(temp -> right != NULL) { temp = temp -> right; } temp -> right = newnode; newnode -> left = temp; } } Inserting a node at an intermediate position: The following steps are followed, to insert a new node in an intermediate position in the list: 1. Get the new node using getnode(). newnode=getnode(); 2. Read the position at which do you want to insert. ‘Pos’ 3. Store the starting address (which is in start pointer) in ‘temp’ and ‘prev’ pointers. temp=start; prev=start; 4. Traverse the temp pointer upto the specified position followed by prev pointer. 5. After reaching the specified position, follow the steps given below: newnode -> left = temp; newnode -> right = temp -> right; temp -> right -> left = newnode; temp -> right = newnode; Figure shows inserting a node into the double linked list at a specified intermediate position other than beginning and end. void dll_insert_mid() { node *newnode,*temp,*prev;  int pos,i; newnode = getnode(); printf("\n Enter the position: "); scanf("%d", &pos); temp = start; for(i=1;i< pos;i++ ) { prev=temp; temp = temp -> right; } newnode -> left = prev; newnode -> right = temp ; temp -> left = newnode; prev -> right = newnode; } Deleting a node at the beginning: The following steps are followed, to delete a node at the beginning of the list: 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: temp = start; start = start -> right; start -> left = NULL; free(temp); Figure shows deleting a node at the beginning of a double linked list. void dll_delete_beg() { node *temp; if(start == NULL) { printf("\n Empty list"); } else { temp = start; start = start -> right; start -> left = NULL; free(temp); } } Deleting a node at the end: The following steps are followed to delete a node at the end of the list: 1. If list is empty then display ‘Empty List’ message 2. If the list is not empty, follow the steps given below: temp = start; while(temp -> right != NULL) { temp = temp -> right; } temp -> left -> right = NULL; free(temp); Figure shows deleting a node at the end of a double linked list. void dll_delete_last() { node *temp,*prev; if(start == NULL) { printf("\n Empty list"); } else { temp = start; while(temp -> right != NULL) { prev=temp; temp = temp -> right; } prev -> right = NULL; free(temp); temp = NULL; } } Deleting a node at Intermediate position: The following steps are followed, to delete a node from an intermediate position in the list (List must contain more than two nodes). 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: 3. Get the position of the node to delete. 4. Then perform the following steps:  temp=start; prev=start; foe(i=1;i right; } prev -> right = temp -> right; temp -> right -> left = prev; free(temp); printf("\n node deleted.."); Figure shows deleting a node at a specified intermediate position other than beginning and end from a double linked list. void dll_delete_mid() { int i , pos; node *temp; if(start == NULL) { printf("\n Empty List"); } else { printf("\n Enter the position of the node to delete: "); scanf("%d", &pos); temp=start; prev=start; for(i=1;i right; } prev -> right = temp -> right; temp -> right -> left = prev; free(temp); printf("\n node deleted.."); } } Traversal and displaying a list (Left to Right): To display the information, you have to traverse the list, node by node from the first node, until the end of the list is reached. The function traverse_left_right() is used for traversing and displaying the information stored in the list from left to right. The following steps are followed, to traverse a list from left to right: 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: temp = start; while(temp != NULL) { Print temp-> data; temp = temp -> right; } Program: void traverse_forward() { node *temp; temp = start; printf("\n The contents of List: "); if(start == NULL ) printf("\n Empty List"); else { while(temp != NULL) { printf("\t %d ", temp -> data); temp = temp -> right; } } } Traversal and displaying a list (Right to Left): To display the information from right to left, you have to traverse the list, node by node from the first node, until the end of the list is reached. The function traverse_right_left() is used for traversing and displaying the information stored in the list from right to left. The following steps are followed, to traverse a list from right to left: 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: temp = start; while(temp -> right != NULL) temp = temp -> right; while(temp != NULL) { print temp -> data; temp = temp -> left; } void traverse_reverse() { node *temp; temp = start; printf("\n The contents of List: "); if(start == NULL) printf("\n Empty List"); else { while(temp -> right != NULL) temp = temp -> right; } while(temp != NULL) { printf("\t%d", temp -> data); temp = temp -> left; } } COUNT Number of nodes in the DOUBLE LINKED LIST: void COUNT() { int count=0; node *temp; temp = start; while(temp != NULL) { count=count+1; temp = temp -> right; } printf(“Number of nodes in Double Linked List = %d \n”, count); } Circular Single Linked List: A circular linked list is very similar to the single linked list (linear list) where in the circular list the pointer of the last node points to the address of first node. Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. A circular linked list has no beginning and no end. It is necessary to establish a special pointer called start pointer always pointing to the first node of the list. In circular linked list no null pointers are used, hence all pointers contain valid address. A circular single linked list is shown in figure Advantages of Circular Linked Lists: 1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again. 2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last. 3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list. 4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci heap.. The basic operations in a circular single linked list are:  Creation.  Insertion.  Deletion.  Traversing. Creating a circular single Linked List with ‘n’ number of nodes: The following steps are to be followed to create ‘n’ number of nodes: 1. Get the new node using getnode(). newnode = getnode(); 2. If the list is empty, assign new node as start. start = newnode; 3. If the list is not empty, follow the steps given below: temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; 4. Repeat the above steps ‘n’ times. 5. newnode -> next = start; The function createlist(), is used to create ‘n’ number of nodes: Inserting a node at the beginning: The following steps are to be followed to insert a new node at the beginning of the circular list: 1. Get the new node using getnode(). newnode = getnode(); 2. If the list is empty, assign new node as start. start = newnode; newnode -> next = start; 3. If the list is not empty, follow the steps given below: temp = start; while(temp -> next != start) temp= temp -> next; newnode -> next = start; start = newnode; temp -> next = start; Figure shows inserting a node into the circular single linked list at the beginning. void cll_insert_beg() { node *newnode, *temp; newnode = getnode(); if(start == NULL) { start = newnode; newnode -> next = start; } else { temp = start; while(temp -> next != start) temp= temp -> next; newnode -> next = start; start = newnode; temp -> next = start; } Inserting a node at the end: The following steps are followed to insert a new node at the end of the list: 1. Get the new node using getnode(). newnode = getnode();  2. If the list is empty, assign new node as start. start = newnode; newnode -> next = start; 3. If the list is not empty follow the steps given below: temp = start; while(temp -> next != start) temp = temp -> next; temp -> next = newnode; newnode -> next = start; Figure shows inserting a node into the circular single linked list at the end. void cll_insert_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL ) { start = newnode; newnode -> next = start; } else { temp = start; while(temp -> next != start) temp = temp -> next; temp -> next = newnode; newnode -> next = start; } Insert node at position: The following steps are followed, to insert a new node in an intermediate position in the list: 1. Get the new node using getnode(). newnode = getnode(); 2. Read the position ‘pos’  3. Store the starting address (which is in start pointer) in temp pointer. Then traverse the temp pointer upto the specified position. temp =start; for(i=1; i next; } 4. After reaching the specified position, follow the steps given below: newnode -> next = temp -> next; temp -> next = newnode; The function insert_mid(), is used for inserting a node in the intermediate position. void insert_mid() { node *newnode, *temp; int i, pos; newnode=getnode(); printf(“ enter the position \n”); scanf(“%d”, &pos); if(start == NULL) { start = newnode; } else { temp =start; for(i=1; i next; } newnode -> next = temp -> next; temp -> next = newnode; } } Deleting a node at the beginning: The following steps are followed, to delete a node at the beginning of the list: 1. If the list is empty, display a message ‘Empty List’. 2. If the list is not empty, follow the steps given below: last = temp = start; while(last -> next != start)  { last= last -> next; } start = start -> next; last -> next = start; free(temp) 3. After deleting the node, if the list is empty then start = NULL. [before deleting check if(start->next==NULL) that is list contains only one node. And after deleting that node list becomes empty. That is start =NULL] Figure shows deleting a node at the beginning of a circular single linked list. void cll_delete_beg() { node *temp, *last; if(start == NULL) { printf("\n No nodes exist.."); } else { last = temp = start; while(last -> next != start) last= last -> next; start = start -> next; last -> next = start; free(temp); } } Deleting a node at the end: The following steps are followed to delete a node at the end of the list: 1. If the list is empty, display a message ‘Empty List’. 2. If the list is not empty, follow the steps given below: temp = start; prev = start; while(temp -> next != start) { prev=temp; temp = temp -> next; }  prev -> next = start; 3. After deleting the node, if the list is empty then start = NULL. Figure shows deleting a node at the end of a circular single linked list. void cll_delete_last() { node *temp, *prev; if(start == NULL) { printf("\n No nodes exist.."); } else { temp = start; prev = start; while(temp -> next != start) { prev = temp; temp = temp -> next; } prev -> next = start; free(temp); } Deleting node at middle: Deleting a node at Intermediate position: The following steps are followed, to delete a node from an intermediate position in the list (List must contain more than two node). 1. If list is empty then display ‘Empty List’ message 2. If the list is not empty, follow the steps given below. for(i=1;i next; } prev -> next = temp -> next; free(temp); printf("\n Node deleted.."); The function delete_mid(), is used for deleting the intermediate node in the list. void delete_mid() { int i, pos; node *temp, *prev; if(start == NULL) { printf("\n Empty List.."); return ; } else { printf("\n Enter position of node to delete: "); scanf("%d", &pos); temp = prev = start; for(i=1;i next; } prev -> next = temp -> next; free(temp); printf("\n Node deleted.."); } } Traversing a circular single linked list from left to right: The following steps are followed, to traverse a list from left to right: 1. If list is empty then display ‘Empty List’ message. 2. If the list is not empty, follow the steps given below: temp = start; do { printf("%d", temp -> data); temp = temp -> next; } while(temp != start); void display() { node *temp; temp = start; printf("\n The contents of List (Left to Right): "); if(start == NULL ) printf("\n Empty List"); else { while(temp != start); { printf("\t %d ", temp -> data);  temp = temp -> next; } } } COUNT Number of Nodes in the circular linked list: void display() { node *temp; int count=0; temp = start; printf("\n The contents of List (Left to Right): "); if(start == NULL ) printf("\n Empty List"); count=0; else { while(temp != start); { count=count+1; temp = temp -> next; } printf(Number of Nodes in circular linked list = %d \n “, count); } } Source Code for the Implementation of Single Linked List: # include # include # include struct node { int data; struct node *next; }; node *start = NULL; int menu() { int ch; printf("\n 1.Create a list "); printf("\n--------------------------"); printf("\n 2.Insert a node at beginning "); printf("\n 3.Insert a node at end"); printf("\n 4.Insert a node at middle"); printf("\n--------------------------"); printf("\n 5.Delete a node from beginning"); printf("\n 6.Delete a node from Last"); printf("\n 7.Delete a node from Middle"); printf("\n--------------------------"); printf("\n 8.Traverse the list (Left to Right)"); printf("\n 9.Traverse the list (Right to Left)"); printf("\n--------------------------"); printf("\n 10. Count nodes "); printf("\n 11. Exit "); printf("\n\n Enter your choice: "); scanf("%d",&ch); return ch; } node* getnode() { node * newnode; newnode = (node *) malloc(sizeof(node)); printf("\n Enter data: "); scanf("%d", &newnode -> data); newnode -> next = NULL; return newnode; } int countnode(node *ptr) { int count=0;  while(ptr != NULL) { count++; ptr = ptr -> next; } return (count); } void createlist(int n) { int i; node *newnode; node *temp; for(i = 0; i < n; i++) { newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } } } void traverse() { node *temp; temp = start; printf("\n The contents of List (Left to Right): \n"); if(start == NULL) { printf("\n Empty List"); return; } else { while(temp != NULL) { printf("%d-->", temp -> data); temp = temp -> next; } } printf(" X "); } void rev_traverse(node *start) { if(start == NULL) { return;  } else { rev_traverse(start -> next); printf("%d -->", start -> data); } } void insert_at_beg() { node *newnode; newnode = getnode(); if(start == NULL) { start = newnode; } else { newnode -> next = start; start = newnode; } } void insert_at_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } } void insert_at_mid() { node *newnode, *temp, *prev; int pos, nodectr, ctr = 1; newnode = getnode(); printf("\n Enter the position: "); scanf("%d", &pos); nodectr = countnode(start); if(pos > 1 && pos < nodectr) { temp = prev = start; while(ctr < pos) { prev = temp; temp = temp -> next;  ctr++; } prev -> next = newnode; newnode -> next = temp; } else printf("position %d is not a middle position", pos); } void delete_at_beg() { node *temp; if(start == NULL) { printf("\n No nodes are exist.."); return ; } else { temp = start; start = temp -> next; free(temp); printf("\n Node deleted "); } } void delete_at_last() { node *temp, *prev; if(start == NULL) { printf("\n Empty List.."); return ; } else { temp = start; prev = start; while(temp -> next != NULL) { prev = temp; temp = temp -> next; } prev -> next = NULL; free(temp); printf("\n Node deleted "); } } void delete_at_mid() { int ctr = 1, pos, nodectr; node *temp, *prev; if(start == NULL) { printf("\n Empty List..");  return ; } else { printf("\n Enter position of node to delete: "); scanf("%d", &pos); nodectr = countnode(start); if(pos > nodectr) { printf("\nThisnode doesnot exist"); } if(pos > 1 && pos < nodectr) { temp = prev = start; while(ctr < pos) { prev = temp; temp = temp -> next; ctr ++; } prev -> next = temp -> next; free(temp); printf("\n Node deleted.."); } else { printf("\n Invalid position.."); getch(); } } } void main(void) { int ch, n; clrscr(); while(1) { ch = menu(); switch(ch) { case 1: if(start == NULL) { printf("\n Number of nodes you want to create: "); scanf("%d", &n); createlist(n); printf("\n List created.."); } else printf("\n List is already created.."); break; case 2: insert_at_beg(); break; case 3:  insert_at_end(); break; case 4: insert_at_mid(); break; case 5: delete_at_beg(); break; case 6: delete_at_last(); break; case 7: delete_at_mid(); break; case 8: traverse(); break; case 9: printf("\n The contents of List (Right to Left): \n"); rev_traverse(start); printf(" X "); break; case 10: printf("\n No of nodes : %d ", countnode(start)); break; case 11 : exit(0); } getch(); } } Complete Source Code for the Implementation of Double Linked List: #include #include #include struct dlinklist { struct node *left; int data; struct node *right; }; typedef struct node node; node *start = NULL; node* getnode() { node * newnode;  newnode = (node *) malloc(sizeof(node)); printf("\n Enter data: "); scanf("%d", &newnode -> data); newnode -> left = NULL; newnode -> right = NULL; return newnode; } int countnode(node *start) { if(start == NULL) return 0; else return 1 + countnode(start -> right); } int menu() { int ch; clrscr(); printf("\n 1.Create"); printf("\n------------------------------"); printf("\n 2. Insert a node at beginning "); printf("\n 3. Insert a node at end"); printf("\n 4. Insert a node at middle"); printf("\n------------------------------"); printf("\n 5. Delete a node from beginning"); printf("\n 6. Delete a node from Last"); printf("\n 7. Delete a node from Middle"); printf("\n------------------------------"); printf("\n 8. Traverse the list from Left to Right "); printf("\n 9. Traverse the list from Right to Left "); printf("\n------------------------------"); printf("\n 10.Count the Number of nodes in the list"); printf("\n 11.Exit"); printf("\n\n Enter your choice: "); scanf("%d", &ch); return ch; } void createlist(int n) { int i; node *newnode; node *temp; for(i = 0; i < n; i++) { newnode = getnode(); if(start == NULL) start = newnode; else { temp = start; while(temp -> right) temp = temp -> right; temp -> right = newnode;  newnode -> left = temp; } } } void traverse_left_to_right() { node *temp; temp = start; printf("\n The contents of List: "); if(start == NULL ) printf("\n Empty List"); else { while(temp != NULL) { printf("\t %d ", temp -> data); temp = temp -> right; } } } void traverse_right_to_left() { node *temp; temp = start; printf("\n The contents of List: "); if(start == NULL) printf("\n Empty List"); else { while(temp -> right != NULL) temp = temp -> right; } while(temp != NULL) { printf("\t%d", temp -> data); temp = temp -> left; } } void dll_insert_beg() { node *newnode; newnode = getnode(); if(start == NULL) start = newnode; else { newnode -> right = start; start -> left = newnode; start = newnode; } } void dll_insert_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL) start = newnode; else { temp = start; while(temp -> right != NULL) { temp = temp -> right; } temp -> right = newnode; newnode -> left = temp; } } void dll_insert_mid() { node *newnode,*temp; int pos, nodectr, ctr = 1; newnode = getnode(); printf("\n Enter the position: "); scanf("%d", &pos); nodectr = countnode(start); if(pos - nodectr >= 2) { printf("\n Position is out of range.."); return; } if(pos > 1 && pos < nodectr) { temp = start; while(ctr < pos - 1) { temp = temp -> right; ctr++; } newnode -> left = temp; newnode -> right = temp -> right; temp -> right -> left = newnode; temp -> right = newnode; } else printf("position %d of list is not a middle position ", pos); } void dll_delete_beg() { node *temp; if(start == NULL) { printf("\n Empty list"); getch(); return ;  } else { temp = start; start = start -> right; start -> left = NULL; free(temp); } } void dll_delete_last() { node *temp; if(start == NULL) { printf("\n Empty list"); getch(); return ; } else { temp = start; while(temp -> right != NULL) temp = temp -> right; temp -> left -> right = NULL; free(temp); temp = NULL; } } void dll_delete_mid() { int i = 0, pos, nodectr; node *temp; if(start == NULL) { printf("\n Empty List"); getch(); return; } else { printf("\n Enter the position of the node to delete: "); scanf("%d", &pos); nodectr = countnode(start); if(pos > nodectr) { printf("\nthis node does not exist"); getch(); return; } if(pos > 1 && pos < nodectr) { temp = start; i= 1; while(i < pos)  { temp = temp -> right; i++; } temp -> right -> left = temp -> left; temp -> left -> right = temp -> right; free(temp); printf("\n node deleted.."); } else { printf("\n It is not a middle position.."); getch(); } } } void main(void) { int ch, n; clrscr(); while(1) { ch = menu(); switch( ch) { case 1 : printf("\n Enter Number of nodes to create: "); scanf("%d", &n); createlist(n); printf("\n List created.."); break; case 2 : dll_insert_beg(); break; case 3 : dll_insert_end(); break; case 4 : dll_insert_mid(); break; case 5 : dll_delete_beg(); break; case 6 : dll_delete_last(); break; case 7 : dll_delete_mid(); break; case 8 : traverse_left_to_right(); break; case 9 : traverse_right_to_left(); break;  case 10 : printf("\n Number of nodes: %d", countnode(start)); break; case 11: exit(0); } getch(); } } Source Code for Circular Single Linked List: # include # include # include struct cslinklist { int data; struct cslinklist *next; }; typedef struct cslinklist node; node *start = NULL; int nodectr; node* getnode() { node * newnode; newnode = (node *) malloc(sizeof(node)); printf("\n Enter data: "); scanf("%d", &newnode -> data); newnode -> next = NULL; return newnode; } int menu() { int ch; clrscr(); printf("\n 1. Create a list "); printf("\n\n--------------------------"); printf("\n 2. Insert a node at beginning "); printf("\n 3. Insert a node at end"); printf("\n 4. Insert a node at middle"); printf("\n\n--------------------------"); printf("\n 5. Delete a node from beginning"); printf("\n 6. Delete a node from Last"); printf("\n 7. Delete a node from Middle"); printf("\n\n--------------------------"); printf("\n 8. Display the list"); printf("\n 9. Exit"); printf("\n\n--------------------------"); printf("\n Enter your choice: "); scanf("%d", &ch); return ch; } void createlist(int n) { int i; node *newnode; node *temp; nodectr = n; for(i = 0; i < n ; i++) { newnode = getnode(); if(start == NULL) { start = newnode; } else { temp = start; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } } newnode ->next = start; } void display() { node *temp; temp = start; printf("\n The contents of List (Left to Right): "); if(start == NULL ) printf("\n Empty List"); else { do { printf("\t %d ", temp -> data); temp = temp -> next; } while(temp != start); printf(" X "); } } void cll_insert_beg() { node *newnode, *last; newnode = getnode(); if(start == NULL) { start = newnode; newnode -> next = start; } else { last = start; while(last -> next != start)  last= last -> next; newnode -> next = start; start = newnode; last -> next = start; } printf("\n Node inserted at beginning.."); nodectr++; } void cll_insert_end() { node *newnode, *temp; newnode = getnode(); if(start == NULL ) { start = newnode; newnode -> next = start; } else { temp = start; while(temp -> next != start) temp = temp -> next; temp -> next = newnode; newnode -> next = start; } printf("\n Node inserted at end.."); nodectr++; } void cll_insert_mid() { node *newnode, *temp, *prev; int i, pos ; newnode = getnode(); printf("\n Enter the position: "); scanf("%d", &pos); if(pos > 1 && pos < nodectr) { temp = start; prev = temp; i= 1; while(i < pos) { prev = temp; temp = temp -> next; i++; } prev -> next = newnode; newnode -> next = temp; nodectr++; printf("\n Node inserted at middle.."); } else { printf("position %d of list is not a middle position ", pos);  } } void cll_delete_beg() { node *temp, *last; if(start == NULL) { printf("\n No nodes exist.."); getch(); return ; } else { last = temp = start; while(last -> next != start) last= last -> next; start = start -> next; last -> next = start; free(temp); nodectr--; printf("\n Node deleted.."); if(nodectr == 0) start = NULL; } } void cll_delete_last() { node *temp, *prev; if(start == NULL) { printf("\n No nodes exist.."); getch(); return ; } else { temp = start; prev = start; while(temp -> next != start) { prev = temp; temp = temp -> next; } prev -> next = start; free(temp); nodectr--; if(nodectr == 0) start = NULL; printf("\n Node deleted.."); } } void cll_delete_mid() {  int i = 0, pos; node *temp, *prev; if(start == NULL) { printf("\n No nodes exist.."); getch(); return ; } else { printf("\n Which node to delete: "); scanf("%d", &pos); if(pos > nodectr) { printf("\nThis node does not exist"); getch(); return; } if(pos > 1 && pos < nodectr) { temp=start; prev = start; i= 0; while(i < pos - 1) { prev = temp; temp = temp -> next ; i++; } prev -> next = temp -> next; free(temp); nodectr--; printf("\n Node Deleted.."); } else { printf("\n It is not a middle position.."); getch(); } } } void main(void) { int result; int ch, n; clrscr(); while(1) { ch = menu(); switch(ch) { case 1 : if(start == NULL) { printf("\n Enter Number of nodes to create: ");  scanf("%d", &n); createlist(n); printf("\nList created.."); } Else printf("\n List is already Exist.."); break; case 2 : cll_insert_beg(); break; case 3 : cll_insert_end(); break; case 4 : cll_insert_mid(); break; case 5 : cll_delete_beg(); break; case 6 : cll_delete_last(); break; case 7 : cll_delete_mid(); break; case 8 : display(); break; case 9 : exit(0); } getch(); } }