DS - Linked List
A linked list is a fundamental data structure used in computer science to organize and store a collection of elements. Unlike arrays, linked lists do not require a contiguous block of memory and can efficiently handle dynamic memory allocation.
Key Characteristics
Nodes: A linked list is composed of nodes, where each node contains two main parts:Data: The value or information stored in the node.Reference (or Link): A pointer or reference to the next node in the sequence.
Head: The first node in the linked list. It provides the entry point to the list.Tail: The last node in the list, which typically points to null (or None in some languages) to indicate the end of the list.
Types of Linked Lists
Singly Linked List: Each node contains a single reference to the next node. Traversal is only possible in one direction (from head to tail).
Operations: Insertion, deletion, and traversal are done by following the next references.
Doubly Linked List: Each node contains two references: one to the next node and one to the previous node. This allows for bidirectional traversal.
Operations: Insertion, deletion, and traversal can be done in both directions (forward and backward).
Circular Linked List: The last node in the list points back to the first node, forming a circle. This can be singly or doubly linked.
Operations: Traversal can continue indefinitely due to the circular nature of the list.
Operations
Insertion: Adding a node to the list (at the beginning, end, or a specific position).Deletion: Removing a node from the list (from the beginning, end, or a specific position).Traversal: Accessing each node in the list to process or display its data.Search: Finding a node with a specific value.
Singly Linked List:
1#include <stdio.h>
2#include <stdlib.h>
3struct node
4{
5 int data;
6 struct node *next;
7};
8struct node *head = NULL;
9void insert(int value)
10{
11 struct node *nn = (struct node *)malloc(sizeof(struct node));
12 nn->data = value;
13 nn->next = NULL;
14 if (head == NULL)
15
16 head = nn;
17 else
18 {
19 struct node *current = head;
20 while (current->next != NULL)
21 {
22 current = current->next;
23 }
24 current->next = nn;
25 }
26}
27void delete(int value)
28{
29 if (head == NULL)
30 {
31 printf("empty list");
32 return;
33 }
34 struct node *current = head;
35 struct node *previous = NULL;
36 while (current != NULL)
37 {
38 if (current->data == value)
39 {
40 if (previous == NULL)
41 head = current->next;
42 else
43 previous->next = current->next;
44 free(current);
45 return;
46 }
47 previous = current;
48 current = current->next;
49 }
50 printf("element not found");
51}
52void traverse()
53{
54 struct node *current = head;
55 while (current != NULL)
56 {
57 printf("%d", current->data);
58 current = current->next;
59 }
60}
61
62void main(){
63
64
65
66 while(1)
67{
68 int ch;
69
70 printf("\nMENU\n");
71 printf("1.insert\n");
72 printf("2.delete\n");
73 printf("3.traverse\n");
74 printf("4.exit\n");
75 printf("Enter choice:\n");
76 scanf("%d", &ch);
77
78switch(ch)
79{
80
81 case 1:
82 int d;
83 printf("enter the data value to be inserted");
84 scanf("%d",&d);
85 insert(d);
86 break;
87 case 2:
88 int a;
89 printf("enter the data value to be deleted");
90 scanf("%d",&a);
91 delete(a);
92 break;
93
94 case 3:traverse();
95 break;
96 case 4:exit(0);
97
98 default: printf("Invalid\n");
99}
100}
101}
Queue Using Linked List:
1#include <stdio.h>
2#include <stdlib.h>
3
4struct node
5{
6 struct node *next;
7 int data;
8};
9
10struct node *f,*r;
11
12void enqueue()
13{
14 int a;
15 printf("\nEnter the data value\n");
16 scanf("%d",&a);
17
18 struct node *nn=(struct node *)malloc(sizeof(struct node));
19 nn->data=a;
20 nn->next=NULL;
21
22 if(r==NULL)
23 {
24 f=nn;
25 r=nn;
26 }
27
28 else {
29
30 r->next=nn;
31 r=nn;
32
33 }
34}
35
36void display()
37{
38 struct node *temp;
39 temp=f;
40 printf("\nThe Queue list is as:");
41
42 while(temp->next!=NULL)
43 {
44 printf("\n%d",temp->data);
45 temp=temp->next;
46 }
47
48 printf("\n%d",temp->data);
49}
50
51void dequeue()
52{
53 if(f!=NULL)
54 f=f->next;
55}
56
57void main()
58{
59
60while(1)
61{
62 int ch;
63
64 printf("\nMENU\n");
65 printf("1.enqueue\n");
66 printf("2.display\n");
67 printf("3.dequeue\n");
68 printf("4.exit\n");
69 printf("Enter choice:\n");
70 scanf("%d", &ch);
71
72switch(ch)
73{
74
75 case 1:enqueue();
76 break;
77 case 2:display();
78 break;
79 case 3:dequeue();
80 break;
81 case 4:exit(0);
82
83 default: printf("Invalid\n");
84}
85}
86}
Doubly Linked List:
1#include <stdio.h>
2#include <stdlib.h>
3struct node
4{
5 struct node *prev;
6 struct node *next;
7
8 int data;
9};
10struct node *head;
11void insertion_beginning();
12void insertion_last();
13void deletion_beginning();
14void deletion_last();
15void display();
16void main()
17{
18 int choice = 0;
19 while (choice != 6)
20 {
21 printf("\nChoose one option from the following list ...\n");
22 printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Show\n6.Exit\n");
23 printf("\nEnter your choice?\n");
24 scanf("\n%d", &choice);
25 switch (choice)
26 {
27 case 1:
28 insertion_beginning();
29 break;
30 case 2:
31 insertion_last();
32 break;
33 case 3:
34 deletion_beginning();
35 break;
36 case 4:
37 deletion_last();
38 break;
39 case 5:
40 display();
41 break;
42 case 6:
43 exit(0);
44 break;
45 default:
46 printf("Please enter valid choice..");
47 }
48 }
49}
50void insertion_beginning()
51{
52 struct node *ptr;
53 int item;
54 ptr = (struct node *)malloc(sizeof(struct node));
55 printf("\nEnter Item value");
56 scanf("%d", &item);
57
58 if (head == NULL)
59 {
60 ptr->next = NULL;
61 ptr->prev = NULL;
62 ptr->data = item;
63 head = ptr;
64 }
65 else
66 {
67 ptr->data = item;
68 ptr->prev = NULL;
69 ptr->next = head;
70 head->prev = ptr;
71 head = ptr;
72 }
73 printf("\nNode inserted\n");
74}
75
76void insertion_last()
77{
78 struct node *ptr, *temp;
79 int item;
80 ptr = (struct node *)malloc(sizeof(struct node));
81 printf("\nEnter value");
82 scanf("%d", &item);
83 ptr->data = item;
84 if (head == NULL)
85 {
86 ptr->next = NULL;
87 ptr->prev = NULL;
88 head = ptr;
89 }
90 else
91 {
92 temp = head;
93 while (temp->next != NULL)
94 {
95 temp = temp->next;
96 }
97 temp->next = ptr;
98 ptr->prev = temp;
99 ptr->next = NULL;
100 }
101
102 printf("\nnode inserted\n");
103}
104
105void deletion_beginning()
106{
107 struct node *ptr;
108 if (head == NULL)
109 {
110 printf("\n UNDERFLOW");
111 }
112 else if (head->next == NULL)
113 {
114 head = NULL;
115 free(head);
116 printf("\nnode deleted\n");
117 }
118 else
119 {
120 ptr = head;
121 head = head->next;
122 head->prev = NULL;
123 free(ptr);
124 printf("\nnode deleted\n");
125 }
126}
127void deletion_last()
128{
129 struct node *ptr;
130 if (head == NULL)
131 {
132 printf("\n UNDERFLOW");
133 }
134 else if (head->next == NULL)
135 {
136 head = NULL;
137 free(head);
138 printf("\nnode deleted\n");
139 }
140 else
141 {
142 ptr = head;
143 if (ptr->next != NULL)
144 {
145 ptr = ptr->next;
146 }
147 ptr->prev->next = NULL;
148 free(ptr);
149 printf("\nnode deleted\n");
150 }
151}
152void display()
153{
154 struct node *ptr;
155 printf("\n printing values...\n");
156 ptr = head;
157 while (ptr != NULL)
158 {
159 printf("%d\n", ptr->data);
160 ptr = ptr->next;
161 }
162}