Module 3: Linked Lists
1. Introduction
A linked list is a linear dynamic data structure where each element (called a node) contains two parts:
• Data: Stores the actual value.
• Link: A pointer that stores the address of the next node in the sequence.
Unlike arrays, linked lists do not require contiguous memory locations and allow efficient insertions
and deletions.
2. Singly Linked List
2.1 Structure Definition
typedef struct Node {
int data;
struct Node *next;
} Node;
2.2 Insertion at Beginning
Node* insertAtBeginning(Node *head, int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = head;
return newNode;
2.3 Insertion at End
Node* insertAtEnd(Node *head, int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) return newNode;
Node *temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
2.4 Deletion at Beginning
Node* deleteAtBeginning(Node *head) {
if (head == NULL) return NULL;
Node *temp = head;
head = head->next;
free(temp);
return head;
2.5 Deletion at End
Node* deleteAtEnd(Node *head) {
if (head == NULL || head->next == NULL) {
free(head);
return NULL;
Node *temp = head;
while (temp->next->next != NULL)
temp = temp->next;
free(temp->next);
temp->next = NULL;
return head;
2.6 Display List
void displayList(Node *head) {
Node *temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
printf("NULL\n");
3. Implementation of Stack and Queue using Linked Lists
3.1 Stack Using Linked List
Node* push(Node *top, int val) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = val;
newNode->next = top;
return newNode;
Node* pop(Node *top) {
if (top == NULL) return NULL;
Node *temp = top;
top = top->next;
free(temp);
return top;
3.2 Queue Using Linked List
typedef struct {
Node *front;
Node *rear;
} Queue;
Queue enqueue(Queue q, int val) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = val;
newNode->next = NULL;
if ([Link] == NULL) {
[Link] = [Link] = newNode;
} else {
[Link]->next = newNode;
[Link] = newNode;
return q;
Queue dequeue(Queue q) {
if ([Link] == NULL) return q;
Node *temp = [Link];
[Link] = [Link]->next;
if ([Link] == NULL) [Link] = NULL;
free(temp);
return q;
4. Concatenation of Two Lists
Node* concatenate(Node *list1, Node *list2) {
if (list1 == NULL) return list2;
Node *temp = list1;
while (temp->next != NULL)
temp = temp->next;
temp->next = list2;
return list1;
5. Reverse a List Without Creating a New Node
Node* reverseList(Node *head) {
Node *prev = NULL, *current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
return prev;
6. Static vs Dynamic (Linked) Allocation
• Static Allocation: Uses arrays, fixed size, memory allocated at compile time.
• Dynamic Allocation: Uses pointers, size can vary at runtime, memory allocated from heap.
Static Example:
int arr[10];
Dynamic Example (Linked List):
Node *head = NULL;
head = insertAtBeginning(head, 5);
7. Circular Singly Linked List
7.1 Insertion at End
Node* insertCircular(Node *last, int val) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = val;
if (last == NULL) {
newNode->next = newNode;
return newNode;
newNode->next = last->next;
last->next = newNode;
return newNode;
7.2 Deletion from Front
Node* deleteFrontCircular(Node *last) {
if (last == NULL || last->next == last) {
free(last);
return NULL;
Node *temp = last->next;
last->next = temp->next;
free(temp);
return last;
7.3 Display
void displayCircular(Node *last) {
if (last == NULL) return;
Node *temp = last->next;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != last->next);
printf("(back to head)\n");