Singly linked list or One way chain
Singly linked list can be defined as the collection of ordered set of elements.
The number of elements may vary according to need of the program. A node
in the singly linked list consist of two parts: data part and link part. Data part
of the node stores actual information that is to be represented by the node
while the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In
other words, we can say that each node contains only next pointer, therefore
we can not traverse the list in the reverse direction.
Consider an example where the marks obtained by the student in three
subjects are stored in a linked list as shown in the figure.
In the above figure, the arrow represents the links. The data part of every
node contains the marks obtained by the student in the different subject.
The last node in the list is identified by the null pointer which is present in
the address part of the last node. We can have as many elements we
require, in the data part of the list.
Complexity
Data Data Structure Data Structure
Structur
e
Average Worst Worst
Acce Sear Inserti Deleti Acce Sear Inserti Deleti
ss ch on on ss ch on on
Singly θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(
Linked n)
List
Operations on Singly Linked List
There are various operations which can be performed on singly linked list. A
list of all such operations is given below.
Node Creation
1. struct node
2. {
3. int data;
4. struct node *next;
5. };
6. struct node *head, *ptr;
7. ptr = (struct node *)malloc(sizeof(struct node *));
Insertion
The insertion into a singly linked list can be performed at different positions.
Based on the position of the new node being inserted, the insertion is
categorized into the following categories.
SN Operation Description
1 Insertion at beginning It involves inserting any
element at the front of the
list. We just need to a few
link adjustments to make
the new node as the head
of the list.
2 Insertion at end of the list It involves insertion at the
last of the linked list. The
new node can be inserted
as the only node in the list
or it can be inserted as the
last one. Different logics are
implemented in each
scenario.
3 Insertion after specified It involves insertion after
node the specified node of the
linked list. We need to skip
the desired number of
nodes in order to reach the
node after which the new
node will be inserted. .
Deletion and Traversing
The Deletion of a node from a singly linked list can be performed at different
positions. Based on the position of the node being deleted, the operation is
categorized into the following categories.
SN Operation Description
1 Deletion at beginning It involves deletion of
a node from the
beginning of the list.
This is the simplest
operation among all. It
just need a few
adjustments in the
node pointers.
2 Deletion at the end of the list It involves deleting
the last node of the
list. The list can either
be empty or full.
Different logic is
implemented for the
different scenarios.
3 Deletion after specified node It involves deleting
the node after the
specified node in the
list. we need to skip
the desired number of
nodes to reach the
node after which the
node will be deleted.
This requires
traversing through the
list.
4 Traversing In traversing, we
simply visit each node
of the list at least
once in order to
perform some specific
operation on it, for
example, printing
data part of each
node present in the
list.
5 Searching In searching, we
match each element
of the list with the
given element. If the
element is found on
any of the location
then location of that
element is returned
otherwise null is
returned. .
Linked List in C: Menu Driven Program
1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *head;
9.
10.void beginsert ();
11.void lastinsert ();
12.void randominsert();
13.void begin_delete();
14.void last_delete();
15.void random_delete();
16.void display();
17.void search();
18.void main ()
19.{
20. int choice =0;
21. while(choice != 9)
22. {
23. printf("\n\n*********Main Menu*********\n");
24. printf("\nChoose one option from the following list ...\n");
25. printf("\
n===============================================\n");
26. printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\
n4.Delete from Beginning\n
27. 5.Delete from last\n6.Delete node after specified location\n7.Search for an ele
ment\n8.Show\n9.Exit\n");
28. printf("\nEnter your choice?\n");
29. scanf("\n%d",&choice);
30. switch(choice)
31. {
32. case 1:
33. beginsert();
34. break;
35. case 2:
36. lastinsert();
37. break;
38. case 3:
39. randominsert();
40. break;
41. case 4:
42. begin_delete();
43. break;
44. case 5:
45. last_delete();
46. break;
47. case 6:
48. random_delete();
49. break;
50. case 7:
51. search();
52. break;
53. case 8:
54. display();
55. break;
56. case 9:
57. exit(0);
58. break;
59. default:
60. printf("Please enter valid choice..");
61. }
62. }
63.}
64.void beginsert()
65.{
66. struct node *ptr;
67. int item;
68. ptr = (struct node *) malloc(sizeof(struct node *));
69. if(ptr == NULL)
70. {
71. printf("\nOVERFLOW");
72. }
73. else
74. {
75. printf("\nEnter value\n");
76. scanf("%d",&item);
77. ptr->data = item;
78. ptr->next = head;
79. head = ptr;
80. printf("\nNode inserted");
81. }
82.
83.}
84.void lastinsert()
85.{
86. struct node *ptr,*temp;
87. int item;
88. ptr = (struct node*)malloc(sizeof(struct node));
89. if(ptr == NULL)
90. {
91. printf("\nOVERFLOW");
92. }
93. else
94. {
95. printf("\nEnter value?\n");
96. scanf("%d",&item);
97. ptr->data = item;
98. if(head == NULL)
99. {
100. ptr -> next = NULL;
101. head = ptr;
102. printf("\nNode inserted");
103. }
104. else
105. {
106. temp = head;
107. while (temp -> next != NULL)
108. {
109. temp = temp -> next;
110. }
111. temp->next = ptr;
112. ptr->next = NULL;
113. printf("\nNode inserted");
114.
115. }
116. }
117. }
118. void randominsert()
119. {
120. int i,loc,item;
121. struct node *ptr, *temp;
122. ptr = (struct node *) malloc (sizeof(struct node));
123. if(ptr == NULL)
124. {
125. printf("\nOVERFLOW");
126. }
127. else
128. {
129. printf("\nEnter element value");
130. scanf("%d",&item);
131. ptr->data = item;
132. printf("\nEnter the location after which you want to insert ");
133. scanf("\n%d",&loc);
134. temp=head;
135. for(i=0;i<loc;i++)
136. {
137. temp = temp->next;
138. if(temp == NULL)
139. {
140. printf("\ncan't insert\n");
141. return;
142. }
143.
144. }
145. ptr ->next = temp ->next;
146. temp ->next = ptr;
147. printf("\nNode inserted");
148. }
149. }
150. void begin_delete()
151. {
152. struct node *ptr;
153. if(head == NULL)
154. {
155. printf("\nList is empty\n");
156. }
157. else
158. {
159. ptr = head;
160. head = ptr->next;
161. free(ptr);
162. printf("\nNode deleted from the begining ...\n");
163. }
164. }
165. void last_delete()
166. {
167. struct node *ptr,*ptr1;
168. if(head == NULL)
169. {
170. printf("\nlist is empty");
171. }
172. else if(head -> next == NULL)
173. {
174. head = NULL;
175. free(head);
176. printf("\nOnly node of the list deleted ...\n");
177. }
178.
179. else
180. {
181. ptr = head;
182. while(ptr->next != NULL)
183. {
184. ptr1 = ptr;
185. ptr = ptr ->next;
186. }
187. ptr1->next = NULL;
188. free(ptr);
189. printf("\nDeleted Node from the last ...\n");
190. }
191. }
192. void random_delete()
193. {
194. struct node *ptr,*ptr1;
195. int loc,i;
196. printf("\n Enter the location of the node after which you want to perform de
letion \n");
197. scanf("%d",&loc);
198. ptr=head;
199. for(i=0;i<loc;i++)
200. {
201. ptr1 = ptr;
202. ptr = ptr->next;
203.
204. if(ptr == NULL)
205. {
206. printf("\nCan't delete");
207. return;
208. }
209. }
210. ptr1 ->next = ptr ->next;
211. free(ptr);
212. printf("\nDeleted node %d ",loc+1);
213. }
214. void search()
215. {
216. struct node *ptr;
217. int item,i=0,flag;
218. ptr = head;
219. if(ptr == NULL)
220. {
221. printf("\nEmpty List\n");
222. }
223. else
224. {
225. printf("\nEnter item which you want to search?\n");
226. scanf("%d",&item);
227. while (ptr!=NULL)
228. {
229. if(ptr->data == item)
230. {
231. printf("item found at location %d ",i+1);
232. flag=0;
233. }
234. else
235. {
236. flag=1;
237. }
238. i++;
239. ptr = ptr -> next;
240. }
241. if(flag==1)
242. {
243. printf("Item not found\n");
244. }
245. }
246.
247. }
248.
249. void display()
250. {
251. struct node *ptr;
252. ptr = head;
253. if(ptr == NULL)
254. {
255. printf("Nothing to print");
256. }
257. else
258. {
259. printf("\nprinting values . . . . .\n");
260. while (ptr!=NULL)
261. {
262. printf("\n%d",ptr->data);
263. ptr = ptr -> next;
264. }
265. }
266. }
267.
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
1
Enter value
1
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
2
Enter value?
2
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
3
Enter element value1
Enter the location after which you want to insert 1
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
8
printing values . . . . .
1
2
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
2
Enter value?
123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
1
Enter value
1234
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
4
Node deleted from the begining ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
5
Deleted Node from the last ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
6
Enter the location of the node after which you want to perform deletion
1
Deleted node 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
8
printing values . . . . .
1
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
7
Enter item which you want to search?
1
item found at location 1
item found at location 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
9
Singly linked list in C
Data structures are crucial elements in computer programming because
they make data handling and storage efficient. The linked list is a typical
data structure. In this blog post, we will examine the concept of a single
linked list in the C programming language. We'll go over its operations,
definition, and example code syntax and outputs.
Each node in a singly linked list has a data element and a reference to the
node after it in the list, making it a linear data structure. The list's head
node is the first node, while the last node points to NULL to denote the list's
end.
A structure for each list node must be constructed to define a single linked
list in C. The structure should have two fields: a data field for storing the
actual data and a pointer field for holding a reference to the subsequent
node.
1. struct Node {
2. int data;
3. struct Node* next;
4. };
We must first initialize the head reference to NULL, which denotes an empty
list, in order to establish a single linked list. After that, we may add nodes to
the list by dynamically allocating memory for each node and connecting
them with the next pointer.
1. struct Node* head = NULL; // Initializing an empty list
2.
3. void insert(int value) {
4. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
5. newNode->data = value;
6. newNode->next = NULL;
7.
8. if (head == NULL) {
9. head = newNode;
10. } else {
11. struct Node* current = head;
12. while (current->next != NULL) {
13. current = current->next;
14. }
15. current->next = newNode;
16. }
17. }
We must first initialize the head reference to NULL, which denotes an empty
list, in order to establish a single linked list. After that, we may add nodes to
the list by dynamically allocating memory for each node and connecting
them with the next pointer.
1. void traverse() {
2. struct Node* current = head;
3. while (current != NULL) {
4. printf("%d ", current->data);
5. current = current->next;
6. }
7. }
A singly linked list can be searched for an element by traversing the list and
comparing each node's data with the desired value. If a match is made, the
relevant node is returned; if not, NULL is returned to show that the element
is not present in the list.
1. struct Node* search(int value) {
2. struct Node* current = head;
3. while (current != NULL) {
4. if (current->data == value) {
5. return current;
6. }
7. current = current->next;
8. }
9. return NULL;
10. }
To remove a component from a singly linked list, locate the node that
contains the desired value and modify the links to the preceding and
following nodes accordingly. Additionally, the memory that the destroyed
node used must be freed.
1. void delete(int value) {
2. if (head == NULL) {
3. printf("List is empty.");
4. return;
5. }
6.
7. struct Node* current = head;
8. struct Node* previous = NULL;
9.
10. while (current != NULL) {
11. if (current->data == value) {
12. if (previous == NULL) {
13. head = current->next;
14. } else {
15. previous->next = current->next;
16. }
17. free(current);
18. return;
19. }
20. previous = current;
21. current = current->next;
22. }
23.
24. printf("Element not found in the list.");
25. }
Let's create a list, add entries, and perform various operations on it to
show how a single linked list is used.
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. // Singly Linked List structure
5. struct Node {
6. int data;
7. struct Node* next;
8. };
9.
10. // Global head pointer
11. struct Node* head = NULL;
12.
13. // Function to insert a node at the end of the list
14. void insert(int value) {
15. // Create a new node
16. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node
));
17. newNode->data = value;
18. newNode->next = NULL;
19.
20. // Check if the list is empty
21. if (head == NULL) {
22. head = newNode;
23. } else {
24. // Traverse to the end of the list
25. struct Node* current = head;
26. while (current->next != NULL) {
27. current = current->next;
28. }
29. // Link the new node to the last node
30. current->next = newNode;
31. }
32. }
33.
34. // Function to traverse and print the list
35. void traverse() {
36. struct Node* current = head;
37. while (current != NULL) {
38. printf("%d ", current->data);
39. current = current->next;
40. }
41. }
42.
43. int main() {
44. // Insert elements into the list
45. insert(10);
46. insert(20);
47. insert(30);
48. insert(40);
49.
50. // Traverse and print the list
51. printf("List: ");
52. traverse();
53.
54. return 0;
55. }
List: 10 20 30 40
