A singly linked list is a data structure consisting of nodes where each node has a pointer to the next node in the list and the last node points to a null pointer marking the end of the list. Linked list provides a versatile way to organize a collection of data in system programming. Nodes in a linked list can be added, removed or modified. The program shown below is a very good starting point to understand singly linked list better.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | #include <stdio.h> #include <stdlib.h> #define OK 0 #define NG -1 struct node { int data; struct node* next; }; void printList(); int insertNodeFirst(int data); int insertNodeLast(int data); int deleteNodeIfDataIs(int data); struct node* listHead = NULL; void printList() { struct node* currentNode = listHead; printf("Printing linked list\n\n"); while(currentNode != NULL) { printf("| %d | -> ", currentNode->data); currentNode = currentNode->next; } printf("NULL\n\n"); } int insertNodeFirst(int data) { int retVal = NG; struct node* newNode = NULL; struct node* temp = listHead; newNode = (struct node*)malloc(sizeof(struct node)); if (newNode != NULL) { retVal = OK; newNode->data = data; listHead = newNode; if (listHead == NULL) { newNode->next = NULL; } else { newNode->next = temp; } } return retVal; } int insertNodeLast(int data) { int retVal = NG; struct node* newNode = NULL; struct node* temp = listHead; newNode = (struct node*)malloc(sizeof(struct node)); if (newNode != NULL) { retVal = OK; newNode->data = data; newNode->next = NULL; if (listHead == NULL) { listHead = newNode; } else { while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } return retVal; } int deleteNodeIfDataIs(int data) { int retVal = NG; struct node* temp = listHead; struct node* prev; do { if (temp == NULL) { continue; } if (temp->data == data) { retVal = OK; listHead = temp->next; continue; } while (temp != NULL) { if (temp->data == data) { retVal = OK; prev->next = temp->next; break; } prev = temp; temp = temp->next; } } while (0); if (retVal == OK) { free(temp); } return retVal; } int main() { insertNodeFirst(1); insertNodeFirst(2); insertNodeFirst(3); insertNodeFirst(4); insertNodeFirst(5); printList(); // | 5 | -> | 4 | -> | 3 | -> | 2 | -> | 1 | -> NULL deleteNodeIfDataIs(4); printList(); // | 5 | -> | 3 | -> | 2 | -> | 1 | -> NULL insertNodeLast(6); insertNodeLast(7); printList(); // | 5 | -> | 3 | -> | 2 | -> | 1 | -> | 6 | -> | 7 | -> NULL return 0; } |
About Program:
This C program demonstrates a singly linked list. Basic supported functionalities include insert node at at first, insert node at last and delete a node if a data is found.
Code walk-through:
The main() function inserts nodes, deletes node and prints the list from its function body.
The below lines actually inserts few nodes into the list by inserting at the start of list,
143 144 145 146 147 148 149 | insertNodeFirst(1); insertNodeFirst(2); insertNodeFirst(3); insertNodeFirst(4); insertNodeFirst(5); printList(); // | 5 | -> | 4 | -> | 3 | -> | 2 | -> | 1 | -> NULL |
The following lines deletes a node if the data is 4 and prints the list,
151 152 153 | deleteNodeIfDataIs(4); printList(); // | 5 | -> | 3 | -> | 2 | -> | 1 | -> NULL |
The below code section inserts couple of nodes at the last of the linked list and prints the list,
155 156 157 158 | insertNodeLast(6); insertNodeLast(7); printList(); // | 5 | -> | 3 | -> | 2 | -> | 1 | -> | 6 | -> | 7 | -> NULL |
Analysis of printList()
struct node* currentNode = listHead; sets the currentNode variable to the head of the linked list.
The below while-loop iterates through the entire linked list and prints the individual data values.
27 28 29 30 31 32 | while(currentNode != NULL) { printf("| %d | -> ", currentNode->data); currentNode = currentNode->next; } |
Analysis of insertNodeFirst()
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | int insertNodeFirst(int data) { int retVal = NG; struct node* newNode = NULL; struct node* temp = listHead; newNode = (struct node*)malloc(sizeof(struct node)); if (newNode != NULL) { retVal = OK; newNode->data = data; listHead = newNode; if (listHead == NULL) { newNode->next = NULL; } else { newNode->next = temp; } } return retVal; } |
A new node is created using the malloc() function and assigns data to its data member. Head of the linked list is updated with the newly created node as the node is to be inserted at the front.
In case if the list was empty, then the newly created node’s next pointer is assigned as NULL else the next pointer is assigned with the previous header node.
Analysis of insertNodeLast()
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | int insertNodeLast(int data) { int retVal = NG; struct node* newNode = NULL; struct node* temp = listHead; newNode = (struct node*)malloc(sizeof(struct node)); if (newNode != NULL) { retVal = OK; newNode->data = data; newNode->next = NULL; if (listHead == NULL) { listHead = newNode; } else { while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } return retVal; } |
Here also a new node is created using the malloc() function. The data is assigned to its data member and NULL is assigned to the new node’s next pointer since the node is to be inserted at the end of the list.
If the list is empty then the new node is assigned as the head node. Otherwise the while-loop iterates to the end of the list and inserts the new node there.
Analysis of deleteNodeIfDataIs()
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | int deleteNodeIfDataIs(int data) { int retVal = NG; struct node* temp = listHead; struct node* prev; do { if (temp == NULL) { continue; } if (temp->data == data) { retVal = OK; listHead = temp->next; continue; } while (temp != NULL) { if (temp->data == data) { retVal = OK; prev->next = temp->next; break; } prev = temp; temp = temp->next; } } while (0); if (retVal == OK) { free(temp); } return retVal; } |
A do-while loop is used to facilitate in an early exit from the function if there is a NULL pointer passed or if the data being searched is found at the head node itself.
If the data being searched is not at the head of the list then the nested while loop will iterate through the individual list nodes and if found, then the next pointer of the previous node is updated to skip the matched node which will be later deleted using the free() function call.
General Note:
In this code there are return values implemented to check whether a particular function execution is a success or not, but the return values are discarded as this article is only an example to show the functionality of a singly linked list.
In the case of production code the return values of the functions needs to be evaluated before proceeding to the next statement of the program and should also service the error codes.
