Data structures -short notes

Module III
Linked List:

 Linked list is a collection of nodes or data elements logically connected to each

other.

 Whenever there is a need to add a new element to the list, a new node is created
and appended at the end of the list.
 An array is allocated fixed amount of memory space before a program is
executed.
 Thus, if there is a need at run time to store more data in the array than its
actual capacity, then there is no way of doing this.
 The linked list allows for dynamic allocation of memory space at runtime.
 Thus, there is no need to block memory space at compile time.
 Linked list is not constrained to be stored in adjacent memory locations as in
array.
Definition:
 Linked list is a collection of nodes stored in such a manner that each node points
at the next node in the list.
 Each node has two parts: data part and link part.
 The data part contains the data element while the link part contains the address of
the next node.
The implementation of linked list in C programming language, using structure can
be defined as
struct node
{
int data;
struct node *link;
};
The link is a pointer that contains the address to indicate the location of the
successor node. The link part of the last node of the list contains a NULL value
indicating the end of the list. The address of the first node in the list is indicated
by the pointer p.
 p
1000

1 2000 2 3000 3 NULL

1000 2000 3000

Comparison of linked list and array

Advantages of linked list over arrays
 An array is allocated fixed amount of memory space before a program is executed.
Thus, we need to allocate memory at compile time. This may lead to wastage of
memory. The linked list allows for dynamic allocation of memory space at runtime.

 Linked list is not constrained to be stored in adjacent memory locations as

in array.

Disadvantages of linked list over arrays

 Array is random access, which means it takes O(1) time to access any
element in the array. Linked list takes O(n) time to access an element in its
worst case.

Types of Linked list

Linked list is classified into the following types -

Singly-linked list - Singly linked list can be defined as the collection of an

ordered set of elements. A node in the singly linked list consists of two parts:
data part and link part. Data part of the node stores actual information that is to
be represented by the node, while the link part of the node stores the address of
its immediate successor.

Doubly linked list - Doubly linked list is a complex type of linked list in
which a node contains a pointer to the previous as well as the next node in the
 sequence. Therefore, in a doubly-linked list, a node consists of three parts:
node data, pointer to the next node in sequence (next pointer), and pointer to
the previous node (previous pointer).

Circular singly linked list - In a circular singly linked list, the last node of the
list contains a pointer to the first node of the list. We can have circular singly
linked list as well as circular doubly linked list.

Circular doubly linked list - Circular doubly linked list is a more complex
type of data structure in which a node contains pointers to its previous node as
well as the next node. Circular doubly linked list doesn't contain NULL in any
of the nodes. The last node of the list contains the address of the first node of
the list. The first node of the list also contains the address of the last node in its
previous pointer.

Operations performed on Linked list

The basic operations that are supported by a list are mentioned as follows –

o Insertion - This operation is performed to add an element into the list.

o Deletion - It is performed to delete an operation from the list.
o Display/Traversal - It is performed to display the elements of the list.
o Search - It is performed to search an element from the list using the given key.

Traverse a Linked List ( Displaying a Single Linked List)

Displaying the contents of a linked list is very simple. We keep moving the temp node
to the next one and display its contents.
 When temp is NULL, we know that we have reached the end of the linked list so we get
out of the while loop.

Algorithm

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.

Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the
last node

Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data --->
NULL).

void display()
{
if(head == NULL)
{
printf("\nList is Empty\n");
}
else
{
struct Node *temp = head;
printf("\n\nList elements are - \n");
while(temp->next != NULL)
{
printf("%d --->",temp->data);
temp = temp->next;
}
printf("%d --->NULL",temp->data);
}

 Insert operation-The insert operation in a linked list can be done to an empty

linked list and insertion to a non-empty linked list.

In the insertion operation to the empty linked list, we create a new node pointed
by the pointer temp and its data value is inserted to data part and link part set to
null.

Insertion to the non-empty linked list – initially the pointer temp points to the
first node in the list. The pointer temp is used to traverse along the list to reach the
end of the node.
You can add elements to either the beginning, middle or end of the linked list.

1. Insert at the beginning

 Allocate memory for new node

 Store data

 Change next of new node to point to head

 Change head to point to recently created node

Algorithm

Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.

Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

2. Insert at the End

 Allocate memory for new node

 Store data

 Traverse to last node

 Change next of last node to recently created node

Algorithm

Step 1 - Create a newNode with given value and newNode → next as NULL.

Step 2 - Check whether list is Empty (head == NULL).

 Step 3 - If it is Empty then, set head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

Step 5 - Keep moving the temp to its next node until it reaches to the last node in the
list (until temp → next is equal to NULL).

Step 6 - Set temp → next = newNode.

3. Insert at the specific location

 Allocate memory and store data for new node

 Traverse to node just before the required position of new node

 Change next pointers to include new node in between

Algorithm

Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

Step 5 - Keep moving the temp to its next node until it reaches to the node after which
we want to insert the newNode (until temp1 → data is equal to location, here location
is the node value after which we want to insert the newNode).

Step 6 - Every time check whether temp is reached to last node or not. If it is reached
to last node then display 'Given node is not found in the list!!! Insertion not
possible!!!' and terminate the function. Otherwise move the temp to next node.

Step 7 - Finally, Set 'newNode → next = temp → next' and

'temp → next = newNode'

 Delete operation: The delete operation removes an existing element from the linked list.

In a single linked list, the deletion operation can be performed in three ways. They are as
follows...

1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node
1. Deleting from Beginning of the list
Algorithm
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with head.
Step 4 - Check whether list is having only one node (temp → next == NULL)
Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.
2. Deleting from End of the list
Algorithm
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Check whether list has only one Node (temp1 → next == NULL)
Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node.
Repeat the same until it reaches to the last node in the list. (until temp1 →
next == NULL)
Step 7 - Finally, Set temp2 → next = NULL and delete temp1.
3. Deleting a Specific Node from the list
Algorithm
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to
the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its
next node.
Step 5 - If it is reached to the last node then display 'Given node not found in the
list! Deletion not possible!!!'. And terminate the function.
Step 6 - If it is reached to the exact node which we want to delete, then check whether
list is having only one node or not
Step 7 - If list has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 . ie free(temp1).
Step 8 - If list contains multiple nodes, then check whether temp1 is the first node in
the list (temp1 == head).
Step 9 - If temp1 is the first node then move the head to the next node (head = head
→ next) and delete temp1.
Step 10 - If temp1 is not first node then check whether it is last node in the list
(temp1 → next == NULL).
Step 11 - If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).
Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1
→ next and delete temp1 (free(temp1)).

Program to implement linked list

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

void insertAtBeginning(int);
void insertAtEnd(int);
void insertBetween(int,int,int);
void display();
void removeBeginning();
void removeEnd();
void removeSpecific(int);

struct Node
{
int data;
struct Node *next;
}*head = NULL;
void main()
{
int choice,value,choice1,loc1,loc2;
clrscr();
while(1){
mainMenu: printf("\n\n****** MENU ******\n1. Insert\n2. Display\n3. Delete\n
4. Exit\nEnter your choice: ");
 scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
while(1){
printf("Where you want to insert: \n1. At Beginning\n2. At End\n3. Betwee
n\nEnter your choice: ");
scanf("%d",&choice1);
switch(choice1)
{
case 1: insertAtBeginning(value);
break;
case 2: insertAtEnd(value);
break;
case 3: printf("Enter the value after which you want to insert: ");
scanf("%d%d",&item);
insertBetween(value,item);
break;
default: printf("\nWrong Input!! Try again!!!\n\n");
goto mainMenu;
}
goto subMenuEnd;
}
subMenuEnd:
break;
case 2: display();
break;
case 3: printf("How do you want to Delete: \n1. From Beginning\n2. From End\
n3. Spesific\nEnter your choice: ");
scanf("%d",&choice1);
switch(choice1)
{
case 1: removeBeginning();
 break;
case 2: removeEnd();
break;
case 3: printf("Enter the value which you wanto delete: ");
scanf("%d",&loc2);
removeSpecific(loc2);
break;
default: printf("\nWrong Input!! Try again!!!\n\n");
goto mainMenu;
}
break;
case 4: exit(0);
default: printf("\nWrong input!!! Try again!!\n\n");
}
}
}
void insertAtBeginning(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
newNode->next = head;
head = newNode;
}
printf("\nOne node inserted!!!\n");
}
void insertAtEnd(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
head = newNode;
else
{
struct Node *temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}
void insertBetween(int value, int loc1)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
struct Node *temp = head;
while(temp->data != item)
temp = temp->next;
newNode->next = temp->next;
 temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}
void removeBeginning()
{
if(head == NULL)
printf("\n\nList is Empty!!!");
else
{
struct Node *temp = head;
if(head->next == NULL)
{
head = NULL;
free(temp);
}
else
{
head = temp->next;
free(temp);
printf("\nOne node deleted!!!\n\n");
}
}
}
void removeEnd()
{
if(head == NULL)
{
printf("\nList is Empty!!!\n");
}
else
{
struct Node *temp1 = head,*temp2;
 if(head->next == NULL)
head = NULL;
else
{
while(temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
temp2->next = NULL;
}
free(temp1);
printf("\nOne node deleted!!!\n\n");
}
}
void removeSpecific(int delValue)
{
struct Node *temp1 = head, *temp2;
while(temp1->data != delValue)
{
if(temp1 -> next == NULL){
printf("\nGiven node not found in the list!!!");
goto functionEnd;
}
temp2 = temp1;
temp1 = temp1 -> next;
}
temp2 -> next = temp1 -> next;
free(temp1);
printf("\nOne node deleted!!!\n\n");
functionEnd:
}
void display()
 {
if(head == NULL)
{
printf("\nList is Empty\n");
}
else
{
struct Node *temp = head;
printf("\n\nList elements are - \n");
while(temp->next != NULL)
{
printf("%d --->",temp->data);
temp = temp->next;
}
printf("%d --->NULL",temp->data);
}
}
Linked list insertion algorithms – complexity
1. Insertion at beginning - O(1)
2. Insertion at end- O(n)
3. Insertion at middle- O(n)

In general the complexity of algorithm to insert a node into the linked list-O(n)
Linked list deletion algorithms – complexity
1. Deletion at beginning -O(1)
2. Deletion at end-O(n)
3. Deletion at middle-O(n)

In general the complexity of algorithm to delete a node into the linked list-O(n)

Circular linked list

The circular linked list is a list where the last node points to the first node of the
list. The link part of the last node contains the address of the first node in the list.
One of the main advantage of circular linked list is that it allows traversal of the complete list from
any of the node, which is not possible with singly linked lists.
 FIRST LAST
1000 3000

1 2000 2 3000 3 1000

1000 2000 3000

Algorithm to insert one node at the end in the circular linked list
Step1: Start
Step 2: Let first points to the first node and last points to the last
node in the linked list.
Step 3: Read the data for new node into d
Step 4: If first=NULL then go to step 5 else go to step 7
Step 5: Create a new node pointed by temp.
Step 5.1: Set temp->data= d
Step 5.2: Set first=last = temp.
Step 6: Set temp->link=first
Step 7: If first ≠ NULL then go to step 8
Step 8: Create a new node pointed by temp
Step 8.1: Set temp->data=d
Step 8.2: Set last->link=temp
Step 8.2: Set temp->link= first
Step 9: Set last= temp
Step 10: Display the data in the nodes of the linked list
Step 11: Stop

PROGRAM:
struct node
{ int data;
struct node *link;
};
 struct node *first=NULL;
struct node *last=NULL;
void insert(int item)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=item;
if(first==NULL)
{
first=last=temp;
temp->link=first;
}
else
{
}
}
void main()
{

last->link=temp;
temp->link=first;
last=temp;
int item;
printf("enter the data item\n");
scanf("%d",&item);
insert(item);

}
Doubly linked list
Each node in the doubly linked list has three parts: previous, data, next. The data
part contains the data element while the next and previous parts contains the
addresses of the next and previous nodes respectively.
The main advantage of a doubly linked list is that it allows both forward and backward
traversal.

The following code defines a node in the doubly linked list

struct node
{
int data;
struct node *next;
struct node *previous;
};
Insert operation: Insert operation in the doubly linked list is the same manner as a
singly linked list. The only exception is that the additional node pointer previous is
also required to be updated for the new node at the time of insertion.
Algorithm for insert function in doubly linked list - insert at end (data)

Step1: Start
Step 2: Let first points to the first node and last points to the last node in the linked list.
Step 3: Read the data for new node into d
Step 4: If first=NULL then go to step 5 else go to step 6
Step 5: Create a new node pointed by temp.
Step 5.1: Set temp->data= d
Step 5.2: Set temp->next=NULL
Step 5.3:Set temp->previous=NULL
Step 5.4:Set first=last=temp

Step 6: If first ≠ NULL then go to step 7

Step 7: Create a new pointer variable temp
Step 8: Set temp = last
Step 9: Create a new node pointed by r
Step 9.1: Set r->data=d
Step 9.2: Set r->next= NULL
 Step 9.3:Set r->previous=temp
Step 9.4: Set temp->next= r
Step 9.5: Set last=r
Step 10: Display the elements in the doubly linked list
Step 11: Stop

(Write program or algorithm for insertion-function into the doubly linked list)
PROGRAM:
struct node
{
int data;
struct node *next;
struct node *previous;
};
struct node *first=NULL;
struct node *last=NULL;
void insert( int num)
{
struct node *temp; // declare a pointer temp
temp=first; // the pointer temp points to the first node
if(temp==NULL) // if linked list is empty
{
temp=(struct node*)malloc(sizeof(struct node)); //
creates new node temp->data=num;
temp->next=NULL;
temp->previous=NULL;
first=last=temp; // inserts the new node to the list.
}
else{ // if linked list is non-empty
struct node *r;
temp=last;
r=(struct node*)malloc(sizeof(struct node));
 r->data=num;
r->next=NULL;
r->previous=temp;
temp->next=r;
last=r; // inserts the new node at the last of the list.
}}
Header Linked list
A header linked list is a linked list which always contains a special node, called
header node, at the beginning of the list.

The following are two kinds of widely used header lists

1. A grounded header list is a header list where the last node contains the null
pointer.
2. A circular header list is a header list where the last node points back to the header
node.
Grounded Header list
START

4000

Header node
5000 1 NULL

4000 5000
Circular Header list
START
4000

Header node
5000 1 4000

4000 5000
Binary Search Algorithm
Searching is the process of finding some particular element in the list. If the element is
present in the list, then the process is called successful, and the process returns the location
of that element. Otherwise, the search is called unsuccessful.

Linear Search and Binary Search are the two popular searching techniques. Here we will
discuss the Binary Search Algorithm.

Binary search is the search technique that works efficiently on sorted lists. Hence, to search
an element into some list using the binary search technique, we must ensure that the list is
sorted.

Binary search follows the divide and conquer approach in which the list is divided into two
halves, and the item is compared with the middle element of the list. If the match is found
then, the location of the middle element is returned. Otherwise, we search into either of the
halves depending upon the result produced through the match.

The recursive method of binary search follows the divide and conquer approach.

Let the elements of array are -

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

mid = (beg + end)/2

So, in the given array -

beg = 0

end = 8

mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

Now, the element to search is found. So algorithm will return the index of the element matched.

Binary Search complexity

Now, let's see the time complexity of Binary search in the best case, average case, and worst case. We will
also see the space complexity of Binary search.

1. Time Complexity
Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

o Best Case Complexity - In Binary search, best case occurs when the element to search is found in
first comparison, i.e., when the first middle element itself is the element to be searched. The best-
case time complexity of Binary search is O(1).
o Average Case Complexity - The average case time complexity of Binary search is O(logn).
o Worst Case Complexity - In Binary search, the worst case occurs, when we have to keep reducing
the search space till it has only one element. The worst-case time complexity of Binary search
is O(logn).
2. Space Complexity
Space Complexity O(1)

o The space complexity of binary search is O(1).

Implementation of Binary Search

Algorithm - Binary_Search(a, lower_bound, upper_bound, val)

// 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the
// index of the last array element, 'val' is the value to search

Step 1: set beg = lower_bound, end = upper_bound, pos = - 1

Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

Program: Write a program to implement Binary search in C language.

#include<stdio.h>
void main()
{
int arr[10],i,n,beg,end,num;
printf("enter the number of elements in the array in sorted order\n");
scanf("%d",&n);
printf("enter the elements\n");
for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("The elements are : \n");
for (i=0;i<n;i++)
{
printf("%d ",arr[i]);
 }
beg=0;
end=n-1;

printf("\nEnter The Value To Search Using Binary Search: ");

scanf("%d",&num);

BinarySearch(arr,num,beg,end);
}

void BinarySearch(int *arr,int num,int first,int last)

{
int mid;

if(first > last){

printf("Number is not in the list \n");

}
else
{

mid = (first + last)/2;

if(arr[mid]==num)
{
printf("Element Is At The Index: %d ",mid+1);
exit(0);
}
else if(arr[mid] > num)
{
BinarySearch(arr, num, first, mid-1);
}
else
{
BinarySearch(arr, num, mid+1, last);
}
}
}