The CS Point

In computer science, a linked list is a linear collection of elements, called nodes, each node have info field and next field pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes in sequence and connected with links. In simplest form of this data structure, each node is consist of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. Types of Link List Singly Link List: Insert node at first position in singly link list Insert node at last position in singly link list Insert node at specific position in singly link list Delete node at first position in singly link list Delete node at last position in singly link list Delete node at specific position in singly link list Find number of nodes in singly link list Dublication of singly link list Concatenation of two singly link list So...

Now we see how to create a duplicate of link list. Here we use two link list. First list contains the data to be copied and other will the get the copy of first list. Algorithm to copy the link list: The algorithm is used to copy the info part of FROM list to INTO list. As shown below:  Set TEMP = FROM    //FROM is same as START of list While TEMP != NULL Insert the INFO part of TEMP at the last of INTO list Set TEMP = TEMP->NEXT End While   Function to create the copy of link list: void copyList(NODE **from, NODE **into){ NODE *temp; temp = *from; while(temp != NULL){ insertAtLast(into, temp->info); temp = temp->next; } }   Program to create the copy of link list: #include <stdio.h> #include <malloc.h> struct node{ int info; struct node *next; }; typedef struct node NODE; void insertAtLast(NODE **, int); void traverse(NODE **); void copyList(NODE **, NODE **); int main(){ NODE *start1 = NULL; NODE *start2 = NULL...

Here we will see how to concat two single link list into other link list. First we copy the content of first list in third list and then the content of second list into third list. Algorithm for concatenation of two link list: This algorithm will use three list. List 1 and List 2 will be concatenated into List 3. The step below: Copy the list 1 into list 3 Copy the list 2 at the last of list 3 Function to concat two link list: void concatLists(NODE **start1, NODE **start2, NODE **mergeinto){ NODE *temp; temp = *start1; while(temp != NULL){ insertAtLast(&*mergeinto, temp->info); temp = temp->next; } temp = *start2; while(temp != NULL){ insertAtLast(&*mergeinto, temp->info); temp = temp->next; } }   Program to concat two link lists: #include <stdio.h> #include <malloc.h> struct node{ int info; struct node *next; }; typedef struct node NODE; void insertAtLast(NODE **, int); void traverse(NODE **); void concatLists(NODE **,...

Here we will see how to sort the link list on the info field of its nodes. Algorithm to sort link list: Set TEMP = START While(TEMP is not NULL) Set CURRENT to point to next of TEMP, (CURRENT = TEMP->NEXT) While(CURRENT is not NULL) If(TEMP->INFO > CURRENT->INFO) Swap(TEMP->INFO, CURRENT->INFO) End If; Update CURRENT to point to next node. (CURRENT = CURRENT->NEXT) End While; Update TEMP to point to next node, (TEMP = TEMP->NEXT) End While;   Function to sort the link list: We will use bubble sort algorithm to sort the list. Code below: void sortList(NODE **start){ NODE *current, *temp; int tempinfo; temp = *start; while( temp ){ current = temp->next; while( current ){ if( temp->info > current->info ){ tempinfo = temp->info; temp->info = current->info; current->info = tempinfo; } current = current->next; } temp = temp->next; } }   Program to sort the link list: #include <...

Now, we will see how to find the number of nodes in single link list: Algorithm to find number of nodes in the list: Set TEMP = START Set COUNT = 0 While (TEMP != NULL) COUNT = COUNT + 1 TEMP = TEMP->NEXT End While; Return COUNT   Function to count number of node in link list: int countNodes(NODE **start){ NODE *temp = *start; int count = 0; while(temp != NULL){ count++; temp = temp->next; } return count; }   Program to count number of nodes in the link list: #include <stdio.h> #include <malloc.h> struct node{ int info; struct node *next; }; typedef struct node NODE; void insertAtFirst(NODE **, int); int countNodes(NODE **); int main(){ NODE *start = NULL; insertAtFirst(&start, 4); insertAtFirst(&start, 5); insertAtFirst(&start, 6); printf("\nThe list have %d nodes\n", countNodes(&start)); return 0; } int countNodes(NODE **start){ NODE *temp = *start; int count = 0; while(temp != NULL){ count++; te...

Deletion of node at specific position N requires traversing the link list to find the N-1 th node so that we can make it's next pointer points to N+1 th node. In the process of deletion of node at specific position, first we check whether the list has some nodes and the position N should be less than number of nodes in the list. It would be error to delete the node which doesn't exist in the list. When deleting the node we come up with the conditions when we will not able to access the N-1 th and N+1 th node for first and last node respectively. These conditions will be handled seperately. So let us see the algorithm to implement deletion of node at specific position below: Algorithm to delete node at position N: The alrorithm presented here uses START as pointer to first node and N is the specific position of node that is to be deleted. TEMPs are temporary pointers that is used in deletion process. Set TEMP = START If START == NULL or N < 1 There is no node or invalid p...

Now we will see how to delete node at last position in singly link list. Algorithm to delete last node in singly link list: Set TEMP = START If START != NULL If list has only one node i.e. [START->NEXT == NULL ] Set START = NULL Else Traverse the list so that TEMP points to second last node Make second last node point to nothing i.e. [TEMP->NEXT = NULL] End If End If Function to delete last node in singly link list:   int deleteLast(NODE **start){ NODE *temp = *start; int info = -1; if(*start == NULL){ printf("\nNo nodes exists in the list"); } else if((*start)->next == NULL){ info = (*start)->info; free(*start); *start = NULL; } else{ while(temp->next->next != NULL){ temp = temp->next; } info = temp->next->info; free(temp->next); temp->next = NULL; } return info; }   Program to delete last node in the singly link list:   #include <stdio.h> #include <malloc.h> struct...

Now we will see how to delete node at first position in singly link list. Algorithm to delete node at first position in singly link list: Set TEMP = START If START != NULL Make START points to second node i.e. [START = START->NEXT] FREE (TEMP) End If Function to delete node at first position in singly link list:   int deleteFirst(NODE **start){ NODE *temp = *start; int info = -1; if(*start == NULL){ printf("\nNo nodes exists in the list\n"); } else{ info = (*start)->info; *start = (*start)->next; free(temp); } return info; }   Program to delete node at first position in the singly link list:   #include <stdio.h> #include <malloc.h> struct node{ int info; struct node *next; }; typedef struct node NODE; void insertAtFirst(NODE **, int); int deleteFirst(NODE **); void traverse(NODE **); int main(){ NODE *start = NULL; insertAtFirst(&start, 4); insertAtFirst(&start, 5); traverse(&start); deleteFirst(...

Insertion of a new node at position N in singly link list requires traversing the list for N-1 th node so that links are updated to accommodate the new node in the list. The new node's next is set to point to Nth node of the list and then N-1 th node's next pointer is updated so that it reference to new node. The step by step algorithm to insert node at Nth position is as below: Algorithm to insert node at specific position N in singly link list: This algorithm will insert the new node PTR at the position N in the link list. The steps are as follows: Create new node PTR Set the INFO field of PTR If N is less than 1 Node can't be inserted Else If node is to be inserted at first i.e. [N=1] Make new node PTR points to first node i.e. [PTR->NEXT = START] Make START point to new node PTR i.e. [START = PTR] Else Traverse the list to get the (N-1)th node of list into TEMP Make PTR's next pointer point to Nth node in the list i.e. [PTR -> NEXT  =  TEMP-...

To insert a node at last position of singly list, we need to traverse the list using some temporary pointer so that temporary pointer points to last node of that list. After getting last node into temp, it's next pointer is updated to point to the new node that is to be inserted at last. After that, the next pointer of new node is set to point to nothing for indicating end of the list as it is inserted at last. Here is the algorithm to inserted node at last position of singly link list: Algorithm to insert node at last position in singly link list: Create new node PTR Set the INFO field of PTR Set PTR->NEXT = NULL If the list has no nodes i.e. [START = NULL] Make START point to new node PTR i.e. [START = PTR] Else Traverse the list using TEMP, so that it points to last node Make last node's NEXT point to new node PTR i.e. [TEMP->NEXT = PTR] End If     Function to insert node at last position in singly link list:   void insertAtLast(NODE **st...

Insertion of a new node at first position requires updation of start pointer pointing to first node of the singly link list. It create a new node and make it's next pointer point to first node of the list and then make the  start  link reference to this new node. The algorithm for the insertion at first position is as below: Algorithm to insert node at first position in singly link list: Create a new node PTR Set the INFO field of PTR Make PTR point to first node i.e. [PTR->NEXT = START] Make START points to PTR i.e. [START = PTR]   Function to insert node at first position in singly link list: void insertAtFirst(NODE **start, int info){ NODE *ptr = (NODE*) malloc(sizeof(NODE)); ptr->info = info; ptr->next = *start; *start = ptr; }   Program to insert node at first position in singly link list: #include <stdio.h> #include <malloc.h> struct node{ int info; struct node *next; }; typedef struct node NODE; void insertAtFi...

Singly Linked Lists are a type of data structure. In a singly linked list each node in the list stores the information of the node and a pointer to the next node in the list. It does not store any pointer reference to the previous node. It is called a singly linked list because each node only has a single link to another node. To store a single linked list, you only need to store a reference to the first node in that list. The last node has a pointer to NULL to indicate that it is the last node. Before going to discuss the operation on singly link list we will first see the basic structure of the data type and see how it could be represented in c programming. First we will see the how the node or element of singly link list is represented. See the image below: The component of singly list node: info : It contains the actual information next : This field points to the next node in the list   Now we see how the singly link list is represented. See the image below: ...