DATA STRUCTURES

NOTES
UNIT I

DATA STRUCTURES
UNIT I

Data structures:
A data structure is basically a group of data elements that are put together
under one name, and which defines a particular way of storing and
organizing data in a computer so that it can be used efficiently.

Types of data structures

o Linear Data structures
If the elements of a data structure are stored in a linear or sequential
order, then it is a linear data structure. Linear data structures can
be represented in memory in two different ways. One way is to have
to a linear relationship between elements by means of sequential
memory locations. The other way is to have a linear relationship
between elements by means of links. Examples:
o Array
o Linked list
o Stacks
o Queues

o Non – Linear Data structures

If the elements of a data structure are not stored in a sequential
order, then it is a non-linear data structure. The relationship of
adjacency is not maintained between elements of a non-linear data
structure. Examples include trees and graphs.
o Trees
o Graphs

ABSTRACT DATA TYPE

An abstract data type (ADT) is a set of operations. Abstract data types are
mathematical abstractions; nowhere in an ADT's definition is there any
mention of how the set of operations is implemented. This can be viewed as
an extension of modular design.
An abstract data type (ADT) is the way we look at a data structure, focusing
on what it does and ignoring how it does its job. For example, stacks and
queues are perfect examples of an ADT. We can implement both these ADTs
using an array or a linked list. This demonstrates the ‘abstract’ nature of
stacks and queues. The word ‘abstract’ in the context of data structures
means considered apart from the detailed specifications or implementation.

LIST ADT
List is an abstract data type that represents a countable number of
ordered values, where the same value may occur more than
once. Operations performed on the list ADT are:
o Create
o Insert
o Delete
o Search
o Display
o Sort

A list ADT can be implemented using Array and Linked list.

Array Implementation of List ADT

Arrays can be declared in various ways in different languages. For

illustration, let's take C array declaration.

As per the above illustration, following are the important points to be

considered.

• Index starts with 0.

• Array length is 10 which means it can store 10 elements.

• Each element can be accessed via its index. For example, we can fetch an
element at index 6 as 9.

Basic Operations
Algorithm
o Create 1. Start
o Insert 2. Set J = N
3. Set N = N+1
o Delete 4. Repeat steps 5 and 6 while J
o Search >=
5.
K
Set LA[J+1] = LA[J]
o Display 6. Set J = J-1
7. Set LA[K] = ITEM
8. Stop
Creating a List ADT
create()
{
int b[20];
printf(”Enter the number of nodes”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(”\n Enter the Element:”,i+1);
scanf(“%d”,&b[i]);
}
printf("\n The Elements of The list ADT are:”);
for(i=0;i<n;i++)
{
printf("\n",b[i]);
}
}

Inserting a new element

Existing list with four elements

b
b[0] b[1] b[2] b[3] b[..] b[max]

A new element 57 is inserted in the position 3, After insertion

the list elements are

b
b[0] b[1] b[2] b[3] b[4] b[..]

void insert()
{
printf("\n Enter the position to insert:”);
scanf(“%d”,&pos);
if(pos>=n)
{
printf("\n invalid Location::");
}
else
 {
for(i=n-1;i>=pos;i--)
{
b[i+1]=b[i];
}
printf("\n Enter the element to insert:\n”);
scanf(“%d”,&p);
b[pos]=p;
n++;
}

Deleting an element from the list

Existing list with 5 elements

b
b[0] b[1] b[2] b[3] b[4] b[..]

An element 57 is to be deleted, after deletion the list elements are

b
b[0] b[1] b[2] b[3] b[4] b[..]

After deletion the number of elements in the list becomes 4.

void deletion()
{
printf("\n Enter the position u want to delete:”);
scanf(“%d”,&pos);
if(pos>=n)
{
printf("\n Invalid Location:”);
}
else
{
for(i=pos+1;i<n;i++)
{
b[i-1]=b[i];
}
n--;
 }
printf("\n The Elements after deletion”);
for(i=0;i<n;i++)
{
printf("\t",b[i]);
}
}

Searching an element in the list

Existing list with four elements

b
b[0] b[1] b[2] b[3] b[..] b[max]

To search a particular data item from a list, the user enters the item to be
searched. The List ADT should provide the position of the item if the item is
available or it should display that the item is not available in the list.

For example:
Enter the element to be searched : 34
The element is available in position 3.

void search()
{
printf("\n Enter the Element to be searched:”);
scanf(“%d”,&e);

for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("The element is in the position”,i+1);
}
}
}
Linked Lists
A linked list, in simple terms, is a linear collection of data elements. These
data elements are called nodes. Linked list is a data structure which in turn
can be used to implement other data structures.

In a linked list every node contains two parts, an integer and a pointer to the next
node. The left part of the node which contains data may include a simple data type,
an array, or a structure. The right part of the node contains address of the next
node

In order to form a linked list, we need a structure called node which has two fields,
DATA and NEXT. DATA will store the information part and NEXT will store the
address of the next node in sequence.

struct node NODE

{ Data Next
int data;
struct node *next; Data Field Address Field
} *start ;

There are different types of linked lists

• Singly Linked List
• Circularly Linked List
• Doubly Linked List

Singly Linked List

A singly linked list is the simplest type of linked list in which every node contains
some data and address of the next node of the same data type. A singly linked list
allows traversal of data only in one way.

Implementing a List ADT using singly linked list

Operations
• Create
• Insert
 • Delete
• Search
• Traverse

Create

For creating a new node,

ptr=(struct node*) malloc (sizeof(struct node));

the above code creates a node with data field and address field is created in
memory and the address of the new node is returned to pointer ptr.
Head
1020

1020

Algorithm for Creation of a list

Step 1 PTR=AVAIL
AVAIL=LINK(AVAIL)
Read INFO (PTR)
Head = PTR
Step 2 CH=”Y”
Step 3 Repeat step 4 to 5 while CH == “Y”
Step 4 CPT = AVAIL
AVAIL=LINK(AVAIL)
Read INFO (CPT)
LINK (PTR) = CPT
PTR = CPT
STEP 5 Read choice <Y/N> into CH for more Nodes
STEP 6 LINK (PTR) = NULL
Step 7 STOP
C Coding for creating a node
void create()
{
struct node *ptr,*temp;
int n,i=1;
printf("Enter the no. of nodes\n”);
scanf(“%d”,&n);
ptr=(struct node*)malloc(sizeof(struct node));
printf("enter the first node\n”);
scanf(“%d”,ptr->data);
start=ptr;
ptr->next=ptr;
while(i<n)
{
temp=(struct node*)malloc(sizeof(struct node));
printf("enter the next node\n”);
scanf(“%d”,temp->data);
ptr->next=temp;
temp->next=start;
ptr=temp;
i++;
}
}
Insert a new node

Here we discuss how a new node is added into an already existing linked list. We
will take four cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.

Inserting a Node at the Beginning of a Linked List

Consider the linked list shown in Figure below. Suppose we want to add a new node with
data 9 and add it as the first node of the list. Then the following changes will be done in the
linked list.

Algorithm for inserting a node at the beginning

We allocate space for the new node. Set its

DATA part with the given VAL and the next
part is initialized with the address of the first
node of the list, which is stored in. Now,
since the new node is added as the first node
of the list, it will now be known as the START
node, that is, the START pointer variable will
now hold the address of the NEW_NODE.

Code for inserting a node at the beginning

voidinsert_beg()
{
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
ptr=head;
head=temp;
printf("\nEnter the data to be inserted\n”);
scanf(“%d”,temp->data);
temp->next=ptr;
}
Inserting a Node at the End of a Linked List
Consider the linked list shown in Figure. Suppose we want to add a new node with
data 9 asthe last node of the list. Then the following changes will be done in the
linked list.
Algorithm to insert a node at the end

To insert a new node at the end of a linked list. In Step 6, we take a pointer
variable PTR and initialize it with START. That is, PTR now points to the first node
of the linked list. In the while loop, we traverse through the linked list to reach the
last node. Once we reach the last node, in Step 9, we change the NEXT pointer of
the last node to store the address of the new node.
Code for inserting a new node at the end
Void insert_end()
{
struct node *ptr,*temp;
ptr=start;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n”);
scanf(“%d”,temp->data);
while (ptr->next != NULL)
{
ptr=ptr->next;
}
ptr->next=temp
temp->next=NULL;
}

Inserting a Node After a Given Node in a Linked List

Consider the linked list shown in Figure. Suppose we want to add a new node with
value 9 afterthe node containing data 3.

• we take a pointer variable PTR and initialize it with START. That is, PTR now points
tothe first node of the linked list.
• Then we take another pointer variable PREPTR which will be usedto store the address of
the node preceding PTR. Initially, PREPTR is initialized to PTR.
• Now, PTR,PREPTR, and START are all pointing to the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the node that has its value
equalto NUM.
• We need to reach this node because the new node will be inserted after this node.
• Oncewe reach this node, in Steps 10 and 11, we change the NEXT pointers in such a
way that new nodeis inserted after the desired node.
Code for inserting a new node after a given node

Void insert_after()
{
intval;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n”);
scanf(“%d”,temp->data);
printf("\nEnter the node after which the new node to be inserted\n”);
scanf(“%d”,&val);
preptr=start;
ptr=start;
while (preptr->data!=val)
{
preptr=preptr->next;
}
ptr=preptr->next;
preptr->next=temp;
temp->next=ptr;
}

Inserting a Node Before a Given Node in a Linked List

• Suppose we want to add a new node with value 9 before the node containing 3.
• We take a pointer variable PTR and initialize it with START.
• That is, PTR now points to the first node of the linked list. Then, we take another pointer
variable PREPTR and initialize it with PTR.
• So now, PTR, PREPTR, and START are all pointing to the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the node that has
its value equal to NUM.
• We need to reach this node because the new node will be inserted before this node.
Void insert_before()
{
intval;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n”);
scanf(“%d”,temp->data);
printf("\nEnter the node before which the new node to be inserted\n”);
scanf(“%d”,&val);
ptr=start;
while (preptr->data!=val)
{
preptr=ptr;
ptr=ptr->next;

}
preptr->next=temp;
temp->next=ptr;

}
 Deleting a node from Singly Linked list

Case 1: The first node is deleted.

Case 2: The last node is deleted.
Case 3: The given node is deleted.

Case 1: Deleting the First Node from a Linked List

Consider the linked list below, When we want to delete a node from the beginning of the list,
then the following changes will be done in the linked list.

Code for deleting the first node:

void delete_first ( )
{
struct node *ptr;
if start == NULL;
{
printf(“The linked list is empty\n”);
}
else
{
ptr = start;
start = start -> next;
free(ptr);
}
}
Case 2: Deleting the Last Node from a Linked List
Consider the linked list shown below. Suppose we want to delete the last node from the linked
list, then the following changes will be done in the linked list.

• we take a pointer variable PTR and initialize it with START. That is, PTR now points to the
first node of thelinked list.
• In the while loop, we take another pointer variable PREPTR such that it always pointsto
one node before the PTR.
• Once we reach the last node and the second last node, we set the NEXTpointer of the
second last node to NULL, so that it now becomes the (new) last node of the linkedlist.
• The memory of the previous last node is freed and returned back to the free pool.

Code for deleting last node:

void delete_last ( )
{
struct node *ptr, *preptr;
if start == NULL;
{
printf(“The linked list is empty\n”);
}
else
{
ptr = start;
while(ptr->next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
}}
Case 3: Deleting the given node from the linked list
Consider the linked list shown below. Suppose we want to delete the given node from the linked
list, then the following changes will be done in the linked list.
Delete node with data 4 ,

Code for deleting the given node

Void delete_given ( )
{
int val;
struct node *ptr, *preptr;
if (start == NULL)
{
printf(“The linked list is empty\n”);
}
else
{
printf(“Enter the node to be deleted”);
scanf(“%d”,&val);
ptr = start;
while(ptr->data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = ptr->next;
free(ptr);
}}
Searching an element in a linked list

Searching is a process of finding the position of a particular element in the list. For
example consider the linked list given below. If we want to find the position of
node with data 2, then the position is printed as 3.

• We initialize a pointer PTR with START

• Then move the PTR until its data part is equal to VALUE to be searched
• Use a variable position to trace the position of the node.
• Print the position of the node.

C Code for Searching an element from linked list

void search()
{
int position =1, val;
struct node *ptr;
printf(“Enter the the node to be found” );
scanf(“%d”, & val);
if(start == NULL)
{
Printf(“The list is empty”)
}
else
{
ptr = start;
while ( ptr -> data != val)
{
ptr = ptr -> next;
position = position + 1;
}
printf ( “The node is in position %d”, position);
}
}
Traversing a linked list
• Traversing a linked list means accessing the nodes of the list in order to perform some
processingon them.
• For traversing the linked list, we also make use of another pointer variable PTR which
points to the node that is currently being accessed.
• first initialize PTR with the address of START. So now, PTR points to the firstnode of
the linked list.
• Then a while loop is executed which is repeated till PTR processes the last node, that is
until it encounters NULL.
• We apply the process (e.g., print) to the current node, that is, the node pointed by PTR.
• We move to the next node by making the PTR variable point to the node whose address
is stored in the NEXT field.

C Code for traversing a linked list

void traverse()
{
struct node *ptr;
if(start == NULL)
{
Printf(“The list is empty”)
}
else
{
ptr = start;
while ( ptr ->next != NULL)
{
printf(“%d”, ptr ->data);
ptr = ptr -> next;
}
printf(“%d”, ptr ->data);
}
}
CIRCULAR LINKED LIST

• In a circular linked list, the last node contains a pointer to the first node of the list.
• While traversing a circular linked list, we can begin at any node and traverse the list in any
direction, forward or backward, until we reach the same node where we started.
• Thus, a circular linked list has no beginning and no ending.
• Circular linked lists are widely used in operating systems for task maintenance.

Circular Linked list

Operations that can performed in a circularly linked list

• Create (similar to singly linked list)
• Insert
• Delete
• Search
• Traverse

Create

For creating a new node,

ptr=(struct node*) malloc (sizeof(struct node));

the above code creates a node with data field and address field is created in
memory and the address of the new node is returned to pointer ptr. In a circularly
linked list the address part of the last node will contain the address of the first
node.

Start

1020

1020

1020
C Coding for creating a node in circular linked list
void create()
{
struct node *ptr,*temp;
int n,i=1;
printf("Enter the no. of nodes\n”);
scanf(“%d”,&n);
ptr=(struct node*)malloc(sizeof(struct node));
printf("enter the first node\n”);
scanf(“%d”,ptr->data);
start=ptr;
ptr->next=ptr;
while(i<n)
{
temp=(struct node*)malloc(sizeof(struct node));
printf("enter the next node\n”);
scanf(“%d”,temp->data);
ptr->next=temp;
temp->next=start;
ptr=temp;
i++;
}
}

Inserting a new node to circularly linked list

Case 1: The new node is inserted at the beginning of the circular linked list.
Case 2: The new node is inserted at the end of the circular linked list.
Case 3: The new node is inserted before a given node (Exactly same as singly linked list)
Case 4: The new node is inserted after a given node (Exactly same as singly linked list)

Inserting at the beginning of the circular linked list

Suppose we want to add a new node with data 9 as the first node of the list. Then the following
changes will be done in the linked list. Consider the circular linked list below

• We allocate space for the new node.

• Set its DATA part with the given VAL and the NEXT part is initialized with the address of
the first node of the list, which is stored in START.
 • Now, since the new node is added as the first node of the list, it will now be known as the
START node, that is, the START pointer variable will now hold the address of the
NEW_NODE.
• While inserting a node in a circular linked list, we have to use a while loop to traverse to
the last node of the list.
• Because the last node contains a pointer to START, its NEXT field is updated so that after
insertion it points to the new node which will be now known as START.

After inserting the new node with data 9, the circularly linked list will change as given below

Code for Inserting at the beginning of the circular linked list:

void insert_beg ( )
{
struct node *ptr, *temp;
temp = (struct node*)malloc(sizeof(struct node));
ptr=start;
while (ptr->next != start )
{
ptr = ptr->next;
}
temp->next=start;
start = temp ;
ptr->next = start;
}

Inserting at the end of the circular linked list

Suppose we want to add a new node with data 9 asthe last node of the list. Then the following
changes will be done in the linked list.

• We take a pointer variable PTR and initialize it with START. That is, PTR now points to
the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the last node.
• Once we reach the last node, we change the NEXT pointer of the last node to store the
address of the new node.
• Remember that the NEXT field of the new node contains the address of the first node which
is denoted by START.

Code for inserting a node at the end of circular linked list

Void insert_end ( )
{
struct node *ptr, *temp;
temp = (struct node*)malloc(sizeof(struct node));
ptr=start;
while (ptr->next != start )
{
ptr = ptr->next;
}
ptr->next=temp;
temp->next=start;
}

Inserting a new node after a given node in a Circular Linked List

Consider the linked list shown in Figure. Suppose we want to add a new node with value 9 after
the node containing data 3.

• we take a pointer variable PTR and initialize it with START. That is, PTR now points tothe
first node of the linked list.
• Then we take another pointer variable PREPTR which will be used to store the address of
the node preceding PTR. Initially, PREPTR is initialized to PTR.
 • Now, PTR, PREPTR, and START are all pointing to the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the node that has its value
equal to NUM.
• We need to reach this node because the new node will be inserted after this node.
• Once we reach this node, in Steps 10 and 11, we change the NEXT pointers in such a way
that new node is inserted after the desired node.

Code for inserting a new node after a given node

void insert_after()
{
int val;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\n Enter the data to be inserted\n”);
scanf(“%d”,temp->data);
printf("\n Enter the node after which the new node to be
inserted\n”);
scanf(“%d”,&val);
preptr=start;
ptr=start;
while (preptr->data!=val)
{
preptr=preptr->next;
}
ptr=preptr->next;
preptr->next=temp;
temp->next=ptr;
}

Inserting a new node before a given node in a Circular Linked List

• Suppose we want to add a new node with value 9 before the node containing 3.
 • We take a pointer variable PTR and initialize it with START.
• That is, PTR now points to the first node of the linked list. Then, we take another pointer
variable PREPTR and initialize it with PTR.
• So now, PTR, PREPTR, and START are all pointing to the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the node that has
its value equal to NUM.
• We need to reach this node because the new node will be inserted before this node.

Code for inserting a new node before a given node

void insert_before()
{
int val;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n”);
scanf(“%d”,temp->data);
printf("\nEnter the node before which the new node to be
inserted\n”);
scanf(“%d”,&val);
ptr=start;
while (preptr->data!=val)
{
preptr=ptr;
ptr=ptr->next;
}
preptr->next=temp;
temp->next=ptr;
}

Deleting a Node from a Circular Linked List

• Case 1: The first node is deleted.
• Case 2: The last node is deleted.
• Case 3: The given node is deleted.

Deleting the first node from circular linked list

When we want to delete a node from the beginning of the list, then the following changes will
be done in the linked list. Consider the given linked list.

• We check if the linked list exists or not.

• We use a pointer variable PTR which will be used to traverse the list to ultimately reach the
last node.
• We change the next pointer of the last node to point to the second node of the circular
linked list.
• Then the memory occupied by the first node is freed.
• Finally, in the second node now becomes the first node of the list and its address is stored in
the pointer variable START.

Code for deleting the first node of circular linked list

void delete_beg( )
{
struct node *ptr, *temp;
if (start == NULL)
{
printf(“The linked list is empty”);
}
else
{
ptr = start;
temp = start;
while (ptr->next != start)
{
ptr = ptr->next;
}
ptr->next=start->next;
start = start->next;
free (temp);
}}

Deleting the last node from circular linked list

Suppose we want to delete the last node from the linked list, then the following changes will be
done in the linked list.
• We take a pointer variable PTR and initialize it with START.
• That is, PTR now points to the first node of the linked list.
• In the while loop, we take another pointer variable PREPTR such that PREPTR always
points to one node before PTR.
• Once we reach the last node and the second last node, we set the next pointer of the second
last node to START, so that it now becomes the (new) last node of the linked list.
 • The memory of the previous last node is freed and returned to the free pool.

Code for deleting the last node of circular linked list

void delete_last( )
{
struct node *ptr, *preptr;
if (start == NULL)
{
printf(“The linked list is empty”);
}
else
{
ptr = start;
while (ptr->next != start)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next=start;
free (ptr);
}}

Deleting the given node from circular linked list

Consider the linked list shown below. Suppose we want to delete the given node from the
circular linked list, then the following changes will be done in the circular linked list.
 • We take a pointer variable PTR and initialize it with START.
• That is, PTR now points to the first node of the linked list.
• In the while loop, we take another pointer variable PREPTR such that PREPTR always
points to one node before PTR.
• We take the pointer PTR to the node we want to delete, so PREPTR is positioned one node
before PTR,
• Once we reach the node we want to delete we set the next part of PREPTR to PTR -> next.
• The memory of the node pointed by PTR is freed and returned to the free pool.

Code for deleting the given node of circular linked list

void delete_last( )
{
int val;
struct node *ptr, *preptr;
if (start == NULL)
{
printf(“The linked list is empty”);
}
else
{
printf(“Enter the node to be deleted”);
scanf(“%d”, &val);
ptr = start;
while (ptr->next != val)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next=ptr->next;
free (ptr);
}}
Doubly Linked list
Doubly linked list is a linear collection of data items similar to singly linked list. But a node of
the doubly linked list has 3 parts, a data field, link to previous node and link to next node. The
node of a doubly linked list is shown below.

A doubly linked list node is created using the structure,

struct node
{
struct node *prev;
int data;
struct node *next;
} *start;

Example of a doubly linked list

Operations that can be done on a doubly linked list

• Create
• Insert
• Delete
• Search
• Traverse

Create
For creating a new node,
ptr=(struct node*) malloc (sizeof(struct node));

the above code creates a node with data field and address field is created in memory and the
address of the new node is returned to pointer ptr.
C Coding for creating a node
void create()
{
struct node *ptr,*temp;
intn,i=1;
printf("Enter the no. of nodes\n");
scanf("%d",&n);
ptr=(struct node*)malloc(sizeof(struct node));
printf("enter the first node\n");
scanf("%d",&ptr->data);
start=ptr;
ptr->prev=NULL;
ptr->next=NULL
while(i<n)
{
temp=(struct node*)malloc(sizeof(struct node));
printf("enter the next node\n");
scanf("%d",&temp->data);
ptr->next=temp;
temp->next=NULL;
temp->prev=ptr;
ptr=temp;
i++;
}
}
Inserting a new node in a Doubly Linked List

Here we discuss how a new node is added into an already existing doubly linked list. We will
take four cases and then see how insertion is done in each case.

Case 1: The new node is inserted at the beginning.

Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.

Inserting a Node at the Beginning of a Linked List

Consider the linked list shown in Figure below. Suppose we want to add a new node with
data 15 and add it as the first node of the list. Then the following changes will be done in
the linked list.

Allocate memory for the new node in PTR and initialize its DATA part to 15 and
PREV field to NULL.

Add the new node before the START node. Now the new node becomes the first node
of the list.

C Code for inserting a node at the beginning

void insert_beg()
{
struct node *ptr,
ptr=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&ptr->data);
ptr->next=start;
 start->prev=ptr;
start=ptr;
}

Inserting a Node at the End of a Doubly Linked List

Consider the linked list shown in Figure. Suppose we want to add a new node with data 15 asthe
last node of the list. Then the following changes will be done in the linked list.

Allocate memory for the new node in TEMP and initialize its DATA part to 15 and NEXT field to NULL.

Take a pointer variable PTR and make it point to the first node of the [Link] PTR so that it points to
the last node of the list. Add the new node after the node pointed by PTR.

C Code for inserting a new node at the end

Void insert_end()

struct node *ptr,*temp;

ptr=start;

temp=(struct node*)malloc(sizeof(struct node));

printf("\nEnter the data to be inserted\n");

scanf("%d",&temp->data);

while (ptr->next != NULL)

ptr=ptr->next;

ptr->next=temp

temp->next=NULL;

temp->prev=ptr;

}
Inserting a Node After a Given Node in a Doubly Linked List
Consider the linked list shown in Figure. Suppose we want to add a new node with value 36
after the node containing data 23.

Allocate memory for the new node in TEMP and initialize its DATA part to 36.

Take a pointer variable PTR and make it point to the first node of the list.

Move PTR further until the data part of PTR = value after which thenode has to
be inserted.

Insert the new node between PTR and the node succeeding it. It can be done by
making following TEMP->NEXT = PTR->NEXT, PTR->NEXT=TEMP, TEMP->PREV=PTR &
TEMP->NEXT->PREV=TEMP.

C Code for inserting a new node after a given node in DLL

Void insert_after()
{
intval;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&temp->data);
printf("\nEnter the node after which the new node to be
inserted\n");
scanf("%d",&val);
ptr=start;
while (ptr->data!=val)
{
ptr= ptr->next;
}
temp->next = ptr->next;
ptr->next=temp;
temp->prev=ptr;
temp->next->prev=temp;
}

Inserting a Node Before a Given Node in a Doubly Linked List

Consider the linked list shown in Figure. Suppose we want to add a new node with value
36beforethe node containing data 23.

Allocate memory for the new node in TEMP and initialize its DATA part to 36

Take a pointer variable PTR and make it point to the first node of the list.

Move PTR further so that it now points to the node whose data is equalto the
value before which the node has to be inserted.
 Add the new node in between the node pointed by PTR and the node preceding [Link]
can be done by making following changes, TEMP->NEXT = PTR,TEMP->PREV=PTR->PREV,
PTR->PREV->NEXT= TEMP &PTR->PREV=TEMP.

C code for inserting a node before a Given Node in a Doubly Linked List

Void insert_before()
{
int val;
struct node *ptr,*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&temp->data);
printf("\nEnter the node before which the new node to be
inserted\n");
scanf("%d",&val);
ptr=start;
while (ptr->data!=val)
{
ptr=ptr->next;

}
temp->next=ptr;
temp->prev=ptr->prev;
ptr->prev->next= temp;
ptr->prev=temp;
}
Deleting a node from Doubly Linked List
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The given node is deleted.

Case 1: Deleting the First Node from a Doubly Linked List

Consider the linked list below, When we want to delete a node from the beginning of the list,
then the following changes will be done in the linked list.

Free the memory occupied by the first node of the list and make the second node of
thelist as the START node. Make PTR=START, START=START->NEXT and FREE(PTR)

C code for deleting the first node:

Void delete_first ( )
{
struct node *ptr;
if start == NULL;
{
printf(“The linked list is empty”)
}
else
{
ptr = start;
start=start->next;
start->prev = NULL
free(ptr);
}
}
Case 2: Deleting the last Node from a Doubly Linked List
Consider the linked list below, when we want to delete a node from the end of the list, then the
following changes will be done in the linked list.

Take a pointer variable PTR that points to the first node of the list.

Move PTR so that it now points to the last node of the list.

Free the space occupied by the node pointed by PTR and store NULL in NEXT field
ofits preceding node. By making PTR->PREV->NEXT=NULL and Free(PTR)

C code for deleting the last node:

Void delete_last ( )
{
struct node *ptr;
if start == NULL;
{
printf(“The linked list is empty”)
}
else
{
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->prev->next=NULL;
free(ptr);
}}
Case 3: Deleting the given node from a Doubly Linked List
Consider the linked list below, when we want to delete a given node from the list, and then the
following changes will be done in the linked list.

Take a pointer variable PTR that points to the first node of the list.

Move PTR so that it now points to the given node which is to be deleted. Here we want to delete
node with data 23.

Free the space occupied by the node pointed by PTR. Then connect the other two nodes by
making PTR->PREV->NEXT= PTR->NEXT, PTR->NEXT->PREV=PTR->PREV and
Free(PTR)

C code for deleting the given node:

Void delete_given ( )
{
int val;
struct node *ptr;
if start == NULL;
{
printf(“The linked list is empty”)
}
else
 {
printf(“Enter the node to be deleted”);
scanf(“%d”, &val);

while(ptr->data!= val)
{
ptr=ptr->next;
}
ptr->prev->next= ptr->next;
ptr->next->prev=ptr->prev;
free(ptr);
}
}

Searching an element in a Doubly linked list

Searching is a process of finding the position of a particular element in the list. For
example consider the linked list given below. If we want to find the position of
node with data 23, then the position is printed as 3.

• We initialize a pointer PTR with START

• Then move the PTR until its data part is equal to VALUE to be searched
• Use a variable position to trace the position of the node.
• Print the position of the node.

C Code for Searching an element from Doubly linked list

void search()
{
int position =1, val;
struct node *ptr;
printf(“Enter the the node to be found” );
scanf(“%d”, & val);
if(start == NULL)
{
 Printf(“The list is empty”)
}
else
{
ptr = start;
while ( ptr -> data != val)
{
ptr = ptr -> next;
position = position + 1;
}
printf ( “The node is in position %d”, position);
}
}

Traversing a Doubly linked list

• Traversing a linked list means accessing the nodes of the list in order to perform some
processing on them.
• Doubly linked list can be traversed in both directions – Forward and backward

Forward Traversal

• First initialize PTR with the address of START. So now, PTR points to the first node of
the linked list.
• Then a while loop is executed which is repeated till PTR processes the last node, that is
until it encounters NULL.
• We apply the process (e.g., print) to the current node, that is, the node pointed by PTR.
• We move to the next node by making the PTR variable point to the node whose address
is stored in the NEXT field.
• OUTPUT – 54 65 23 15
 C Code for forward traversing a doubly linked list
void forward()
{
struct node *ptr;
if(start == NULL)
{
Printf(“The list is empty”)
}
else
{
ptr = start;
while ( ptr ->next != NULL)
{
printf(“%d”, ptr ->data);
ptr = ptr -> next;
}
printf(“%d”, ptr ->data);
}
}

Backward Traversal

• Backward traversal starts visiting the nodes in reverse.

First initialize PTR with the address of START. So now, PTR points to the first node of the
linked list.

Then move the PTR to last node using a while loop.

• Then use another while loop to navigate the PTR in reverse.
• We apply the process (e.g., print) to the current node, that is, the node pointed by PTR.
• We move to the next node by making the PTR variable point to the node whose address
is stored in the PREV field.
• OUTPUT – 15 23 65 54

C Code for Backward traversing a doubly linked list

void backward()
{
struct node *ptr;
if(start == NULL)
{
Printf(“The list is empty”)
}
else
{
ptr = start;
while ( ptr -> next != NULL)
{
ptr = ptr -> next;
}
while ( ptr ->prev != NULL)
{
printf(“%d”, ptr ->data);
ptr = ptr -> prev;
}
printf(“%d”, ptr ->data);
}
}
Applications of Linked List
Linked lists and Polynomials
In mathematics, a polynomial is an expression consisting of variables (also called
indeterminates) and coefficients, that involves only the operations of addition, subtraction,
multiplication, and non-negative integer exponents of variables. An example of a polynomial of
a single indeterminate, x, is 6𝑥 4 + 2𝑥 3 + 5𝑥 2 + 9𝑥 + 16
We can maintain and represent polynomials with the help of linked lists.
In the linked representation of polynomials, each node should consist of three elements, namely
(i) Coefficient
(ii) Exponent
(iii) and a link to next term

The coefficient field holds the value of the coefficient of a term, the exponent field contains the
exponent value of the term and the link field contains the address of the next term in the
polynomial.

For example the following polynomial of degree 4 can be represented as linked list as:

3𝑥 4 + 8𝑥 2 + 6𝑥 + 8

Polynomial operations using linked list

➢ Polynomial addition
➢ Polynomial subtraction
➢ Polynomial multiplication

Addition of polynomials
➢ Add the coefficients having same exponent and keep the exponents unchanged
Example 2 - Add 𝟓𝒙𝟒 + 𝟔𝒙𝟑 + 𝟐𝒙𝟐 + 𝟏𝟎𝒙 + 𝟒 and 𝟕𝒙𝟑 + 𝟑𝒙𝟐 + 𝒙 + 𝟕

5𝑥 4 + 6𝑥 3 + 2𝑥 2 + 10𝑥 + 4
7𝑥 3 + 3𝑥 2 + 𝑥+7
5𝑥 4 + 13𝑥 3 + 5𝑥 2 + 11𝑥 + 11
Using Linked list
To add two polynomials, compare their corresponding terms starting from the first node and
move towards the 2nd node.
A general algorithm for addition of two polynomials:
Let a and b be the two polynomials represented by linked lists
1. while a and b are not null, repeat step 2.
2. If powers of the two terms are equal
then if the terms do not cancel
then insert the sum of the terms into the sum Polynomial
Advance a
Advance b
Else if the power of the first polynomial > power of second
polynomial
Then insert the term from first polynomial into sum
polynomial
Advance a
Else insert the term from second polynomial into sum polynomial
Advance b
3. copy the remaining terms from the non empty polynomial into the
sum polynomial.

Linked list addition

ADD 5𝑥 4 + 6𝑥 3 + 2𝑥 2 + 10𝑥 + 4 and 7𝑥 3 + 3𝑥 2 + 𝑥+7

 After execution of the procedure the resultant polynomial is shown below.

Multiplication of polynomials
The multiplication of polynomials is performed by multiplying the coefficient and
adding the respective exponents.

Example: Multiply 8𝑥 4 + 6𝑥 2 + 5𝑥 + 2 and 3𝑥 2 + 𝑥 + 2

8𝑥 4 + 6𝑥 2 + 5𝑥 + 2
3𝑥 2 + 𝑥 + 2
16𝑥 4 + 0 + 12𝑥 2 + 10𝑥 + 4
8𝑥 5 + 0 + 6𝑥 3 + 5𝑥 2 + 2𝑥
24𝑥 6 + 0 + 18𝑥 4 + 15𝑥 3 + 6𝑥 2

24𝑥 6 +8𝑥 5 + 34𝑥 4 + 21𝑥 3 + 23𝑥 2 + 12𝑥 + 4

To produce multiplication of two polynomials

1. Check whether two given polynomials are nonempty.
a. If anyone polynomial is empty then polynomial
multiplication is not possible.
2. Polynomials are scanned from left to right.
3. For each term of the second polynomial, first
polynomial is scanned from left to right and its
each term is multiplied by the term of second
polynomial.
a. Multiply the coefficients and add the
exponents.
4. If the product term already exists in the resultant
polynomial, then its coefficients are added
otherwise a new node is inserted to represent the
product term.