Linked List

Linked List

implementation

Insertion, Deletion and Traversal on Linear Linked Lists, Doubly Linked List, Circular Linked List, Header nodes, Implementation of Stacks & Queues using linked list, Application - Polynomial manipulation, Dynamic memory management, Garbage Collection.

problem solving

Reverse a Linked List, Middle of the Linked List, Delete Node in a Linked List, Merge Two Sorted Linked List, Remove duplicates from sorted list, Intersection of two linked list, Linked List Cycle, Palindrome Linked List, Swapping Nodes in a Linked List, Odd Even Linked List, Remove nth node from Linked List, Add Two Numbers, Swap Nodes in Pairs, Split Linked List in Parts, Insertion sort on Linked List, Merge sort on Linked List, Copy list with random pointers, Remove zero sum from consecutive nodes from linked list, Merge k sorted Linked List, Reverse nodes in k group, Doubly Linked List, Adding a node at the front, at the end, after a node or before a node, Deleting a node from the front, from the end, after a node or before a node, Circular Doubly Linked List, Adding a node at the front, at the end, after a node or before a node, Deleting a node from the front, from the end, after a node or before a node, LRU Cache, LFU Cache

linked list

data structure

lists are used when size is not known, and because size is not specified at compile time, dynamically memory is allocated at runtime, where each memory block holds the address of the next memory block, because the runtime memory creation is not a contiguous memory block, so it cannot be accessed using indexes.

files stored in various folders in our computer, are internally implemented using linked lists, where each folder represents nodes in a list, containing files as data, and lists are used in various data structures for dynamic implementation, and even used for storing databases dynamically.

time complexity analysis

lists are more flexible for insertion and deletion, at beginning, at ending, or at the middle, the time complexity is always O(1) which is not the case with arrays, where only insertion at the end would be O(1) otherwise any other insertion in array would need shifting of all other elements, leading to O(n) time complexity.

but for traversal and accessing the element at a certain index, arrays are much preferred because elements are easily accessed using indexes in O(1), which is unlikely the case for linkedlist, where each previous node has to be accessed to reach the next node, leading to O(n) time complexity.

memory structure

lists are stored in a sequential and orderly manner, each node connected to the other, dynamically, like a chain of tasks, where each task depends on its previous task, and we as a person checking off the list of tasks one by one in the same written order, similarly the head pointer is updated to focus on the next node accordingly.

whereas arrays are stored in a single contiguous memory block, like letting someone know we can only do these number of tasks, where the number is the limited storage capacity of the array, necessary to be given at compile time, so an array memory is unlikely to handle uncertainty, if more tasks had to be assigned according to the real-time situations.

node structure

struct node{

int data;

struct node *next;

}

a typical node stores some data, and the address to the next node, which is also of type node,

in order to access the whole memory block, the pointer has to be of the type of node it is pointing to.

head pointer

a linked list is handled using a single pointer, we say, head, which stores the reference to the first node of the list, and is used for insertion and deletion operations of the list, and the last node of the list stores a null address, where the null terminating address of the last node is very crucial for traversal of the list.

linked list operations

insertion and deletion can be at beginning, middle, end, so there is a function for each of these operations,

and there are no overflow errors as list is dynamic, but there certainly will be underflow errors while deletion if the list is empty.

insert_at_beg( head , e )

create node node n

store data n.data = e

node points to head of next n.next = head

head points to node head = n

delete_at_beg( head )

underflow condition if( head == null )

return underflow error

store node in temp temp = head

move head to next node head = head.next

get item before deleting node e = temp.data

free node memory free(temp)

insert_at_end( head , e )

create new node node n

store data in node n.data = e

make last node null n.next = null

if list is empty if( head == null )

head = n

else

create temp node to traverse node temp = head

traverse till last node while( temp.next != null )

temp = temp.next

connect new node at end temp.next = n

delete_at_end( head )

underflow condition if( head == null )

return underflow error

create temp node to traverse node temp = head

if single node present if( temp.next == null )

head == null

e = temp.data

free(temp)

else

traverse till second last node while( temp.next.next != null )

temp = temp.next

store last node in new_temp node new_temp = temp.next

get item at last node e = new_temp.data

make second last node null temp.next = null

delete the last node free(new_temp)

insert_at_middle( head , pos , e )

if pos is negative or zero if( pos <= 0 )

return wrong pos

create temp node to traverse node temp = head

create new_temp to traverse till pos - 1 node prev_temp = head

create a counter to count till pos count = 0

traverse till reaching pos while( count != pos )

prev_temp = temp

temp = temp.next

count++

if pos not found while traversing till last node if( temp == null )

return out of bound error

create a new node node n

store data into new node n.data = e

insert at middle of new_temp and temp prev_temp.next = n

n.next = temp

delete_at_middle( head , pos )

if pos is negative or zero if( pos <= 0 )

return wrong pos

underflow condition if( head == null )

return underflow error

create prev_temp node to traverse till pos - 1 node prev_temp = head

create temp node to traverse till pos node temp = head

create next_temp node to traverse till pos + 1 node next_temp = head

create counter to count till pos count = 0

traverse till reaching pos while( count != pos )

prev_temp = temp

temp = temp.next

if pos not found while traversing till last node if( temp == null )

return out of bound error

updated next_temp later to avoid segmentation fault next_temp = temp.next

count++

get item at pos e = temp.data

connect prev_temp to next_temp prev_temp.next = next_temp

delete the middle node free(temp)

Single linked list implementation in c,

#include <stdio.h>
#include <stdlib.h>
typedefstructnode{
int data;
structnode* next;
} NODE;
typedefstructlist{
NODE* head;
} LINKED_LIST;
voidinitialize(LINKED_LIST *l){
l->head = NULL;
}
voidinsert_at_beg(LINKED_LIST *l, int e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
newnode->next = l->head;
l->head = newnode;
}
intdelete_at_beg(LINKED_LIST *l){
if( l->head == NULL ){
printf("underflow");
return-1;
} else{
NODE* temp = l->head;
l->head = l->head->next;
int e = temp->data;
free(temp);
return e;
}
}
voidinsert_at_end(LINKED_LIST *l, int e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
newnode->next = NULL;
if(l->head == NULL){
l->head = newnode;
return;
} else {
NODE* temp = l->head;
while( temp->next != NULL ){
temp = temp->next;
}
temp->next = newnode;
}
}
intdelete_at_end(LINKED_LIST *l){
if( l->head == NULL ){
printf("underflow");
return-1;
} else {
NODE* temp = l->head;
if( temp->next == NULL ){
int e = temp->data;
l->head = NULL;
free(temp);
return e;
}
while( temp->next->next != NULL ){
temp = temp->next;
}
NODE* new_temp = temp->next;
int e = new_temp->data;
temp->next = NULL;
free(new_temp);
return e;
}
}
voidinsert_at_middle(LINKED_LIST *l, int pos, int e){
if( pos <= 0 ){
printf("wrong pos");
return;
}
NODE* temp = l->head;
NODE* prev_temp = l->head;
int count = 0;
while( count != pos ){
prev_temp = temp;
temp = temp->next;
count++;
if( temp == NULL ){
printf("out of bound error");
return;
}
}
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
prev_temp->next = newnode;
newnode->next = temp;
}
intdelete_at_middle(LINKED_LIST *l, int pos){
if( pos <= 0 ){
printf("wrong pos");
return-1;
}
if( l->head == NULL ){
printf("underflow");
return-1;
} else {
NODE* prev_temp = l->head;
NODE* temp = l->head;
NODE* next_temp = l->head;
int count = 0;
while( count != pos ){
prev_temp = temp;
temp = temp->next;
if( temp == NULL ){
printf("out of bound error");
return-1;
}
next_temp = temp->next;
count++;
}
int e = temp->data;
prev_temp->next = next_temp;
free(temp);
return e;
}
}
voidprint_list(LINKED_LIST *l){
if( l->head == NULL ){
return;
} else {
NODE* temp = l->head;
while( temp->next != NULL ){
printf("%d->", temp->data);
temp = temp->next;
}
printf("%d", temp->data);
printf("\n");
}
}
intmain(){
LINKED_LIST l;
initialize(&l);
insert_at_beg(&l, 10);
insert_at_beg(&l, 20);
printf("Initial List: ");
print_list(&l);
insert_at_end(&l, 30);
insert_at_end(&l, 40);
printf("After inserting elements: ");
print_list(&l);
printf("Deleted from end: %d\n", delete_at_end(&l));
printf("Deleted from beginning: %d\n", delete_at_beg(&l));
insert_at_middle(&l, 1, 25);
printf("After inserting 25 at position 1: ");
print_list(&l);
printf("Deleted from middle position 1: %d\n", delete_at_middle(&l, 1));
printf("Final List: ");
print_list(&l);
return0;
}


Output:
Initial List: 20->10
After inserting elements: 20->10->30->40
Deleted from end: 40
Deleted from beginning: 20
After inserting 25 at position 1: 10->25->30
Deleted from middle position 1: 25
Final List: 10->30

doubly linked list

a doubly linked list has two pointers for each node, a next pointer as usual, and a previous pointer as a new addition, with a single head pointer as usual, however, as last node of next is always null, similarly the previous of first node is always null, doubly lists are used to overcome the singular direction traversal of a singly list, so that traversal can be done back and forth easily.

node structure
struct node{
int data;
struct node* prev;
struct node* next;
};
doubly list operations
insert_at_beg(head, e)
create a node node n
connect node to list n.next = head
n.prev = null
add data to node n.data = e
connect backwards next node if( n.next != null )
n.next.prev = n
update head to new node head = n
delete_at_beg( head )
underflow condition if( head == null )
return underflow error
create temp node node temp = head
store data e = temp.data
update head to next node head = head.next
discard backwards connection head.prev = null
remove the node free(temp)


insert_at_end(head,e)
create node node n
n.data = e
n.next = null
if list is empty if( head == null )
head = n
n.prev = null
else
create a temp node node temp = head
traverse till last node while( temp.next != null )
temp = temp.next
update pointers temp.next = n
n.prev = temp


delete_at_end(head)
underflow condition if( head == null )
return underflow error
create a temp node node temp = head
if single node present if( head.next == null )
e = temp.data
head = null
free(temp)
else
create a prev_temp node node prev_temp = head
traverse till we reach last node while( temp.next != null )
prev_temp = temp
temp = temp.next
make previous node point to null prev_node.next = null
store data from node e = temp.data
remove node free(temp)


insert_at_middle(head, pos, e)
if pos is negative or zero if( pos <= 0 )
return wrong pos
create a temp node node temp = head
create a prev_node node prev_temp = head
create a counter count = 0
traverse till reach middle node while( count != pos )
prev_temp = temp
temp = temp.next
count++
if pos is greater than size of list if( temp == null )
return out of bound error
create a new node node n
store data n.data = e
insert node in middle prev_temp.next = n
temp.prev = n
update node pointers n.prev = prev_temp
n.next = temp


delete_at_middle(head, pos)
if pos is negative or zero if( pos <= 0 )
return wrong pos
underflow condition if( head == null )
return underflow error

create prev_temp node to traverse till pos - 1 node prev_temp = head

create temp node to traverse till pos node temp = head

create next_temp node to traverse till pos + 1 node next_temp = head

create counter to count till pos count = 0

traverse till reaching pos while( count != pos )

prev_temp = temp

temp = temp.next

if pos not found while traversing till last node if( temp == null )

return out of bound error

updated next_temp later to avoid segmentation fault next_temp = temp.next

count++

get the item e = temp.data
if last node if( temp.next == null )
prev_temp.next = null
free(temp)
else
update pointers prev_temp.next = next_temp
next_temp.prev = prev_temp
free(temp)
doubly linked list implementation in c,
#include <stdio.h>
#include <stdlib.h>
typedefstructnode{
int data;
structnode* next;
structnode* prev;
} NODE;
typedefstructlist{
NODE* head;
} LINKED_LIST;
voidinitialize(LINKED_LIST *l){
l->head = NULL;
}
voidinsert_at_beg(LINKED_LIST *l, int e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->next = l->head;
newnode->prev = NULL;
newnode->data = e;
if(newnode->next != NULL){
newnode->next->prev = newnode;
}
l->head = newnode;
}
intdelete_at_beg(LINKED_LIST *l){
if( l->head == NULL ){
printf("underflow");
return-1;
} else{
NODE* temp = l->head;
l->head = l->head->next;
l->head->prev = NULL;
int e = temp->data;
free(temp);
return e;
}
}
voidinsert_at_end(LINKED_LIST *l, int e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
newnode->next = NULL;
if(l->head == NULL){
l->head = newnode;
newnode->prev = NULL;
return;
} else {
NODE* temp = l->head;
while( temp->next != NULL ){
temp = temp->next;
}
temp->next = newnode;
newnode->prev = temp;
}
}
intdelete_at_end(LINKED_LIST *l){
if( l->head == NULL ){
printf("underflow");
return-1;
} else {
NODE* temp = l->head;
if( l->head->next == NULL ){
int e = temp->data;
l->head = NULL;
free(temp);
return e;
}
NODE* prev_temp = l->head;
while( temp->next != NULL ){
prev_temp = temp;
temp = temp->next;
}
prev_temp->next = NULL;
int e = temp->data;
free(temp);
return e;
}
}
voidinsert_at_middle(LINKED_LIST *l, int pos, int e){
if( pos <= 0 ){
printf("wrong pos");
return;
}
NODE* temp = l->head;
NODE* prev_temp = l->head;
int count = 0;
while( count != pos ){
prev_temp = temp;
temp = temp->next;
count++;
if( temp == NULL ){
printf("out of bound error");
return;
}
}
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
prev_temp->next = newnode;
temp->prev = newnode;
newnode->prev = prev_temp;
newnode->next = temp;
}
intdelete_at_middle(LINKED_LIST *l, int pos){
if( pos <= 0 ){
printf("wrong pos");
return-1;
}
if( l->head == NULL ){
printf("underflow");
return-1;
} else {
NODE* prev_temp = l->head;
NODE* temp = l->head;
NODE* next_temp = l->head;
int count = 0;
while( count != pos ){
prev_temp = temp;
temp = temp->next;
if( temp == NULL ){
printf("out of bound error");
return-1;
}
count++;
next_temp = temp->next;
}
int e = temp->data;
if( temp->next == NULL ){
prev_temp->next = NULL;
free(temp);
return e;
} else {
prev_temp->next = next_temp;
next_temp->prev = prev_temp;
free(temp);
return e;
}
}
}
voidprint_list(LINKED_LIST *l){
if( l->head == NULL ){
return;
} else {
NODE* temp = l->head;
while( temp->next != NULL ){
printf("%d->", temp->data);
temp = temp->next;
}
printf("%d", temp->data);
printf("\n");
}
}
intmain(){
LINKED_LIST l;
initialize(&l);
insert_at_beg(&l, 10);
insert_at_beg(&l, 20);
printf("Initial List: ");
print_list(&l);
insert_at_end(&l, 30);
insert_at_end(&l, 40);
printf("After inserting elements: ");
print_list(&l);
printf("Deleting from empty list: %d\n", delete_at_beg(&l));
printf("Deleting from end of empty list: %d\n", delete_at_end(&l));
insert_at_middle(&l, -1, 25);
insert_at_middle(&l, 5, 25);
printf("\n");
insert_at_beg(&l, 50);
insert_at_end(&l, 60);
printf("After inserting more elements: ");
print_list(&l);
printf("Deleted from end: %d\n", delete_at_end(&l));
printf("Deleted from beginning: %d\n", delete_at_beg(&l));
insert_at_middle(&l, 1, 25);
printf("After inserting 25 at position 1: ");
print_list(&l);
printf("Deleted from middle position: %d\n", delete_at_middle(&l, 2));
printf(" %d\n", delete_at_middle(&l, 10));
printf(" %d\n", delete_at_middle(&l, -1));
printf("Final List: ");
print_list(&l);

return0;
}


output:
Initial List: 20->10
After inserting elements: 20->10->30->40
Deleting from empty list: 20
Deleting from end of empty list: 40
wrong posout of bound error
After inserting more elements: 50->10->30->60
Deleted from end: 60
Deleted from beginning: 50
After inserting 25 at position 1: 10->25->30
Deleted from middle position: 30
out of bound error -1
wrong pos -1
Final List: 10->25









Circular Linked Lists

a circular linked list, is similar to a singly list, just that the null terminating pointer representing the end of the list, is now replaced by the address of the first node, leading to a uni-directional circular kind of list, but to be cautious not to be caught in a infinite loop traversing the list, for that we take head pointer as our indicator that the list has been fully traversed.

node structure

struct node{

int data;

struct node* next;

}

circular linked list operations,

insert_at_beg( head, e )

create a new node node n

add data n.data = e

if list empty if( head == null )

head = n

n.next = head

else

create a temp node node temp = head

traverse till end while( temp.next != head )

temp = temp.next

connect to list n.next = head

update head to first node head = n

update circular pointer temp.next = head

delete_at_beg(head)

check empty if( head == null )

return underflow error

create a temp node node temp = head

if only one node if( temp.next == temp )

e = temp.data

head = null

free(temp)

else

traverse till end while( temp.next != head )

temp = temp.next

create pop_temp node node pop_temp = head

get the item e = pop_temp.data

move head forwards head = head.next

update circular pointer temp.next = head

remove the node free(pop_temp)

#include <stdio.h>
#include <stdlib.h>
typedefstructnode{
int data;
structnode* next;
} NODE;
typedefstructlist{
NODE* head;
} LINKED_LIST;
voidinsert_at_beg(LINKED_LIST *l, int e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->data = e;
if(l->head == NULL) {
l->head = newnode;
newnode->next = l->head;
} else {
NODE* temp = l->head;
while(temp->next != l->head){
temp = temp->next;
}
newnode->next = l->head;
l->head = newnode;
temp->next = l->head;
}
}

intdelete_at_beg(LINKED_LIST *l){
if(l->head == NULL){
printf("underflow");
return-1;
} else {
NODE* temp = l->head;
if(temp->next == temp){
int e = temp->data;
l->head = NULL;
free(temp);
return e;
} else{
while(temp->next != l->head){
temp = temp->next;
}
NODE* pop_temp = l->head;
int e = pop_temp->data;
l->head = l->head->next;
temp->next = l->head;
free(pop_temp);
return e;
}
}
}
voidprintlist(LINKED_LIST *l){
if(l->head == NULL){
printf("list not found\n");
return;
} else{
NODE* temp = l->head;
while(temp->next != l->head){
printf("%d->", temp->data);
temp = temp->next;
}
printf("%d", temp->data);
printf("\n");
}
}
intmain(){
LINKED_LIST l;
l.head = NULL;
insert_at_beg(&l, 10);
insert_at_beg(&l, 20);
insert_at_beg(&l, 30);
printlist(&l);
delete_at_beg(&l);
delete_at_beg(&l);
printlist(&l);
return0;
}
output:
30->20->10
10



Header Nodes

there is nothing special in its implementation, just that the header pointer we were using till now is treated as a dummy node and included as a part of the linked list traversal, however, that will consume more memory but is helpful for storing meta data about the list itself, such as the current size of list, and these header nodes are very helpful in the cases of a circular linked list, where it can be used as an indicator to end the loop in a circular list.

types of header nodes,

• Grounded Header Linked List

• Circular Header Linked List

• Two-way Linked List

• Circular Two-way Linked List

advantages & disadvantages of using header linked lists,

advantages

The header node allows access to all the nodes in the list. Polynomials are often stored in memory as header-linked lists. The size can be increased during runtime. It allocates memory for the actual data nodes, reducing memory waste compared to arrays. This stores global information about the list, such as the total number of nodes, maximum value, or minimum value.

disadvantages

Header-linked lists require additional memory for storing pointer information alongside the actual data, leading to increased memory usage. Searching for an element in a Header Linked List can be time-consuming, as it may involve traversing from the start to the point of interest, which is not efficient for large lists. It can be difficult to traverse a linked list, and it can take a long time to get to a node. It can be challenging to reverse-traverse a linked list.

implementation of stacks using linked lists,
#include <stdio.h>
#include <stdlib.h>
structnode{
int data;
structnode *next;
};
voidpush(struct node **head, int e){

structnode *newnode = (structnode *)malloc(sizeof(structnode));
newnode->data = e;

newnode->next = *head;
*head = newnode;
}
intpop(struct node **head){
if( *head == NULL){
printf("underflow");
return0;
}
structnode *temp = *head;

int e = temp->data;
*head = (*head)->next;

free(temp);
return e;
}
intmain(){

structnode *top = NULL;

push(&top, 5);
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
push(&top, 10);
push(&top, 20);
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
return0;
}

output:
5
underflow 0
20
10
underflow 0



queues implementation in c using linkedlist,
#include <stdio.h>
#include <stdlib.h>
typedefstructNode{
int data;
structNode* next;
} Node;
typedefstructQueue{
Node *front, *rear;
} Queue;
voidinitialize(Queue *q){
q->front = NULL;
q->rear = NULL;
}
voidenqueue(Queue *q, int e){
Node* new = (Node*)malloc(sizeof(Node));
new->next = NULL;
new->data = e;
if( q->front == NULL){
q->front = new;
q->rear = new;
} else {
q->rear->next = new;
q->rear = new;
}
}
intdequeue(Queue *q){
if( q->front == NULL ){
printf("underflow");
return-1;
} else {
Node *temp = q->front;
int e = q->front->data;
q->front = q->front->next;
if( q->front == NULL ){
q->rear = NULL;
}
free(temp);
return e;
}
}
intmain(){
Queue q;
initialize(&q);
enqueue(&q, 10);
enqueue(&q, 20);
printf(" %d ", dequeue(&q));
printf(" %d ", dequeue(&q));
printf(" %d ", dequeue(&q));
return0;
}


polynomial manipulation using linked lists to be covered later.