Linked List

A linked list is a linear data structure which can store a collection of "nodes"
connected together via links i.e. pointers. Linked lists nodes are not stored at a
contiguous location, rather they are linked using pointers to the different
memory locations. A node consists of the data value and a pointer to the
address of the next node within the linked list.

A linked list is a dynamic linear data structure whose memory size can be
allocated or de-allocated at run time based on the operation insertion or
deletion, this helps in using system memory efficiently. Linked lists can be used
to implment various data structures like a stack, queue, graph, hash maps, etc.

A linked list starts with a head node which points to the first node. Every node
consists of data which holds the actual data (value) associated with the node
and a next pointer which holds the memory address of the next node in the
linked list. The last node is called the tail node in the list which points
to null indicating the end of the list.

Linked List:

• Data Structure: Non-contiguous

• Memory Allocation: Typically allocated one by one to individual

elements

• Insertion/Deletion: Efficient

• Access: Sequential
Array:

• Data Structure: Contiguous

• Memory Allocation: Typically allocated to the whole array

• Insertion/Deletion: Inefficient

• Access: Random

Types of Linked List:

❖Singly linked lists:

Singly linked lists contain two "buckets" in one node; one bucket holds
the data and the other bucket holds the address of the next node of the
list. Traversals can be done in one direction only as there is only a single
link between two nodes of the same list.

Common Operation in Singly Linked List ::

• Traversal : Traversing singly linked list

(Display all nodes)

Algorithm

[Link] from head

[Link] until the current node becomes NULL:
[Link] current node's data
[Link] to the next node
[Link] when the list ends
 • Insertion : At the beginning, At the end and At a specific position

A. Insert at Beginning

Algorithm

[Link] a new node

[Link] newNode->next = head
[Link] head = newNode

B. Insert at End

Algorithm

1. Create a new node

2. If list is empty: head = newNode
3. Else traverse to last node
4. Set last node’s next = newNode

C. Insert at a Specific Position

Algorithm

1. Traverse until position − 1

2. Link newNode to next node
3. Link previous node to newNode

• Deletion : From beginning, From end and From a specific

position

[Link] from Beginning

Algorithm

[Link] if list is empty

[Link] head to next node
[Link] old head
[Link] from End

Algorithm

[Link] list empty: return

[Link] only one node: make head NULL
[Link] traverse to second last node
4. Make its next = NULL
5. Free last node

B. Delete at Specific Position

Algorithm

[Link] to pos−1
[Link] pointer to node to delete
[Link] previous node to next node
[Link] delete node

• Searching : Find whether a given key exists in the list

Algorithm

[Link] from head

[Link] each node data with key
[Link] match found → return position
[Link] return -1

❖ Doubly Linked Lists

Doubly Linked Lists contain three "buckets" in one node; one bucket holds the
data and the other buckets hold the addresses of the previous and next nodes
in the list. The list is traversed twice as the nodes in the list are connected to
each other from both sides.
Common Operation in Doubly Linked List :

• Traversal : Display Linked List Elements

a. Forward Traversal in Doubly Linked List

Algorithm
[Link] a temporary pointer ptr and copy the head pointer into it.
[Link] through the list using a while loop.
[Link] moving the value of temp pointer variable ptr to ptr->next until the last
node whose next part contains null is found.
[Link] each iteration of the loop, perform the desired operation.

b. Reverse Traversal in Doubly Linked List

[Link] a temporary pointer ptr and copy the tail pointer into it.
[Link] through the list using a while loop.
[Link] moving the value of temp pointer variable ptr to ptr->prev until
the first node whose prev part contains null is found.
[Link] each iteration of the loop, perform the desired operation

• Insertion : At the Beginning, At the End and At the specific position

a. Insertion at the Beginning of the Doubly Linked List

Algorithm

[Link] a newNode with data field assigned the given value.

[Link] the list is empty:
[Link] newNode->next to NULL.
[Link] newNode->prev to NULL.
[Link] the head pointer to point to newNode.
[Link] the list is not empty:
[Link] newNode->next to head.
[Link] newNode->prev to NULL.
[Link] head->prev to newNode.
[Link] the head pointer to point to newNode.

b. Insertion at the End of the Doubly Linked List

Algorithm

[Link] a newNode with data field assigned the given value.

[Link] the list is empty:
[Link] newNode->next to NULL.
[Link] newNode->prev to NULL.
[Link] the head pointer to point to newNode.
[Link] the list is not empty:
[Link] the list to find the last node (where last->next == NULL).
[Link] last->next to newNode.
[Link] newNode->prev to last.
[Link] newNode->next to NULL.

b. Insertion in the Middle of the Doubly Linked List

Algorithm

[Link] a newNode.
[Link] the size of the list to ensure the position is within valid bounds.
[Link] the position is 0 (or 1 depending on your indexing):
o Use the insertion at the beginning approach.
[Link] the position is equal to the size of the list:
o Use the insertion at the end approach.
[Link] the position is valid and not at the boundaries:
o Traverse the list to find the node immediately before the desired
insertion point (prevNode).
o Set newNode->next to prevNode->next.
o Set newNode->prev to prevNode.
o If prevNode->next is not NULL, set prevNode->next->prev to
newNode.
o Set prevNode->next to newNode.

• Deletion : From the Beginning, From End and From a Specific Position

a. Deletion at the Beginning of the Doubly Linked List

Algorithm

[Link] if the List is Empty: If true, there's nothing to delete.

[Link] if the List Contains Only One Node:
Set head to NULL.
Free the memory of the node.
[Link] the List Contains More Than One Node:
Update head to head->next.
Set the prev of the new head to NULL.
Free the memory of the old head.
Deletion at the End of the Doubly Linked List

Algorithm

[Link] if the List is Empty: If true, there's nothing to delete.

[Link] the List is Not Empty:
o Traverse to the last node using a loop.
o Check if the last node is the only node (head->next == NULL):
o Update head to NULL.
o If more than one node:
o Set the next of the second last node (last->prev) to NULL.
o Free the memory of the last node.

Deletion at a Specific Position in Doubly Linked List

Algorithm

Check Position Validity:

[Link] position is 0 (or 1 depending on indexing), use

deletion at the beginning.

[Link] position is the size of the list, use deletion at the end.

[Link], proceed with the middle deletion.

Traverse to the Specified Position:

[Link] a loop to reach the node (delNode) at the desired

position.

[Link] delNode is the first node, adjust head.

[Link] not, adjust delNode->prev->next and delNode-

>next->prev if delNode->next is not NULL.

Free the Memory:

[Link] the node to be delete.

 ❖Circular Linked Lists
Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected,
the traversal in this linked list will go on forever until it is broken.

Common Operation in Circular Linked List :

• Insertion : At the Beginning, At the End and At a Specific Position

Insertion at the beginning:

Algorithm

[Link] a new node

allocate memory for new Node
assign the data to the new Node
[Link] the address of the current first node in the new Node (i.e.
pointing the new Node to the current first node)
[Link] the last node to new Node (i.e making new Node as head)

Insertion at a specific position/in between the nodes:

Algorithm

1. travel to the node given i.e. node 1

2. point the next of new Node to the node next to node 1

3. store the address of the new Node at the next of node 1.

Insertion at the end

1. store the address of the head node to the next of new Node (making
new Node the last node)

2. point the current last node to new Node

3. make new Node as the last node

• Deletion : Removal from different positions

If it's the only node

1. free the memory occupied by the node

2. store NULL in the last

If it's the last node

1. find the node before the last node (let it be temp)

2. store the address of the node next to the last node in temp

3. free the memory of the last

4. make temp the last node

If it's any other node

1. travel to the node to be deleted (here we are deleting node two)

2. Let the node before node two be temp

3. store the address of the node next to two in temp

4. free the memory of two

 Program for stack using linked list

#include <stdio.h>
#include <stdlib.h>

// Node structure for the linked list

struct Node {
int data;
struct Node* next;
};

struct Node* top = NULL; // Global pointer to the top of the stack

// Push operation: Adds an element to the top of the stack

void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Stack Overflow (Memory allocation failed)\n");
return;
}
newNode->data = value;
newNode->next = top; // New node points to the previous top
top = newNode; // Update top to the new node
printf("%d pushed to stack\n", value);
}

// Pop operation: Removes and returns the top element

int pop() {
if (top == NULL) {
printf("Stack Underflow (Stack is empty)\n");
return -1; // Or throw an error
}
struct Node* temp = top;
int poppedValue = temp->data;
top = top->next; // Move top to the next node
free(temp); // Free the memory of the popped node
return poppedValue;
}

// Peek operation: Returns the top element without removing it

int peek() {
if (top == NULL) {
printf("Stack is empty. No top element.\n");
return -1; // Or throw an error
}
return top->data;
}

// Check if the stack is empty

int isEmpty() {
return top == NULL;
}

Program for queue using stack

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the linked list

struct Node {
int data;
struct Node* next;
};

// Define the structure for the Queue

struct Queue {
struct Node *front; // Pointer to the front of the queue
struct Node *rear; // Pointer to the rear of the queue
};

// Function to initialize an empty queue

struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
if (q == NULL) {
perror("Memory allocation failed for Queue");
exit(EXIT_FAILURE);
}
q->front = NULL;
q->rear = NULL;
 return q;
}

// Function to check if the queue is empty

int isEmpty(struct Queue* q) {
return (q->front == NULL);
}

// Function to add an element to the rear of the queue (enqueue)

void enqueue(struct Queue* q, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
perror("Memory allocation failed for new Node");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;

if (isEmpty(q)) {
q->front = newNode;
q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
printf("%d enqueued to queue.\n", data);
}

// Function to remove an element from the front of the queue (dequeue)

int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1; // Indicate an error or empty queue
}
struct Node* temp = q->front;
int dequeuedData = temp->data;
q->front = q->front->next;

// If the queue becomes empty after dequeue, update rear as well

if (q->front == NULL) {
 q->rear = NULL;
}
free(temp);
printf("%d dequeued from queue.\n", dequeuedData);
return dequeuedData;
}

// Function to get the front element of the queue without removing it (peek)
int peek(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty. Cannot peek.\n");
return -1;
}
return q->front->data;
}

// Function to display the elements of the queue

void displayQueue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return;
}
struct Node* current = q->front;
printf("Queue elements: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// Main function to test the queue implementation

int main() {
struct Queue* myQueue = createQueue();

enqueue(myQueue, 10);
enqueue(myQueue, 20);
enqueue(myQueue, 30);
displayQueue(myQueue);
 printf("Front element: %d\n", peek(myQueue));

dequeue(myQueue);
displayQueue(myQueue);

dequeue(myQueue);
dequeue(myQueue);
displayQueue(myQueue);

dequeue(myQueue); // Attempt to dequeue from an empty queue

// Free the queue structure itself

free(myQueue);

return 0;
}