Counting the nodes in a ListReversing a linked list by storing elements backwards in another listCode for Creating and Printing a Linked ListLINKED LIST - II Counting number of nodes in a list Printing a list Searching for a specific node in a list Creating a list Reversing a list Deleting a specific node Inserting a node in a sorted listThe following site gives a good coverage of linked lists. http://cslibrary.stanford.edu/103/LinkedListBasics.pdf Counting the nodes in a List • Recursive version: int count (struct node * pHead) { if (pHead==NULL) return 0; else return(1 + count(pHead->next)); } • Iterative version: int count(struct node *pHead) { struct node * p; int c = 0; p = pHead; while (p != NULL){ c = c + 1; p = p->next; } return c; }Printing the contents of a list To print the contents, traverse the list from the head node to the last node. int PrintList( struct node *list) { struct node current = list ; The dummy name current“ is assigned to the first node of the list . We shall be moving down the list by following the next link of current , without disturbing any item in the list including its name. while (current != NULL) { printf(“%d”, current -> data); current = current -> next; } return 1; } Searching for a node containing a specific item Given a target value, the search attempts to locate the requested node in the linked list. If a node in the list matches the target value, the search returns 1; otherwise it returns 0. // Start with a dummy pointer to headnode pCur = pHead; // Search until target is found or we reach // the end of list while (pCur != NULL ){ if( pCur->data == target) return 1; pCur = pCur->next; } // target not found return 0;Creation of Linked Lists by adding nodes at front of the list Here we assume that the main program is sending a list and an integer to the function. The integer is to be included as the first element of the list, and the new list is to be sent back to the main. A typical statement in the main program could be : p =Add_Start(p, 60). Thus given the values 32,40,55,60 and 80 the following linked list is desired. p 80 60 55 40 32 We invoke malloc to allocate space for a new node. The given integer is stored in the data part. To add the node at the front of the list, all you have to do is to store the pointer to the list in the address part of this node. struct node * Add_Start(struct node *list,int d ) { struct node * pNew=(struct node *) (malloc(sizeof(struct node))); pNew -> data = d ; pNew ->next = list ; return pNew; }Creation of Linked Lists by adding nodes at the end of the list We want to create a list by adding nodes at the end of the list, as and when the user inputs the elements. The main function sends the list p and the value of the element to the function. Thus given the same values as in previous case, the desired Linked list is: p 32 40 55 60 80 Here is a function, which adds a node to end of the linked list named list. Malloc is used to get a new node pNew. The element value is stored in the data part. If there are no elements in the list (empty list), the first pNew is going to be the only node of list., so it returns pNew. If there are nodes in the list, the while loop finds the last node and the pointer to pNew is stored in its address part. struct node* Addrear(struct node *list, int d) { struct node *pNew = NULL; struct node *current = NULL; pNew = (struct node*)malloc(sizeof(struct node)); pNew ->data = d; pNew ->next = NULL; // Store front of the linked list current = list; // if list is empty then this becomes the first node. if (list == NULL) return pNew; while (current ->next != NULL) current = current ->next; current ->next = pNew; // Return a pointer to the created list. return list; } A complete code is provided at the end of this lecture notes.Reversing a linked list by storing elements backwards in another list Given a linked list P P 32 40 55 60 80 it is desired to reverse the elements to result in another list Q Q 80 60 55 40 32 // Reverse the list by inserting every element in front of the previous one pCur= P; second = NULL; while(pCur !=NULL) { struct node* pNew = (struct node*) (malloc(sizeof(struct node))); pNew ->data = pCur ->data; pNew->next = second; second = pNew; pCur = pCur->next; } Q = second;Creation of Linked Lists by adding nodes at front of the list (using double pointers) Here we present a different mechanism to create a linked list. Instead of sending the pointer to the list, we send the address of the pointer to the list as a parameter in the function call and have the list in the memory updated by this function. This is nothing but passing-by-reference the address of the pointer to head node . This can be done through a double pointer. While *list is the address of list, the pointer to the address itself can be passed through the double pointer **list. See the following code where the function is getting the proper pointer, and the called function can see the changes made to the list. Note this function does not return any list. . void Add_Front(struct node **list,int d ) { struct node * pNew=(struct node *) (malloc(sizeof(struct node))); pNew-> data = d ; pNew->next = NULL ; if( *list== NULL) *list = pNew; else { pNew->next = *list; *list = pNew ; } } A typical call from the main function would have the following form: Add_Front( &pList, number ); You may also see pages 12-14 of http://cslibrary.stanford.edu/103/LinkedListBasics.pdffor more information on this.Deleting a Node from a Linked List Deleting a node requires that we logically remove the node from the list by changing various link pointers and then physically deleting the node from the heap. We can delete • the first node • any node in the middle • the end node To logically delete a node: 1. first locate the node itself , name the current node as pCur and its predecessor node as pPre. 2. change the predecessor’s link field to point to successor of the current node. 3. recycle the node (send it back to memory) using free. Note: We may be deleting the only node in a list. So take care of it separately. This will result in an empty list in which case the head pointer is set to NULL.Delete First Node BEFORE pHead pPre 75 124 pCur