Data Structures and Algorithms
Linked List
Prepared By : Vaishali Koria Data Structure and Algorithms 1
Linked List
• Linked list is a linear data structure.
• List of elements are logically continuous, but not necessarily physical.
Prepared By : Vaishali Koria Data Structure and Algorithms 2
Array vs Linked List
• Consider the list to store the roll numbers of three topper students: 25,67,89
Consider we have this kind of memory available for storage of roll numbers.
Addresses Value
If we use array to store data minimum 3*2 = 6 bytes are
1000
required, which must be contiguous. (if size of integer is 2
1001
bytes)
1002
1003
1004 ////////// Enough memory locations are available to store the list but
1005 contiguous 6 bytes are not available. So memory allocation will
1006 be failed if we want to use the array.
1007
1008 For the solution of this, we can use linked list.
1009 //////////
1010
1011
1012
Prepared By : Vaishali Koria Data Structure and Algorithms 3
Array vs Linked List
• Consider the same list to store the roll numbers of three topper students: 25,67,89
Addresses Value
1000
25 Same thing we can represent as follows too:
1001
1002
1005
25 1005 67 1010 89 NULL
1003
1004 ////////// 1000 1005 1010
1005
1006
67
1007
1008 1010
1009 //////////
1010
1011
89
1012
NULL
1013
Prepared By : Vaishali Koria Data Structure and Algorithms 4
Linked List
Consider the list to store the roll numbers of three topper students: 25,67,89
Consider this as a node
25 2000 Linked list will be :
25 2000 67 3000 89 NULL
Data Address of
next data Head= 1000 2000 3000
Address of
this node is Head pointer will keep the address
suppose of first node of the linked list.
1000
This is called Singly Linked List.
Prepared By : Vaishali Koria Data Structure and Algorithms 5
Singly Linked List operations:
1. Insert at front of the linked list: (Insert_at_front)
Step 1 : Create a new node structure
struct node
Data Pointer to next node
{
int data;
struct node * next;
} *head = NULL;
Step 2 : Allocate Address
struct node* create(int v)
{
struct node* new1;
new1 = (struct node*)malloc(sizeof(struct node));
new1->data = v;
new1-> next = NULL;
return new1; 10 NULL
}
new1= 1000 (assumed)
Consider call : Create(10)
Prepared By : Vaishali Koria Data Structure and Algorithms 6
Singly Linked List operations:
1. Insert at front of the linked list: (Insert_at_front)
Step 3 : Insert a new node in the linked list
Case 1: No node in the linked list
struct node* Insert_at_front(int v)
{
struct node* new1; 10 NULL
new1 = create(v);
if (head == NULL)
{ head = new1= 1000
head = new1;
}
}
Consider call : insert_at_front(10);
Prepared By : Vaishali Koria Data Structure and Algorithms 7
Singly Linked List operations:
1. Insert at front of the linked list: (Insert_at_Front)
Step 3 : Insert a new node in the linked list
Case 2: insert node at front in the existing linked list with nodes Existing linked list:
struct node* Insert_at_front(int v) 10 NULL
{
struct node* new1; 8 NULL
new1 = create(v); head = 1000
if (head == NULL) new1 = 1500
{
head = new1;
}
else
{
new1next= head; 8 1000 10 NULL
head= new1; head = 1500 1000
}
}
Consider call : Insert_at_front(8);
Prepared By : Vaishali Koria Data Structure and Algorithms 8
Singly Linked List operations:
2. Insert at end of the linked list: (Insert_at_end)
Case 1 will be similar to previous example. 8 1000 10 NULL
Case 2: insert node at end in the existing linked list with nodes head = 1500 1000
15 NULL
i. Create new node: new1= 3000
8 1000 10 3000 15 NULL
ii. This node should be inserted like
head = 1500 1000 new1=3000
this:
iii. We need to change the next part of node with address 1000.
1000->next = new1(3000)
How can we get the address of last node?
- Last node’s feature is : its next field is NULL. That we can use to find the address of last node.
Prepared By : Vaishali Koria Data Structure and Algorithms 9
Singly Linked List operations:
2. Insert at end of the linked list: (Insert_at_end)
Case 2: insert node at end in the existing linked list with nodes
iv. Find the address of last node:
8 1000 10 NULL 15 NULL
struct node * t = head;
head = 1500 1000 new1= 3000
while(t->next != NULL)
{ 1. t= 1500 1. t= 1000
t = t-> next;
2. t->next != NULL 2. t->next == NULL
}
3. t= t->next So, t= 1000 (address of last node)
iv. Insert node at end
8 1000 10 3000 15 NULL
t-> next = new1;
head = 1500 1000 3000
Prepared By : Vaishali Koria Data Structure and Algorithms 10
Singly Linked List operations:
3. Delete from front
Case 1: No node in the linked list
if(head== NULL)
{
printf(“No node in the list to delete”);
}
Existing linked list:
Case 2: Delete Front Node 8 1000 10 3000 15 NULL
head = 1500 1000 3000
Resultant linked list should be:
head = head -> next; 10 3000 15 NULL
head=1000 3000
Prepared By : Vaishali Koria Data Structure and Algorithms 11
Singly Linked List operations:
4. Delete last node (Delete from end)
Case 2: Delete last Node Existing linked list:
- Reach to the last node. 8 1000 10 3000 15 NULL
struct node * t = head , *pred; head = 1500 1000 3000
while(t->next != NULL) t= 1500 t= 1000 t= 3000
{ t->next=1000!=NULL t->next=3000!=NULL t->next==NULL
pred = t; // before going to next node, store the address pred=t=1500 pred=t=1000
of previous node in pred
t =t->next = 3000
t = t-> next; t =t->next = 1000
}
t= 3000 pred= 1000 Resultant linked list should be:
8 1000 10 NULL
pred->next = NULL; head = 1500 1000
Prepared By : Vaishali Koria Data Structure and Algorithms 12
Thank You!!!
Prepared By : Vaishali Koria Data Structure and Algorithms 13
