CS8391 DATA STRUCTURES

UNIT I
LINEAR DATA STRUCTURES – LIST
Abstract Data Types (ADTs) – List ADT – array-based implementation – linked list implementation ––
singly linked lists- circularly linked lists- doubly-linked lists – applications of lists –Polynomial
Manipulation – All operations (Insertion, Deletion, Merge, Traversal).

1.1 Introduction
Definition of Data structure
“The way information is organized in the memory of a computer is called a data structure”.
(OR)
A data structure is a way of organizing data that considers not only the items stored, but also their
relationship to each other. Advance knowledge about the relationship between data items allows
designing of efficient algorithms for the manipulation of data.
Common data structures are
• Stacks • Queues • Lists
• Trees • Graphs • Tables
Classification of data Structure:
Based on how the data items are operated, it will classified into
1. Primitive Data Structure: is one the data items are operated closest to the machine level
instruction.
Example: int, char and double.
2. Non-Primitive Data Structure: is one that data items are not operated closest to machine
level instruction.
2.1. Linear Data Structure: In which the data items are stored in sequence order.
Example: Arrays, Lists, Stacks and Queues.
2.2. Non Linear Data Structure: In which the order of data items is not presence.
Example: Trees, Graphs.

1.2 Abstract Data Types

Abstract data type (ADT) is a specification of a set of data and the set of operations that can be
performed on the data.
The abstract data type is written with the help of instances and operations. In ADT instances
represent the elements on which various operations can be performed.
Examples,
Array, stack, queue, tree, etc.,
Department of IT, Panimalar Engineering College, Chennai.
1
 CS8391 DATA STRUCTURES

Array as an ADT:
AbstractDataType Array
{
Instances:
An array A of some size, index i and total number of elements in the array n
Operations:
Store() – this operation stores the desired elements at each successive location.
Display() – this operation displays the elements of the array.
}

ADT is useful to handle the data type correctly. Always what is to be done is given in ADT but
how is to be done is not given in ADT. Note that we have only given what are the operations in arrays in
above example. But how it is to be done is not given.

1.3 List ADT

• A list is a ordered tuple of homogeneous elements
A0, A1, A2, …., An-1
where Ai is the i-th element of the list
• The position of element Ai is i; positions range from 0 to n-1 inclusive
• The size of a list is N (a list with no elements is called an “empty list”.
Generic Operations on a list:
1. Create an empty list
2. printList – prints all elements in the list
3. find(x) – returns the position of the first occurrence of x.
4. remove(x) – removes x from the list if present
5. insert(x,postion) – inserts x into the list at the specified position.
6. isEmpty() – returns true if the list has no elements
7. findKth(int k) –returns the element in the specified position.
8. Sort() – sort the elements in ascending or descending order.

1.4 Array implementation of List

An array is a collection of elements of similar data type that are referred through a common name. It is
simply a grouping of similar data items.
The elements in the array are stored in contiguous memory locations. A specific element in an array is
accessed by an index or subscript. Subscript or index should not be negative. The first element of array will
have index as zero.

Department of IT, Panimalar Engineering College, Chennai.

2
 CS8391 DATA STRUCTURES

One-Dimensional Arrays:
A list of items can be given one variable name using only one subscript and such a variable is called
single-subscripted variable or one dimensional array. A one dimensional array can be declared as
follows:
General syntax:
datatype array_name[size_of_array];
Example:
int a[7];
The array ‘a’ of size 7, has all the elements which are of integer type. Let us understand such an
arrangement of array elements by following figure 1.1

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

10 20 30 40 50 60 70

Figure. 1.1 Array a[7]

Now let us see how to handle this array. We will write a simple C program in which we are simply going
to store the elements and then we will print those stored elements.
#include<stdio.h>
void main()
{
int a[7],index;
printf(“\nEnter the Elements in an Array a:”);
for(index=0;index<=6;index++)
scanf(“%d”,&a[index]);
printf(“\n You have Stored these numbers in the array a:”);
for(index=0;index<=6;index++)
printf(“\n%d”,a[index]);
}

Memory Representation of One-Dimensional Array:

The array name holds the address of the first element. It is called as BASE ADDRESS of that
array. The base address can’t be modified during execution, because it is static.
Consider the first element is stored in the address of 1020. It will look like in figure 1.2,
int a[7];

Department of IT, Panimalar Engineering College, Chennai.

3
 CS8391 DATA STRUCTURES

Address 1020 1022 1024 1026 1028 1030 1032

10 20 30 40 50 60 70
Index 0 1 2 3 4 5 6

a[0] means a + 0 ➔ 1020 + 0 ➔ 1020 (locates the 1020)

a[1] means a + 1 ➔ 1020 + 1 * size of datatype ➔ 1020 + 2 ➔ 1022
[ for ‘int’ size is 2 byte]
a[2] means a + 2 ➔ 1020 + 2 * size of datatype ➔ 1020 + 4 ➔ 1024
a[3] means a + 3 ➔ 1020 + 3 * size of datatype ➔ 1020 + 6 ➔ 1026
a[4] means a + 4 ➔ 1020 + 4 * size of datatype ➔ 1020 + 8 ➔ 1028

Array Implementation of List:

#include<stdio.h>
#include<conio.h>
#define MAX 10

int a, b[20], n, p, e, f, i, pos;

void create()
{
printf("\n 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]);
}
}

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%d", b[i]);

Department of IT, Panimalar Engineering College, Chennai.

4
 CS8391 DATA STRUCTURES

void search()
{
printf("\n Enter the Element to be searched:");
scanf("%d", &e);
for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("Value is in the %d Position", i);
break;
}
}
if(i==n)
Printf(“Element not Found!”);
}

void insert()
{
printf("\n Enter the position u need to insert::");
scanf("%d", &pos);
if(pos>=n)
printf("\n invalid Location::");
else
{
for(i=MAX-1;i>=pos-1;i--)
{
b[i+1]=b[i];
}
printf("\n Enter the element to insert::\n");
scanf("%d",&p);
b[pos]=p;
n++;
}
printf("\n The list after insertion::\n");
display();
}
void display()
{
printf("\n The Elements of The list ADT are:");
for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]);
}
}
void main()
{
int ch;
char g='y';
do
{
Department of IT, Panimalar Engineering College, Chennai.
5
 CS8391 DATA STRUCTURES

printf("\n main Menu");

printf("\n 1.Create \n 2.Delete \n 3.Search \n 4.Insert \n 5.Display\n 6.Exit \n");
printf("\n Enter your Choice");
scanf("%d", &ch);
switch(ch)
{
case 1: create(); break;
case 2: deletion(); break;
case 3: search(); break;
case 4: insert(); break;
case 5: display();break;
case 6: exit(); break;
default: printf("\n Enter the correct choice:");
}
printf("\n Do u want to continue:::");
scanf("\n%c", &g);
}while(g=='y'||g=='Y');
getch();
}
1.5 Linked Lists implementation of List
A linked list is a linear collection of data elements, called nodes, where the linear order is given
by means of pointers.
Types of Linked Lists:
There are different kinds of linked list. They are
1. Singly Linked List
2. Circular Linked List
3. Two-way or doubly linked lists
4. Circular doubly linked lists
Singly-linked list
A singly linked list is a linear collection of data elements, called nodes. Each and every node has
two parts:
• The first part contains the information of the element i.e. INFO.
• The second part is NEXT, which contains the address of the next node in the list.
NODE

INFO NEXT
Node Structure:
typedef struct nodetype
{
int info;
struct nodetype *next;
}node;

Department of IT, Panimalar Engineering College, Chennai.

6
 CS8391 DATA STRUCTURES

❖ The linked list consists of series of nodes, which are not necessarily adjacent in memory.
❖ A list is a dynamic data structure i.e. the number of nodes on a list may vary dramatically as
elements are inserted and removed.
❖ The pointer of the last node contains a special value, called the null pointer. This null pointer
signals the end of list.
❖ The list with no nodes on it is called the empty list or null list.
Example:
The single linked list with 4 nodes is shown below:

Head First Node Last Node

10 20 30 40 Null

Figure. 1.2 Singly Linked List containing four integer values

Basic Operations:
1. Insertion
a. At first
b. At last
c. At a given location (At middle)
2. Deletion
a. First Node
b. Last Node
c. Node in given location or having given data item
Initial Condition
HEAD = NULL;
Address of the first node in the list is stored in HEAD. Initially there is no node in the list. So, HEAD is
initialized to NULL (No address)
Insertion
a) Inserting at the beginning of a List
Algorithm INSFIRST(HEAD, ITEM)
/* This algorithm inserts ITEM as the first node in the list */
1. Start
2. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
3. TEMP->INFO = ITEM /* Store the ITEM in the INFO part of the TEMP node */
4. TEMP->NEXT = HEAD /* Address of Starting Node is Copied to NEXT part of the TEMP node
*/
Department of IT, Panimalar Engineering College, Chennai.
7
 CS8391 DATA STRUCTURES

5. HEAD = TEMP /* Address of New node is copied to the HEAD. Now the new becomes the first
node of the LIST. */
6. Exit
This is illustrate in figure 1.3.

head 1080 7060 1024

Assume: Initial List 1080 6 7060 7 1024 2 NULL

Step 4
temp 7088
Results of Steps 2 & 3 7088 8 NULL

head 1080 7060 1024

1080 6 7060 7 1024 2 NULL

Step 5
temp 7088 Result of Step 4
7088 8 1080

head 1080 7060 1024

7088 6 7060 7 1024 2 NULL

Result of Step 5 Result of Step 4

7088
temp
7088 8 1080

head 7088 1080 7060 1024

Final List 7088 8 1080 6 7060 7 1024 2 NULL

Figure.1.3 Linked List Insertion Operations

Implementation in C:
/* head is global variable, holds the address of the first node in the linked list and structure node is
defined globally */
void addfirst()
{ node *temp;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->info);
temp->next = head;
head = temp;
}

Department of IT, Panimalar Engineering College, Chennai.

8
 CS8391 DATA STRUCTURES

b) Inserting at the end of a List

Algorithm INSLAST(HEAD, ITEM)
/* This algorithm inserts ITEM as the last node in the list */
1. Start
2. Move the CUR pointer to the last node of the list.
3. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
4. TEMP->INFO = ITEM /* Store the ITEM in the INFO part of the TEMP node */
5. TEMP->NEXT = CUR->NEXT /* Address of last node is Copied to NEXT part of the TEMP
node */
6. CUR->NEXT = TEMP /* Address of last node is copied to the CUR->NEXT. Now the new node
becomes the last node of the LIST. */
7. Exit
Implementation in C:
/* head is global variable, holds the address of the first node in the linked list and structure node is
defined globally */
void addlast()
{ node *temp, *cur = head;
while(cur->next!=NULL)
cur=cur->next;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->info);
temp->next = cur->next;
cur->next = temp;
}

c) Inserting at the given location of the List (Middle of the List)

Algorithm INSMID(HEAD, POS, ITEM)
1. Start
2. Get the position POS, where the new node should be inserted
3. Move the CUR pointer to the previous node of POS positioned node in the list. If the POS is not
available display error message.
4. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
Department of IT, Panimalar Engineering College, Chennai.
9
 CS8391 DATA STRUCTURES

5. TEMP->INFO = ITEM /* Store the ITEM in the INFO part of the TEMP node */
6. TEMP->NEXT = CUR->NEXT /* Address in CUR->NEXT is Copied to NEXT part of the
TEMP node */
7. CUR->NEXT = TEMP /* Address in TEMP is copied to the CUR->NEXT. Now the new node is
inserted at the given POS of the LIST. */
8. Exit
Implementation in C:
void addmid()
{
int i=1, pos;
node *cur=head , *temp;
printf("\nEnter the position to insert...");
scanf("%d", &pos);
while( i != pos-1 && cur!=NULL)
{
cur = cur->next;
i++;
}
if( i == pos - 1)
{
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item for the node...");
scanf("%d",&temp->info);
temp->next = cur->next;
cur->next = temp;
}
else
printf(“List is Small, Unable to find the Position”);
}

Deletion
(a) Deleting the first node of the list
Algorithm DELFIRST(HEAD)
/* This algorithm deletes the first node of the list */
1. Start
Department of IT, Panimalar Engineering College, Chennai.
10
 CS8391 DATA STRUCTURES

2. TEMP = HEAD /* Copy address in HEAD to TEMP */

3. HEAD = HEAD->NEXT /* Copy address in HEAD->NEXT to HEAD */
4. free(TEMP) /* Delete the First Node, using the address stored in the TEMP */
5. Exit
This process is illustrated in figure 1.4.

head 1080 7060 2140 7088

1080 6 7060 7 2140 5 7088 8 NULL

temp
1080

head 1080 7060 2140 7088

7060 6 7060 7 2140 5 7088 8 NULL

temp
1080

head 7060 2140 7088

Final List 7060 7 2140 5 7088 8 9004

Figure 1.4. Linked List Deletion Operations

Implementation in C:
void delfirst()
{
node *temp;
temp=head;
head = head->next;
free(temp);
}

(b) Deleting the last node

Algorithm DELLAST(HEAD)
/* This algorithm deletes the last node of the list */
1. Start
2. Move CUR pointer to the previous node of the last node
3. TEMP = CUR->NEXT /* Copy address in CUR->NEXT to TEMP */

Department of IT, Panimalar Engineering College, Chennai.

11
 CS8391 DATA STRUCTURES

4. CUR->NEXT = NULL /* Store NULL in CUR->NEXT */

5. free(TEMP) /* Delete the last Node, using the address stored in the TEMP */
6. Exit
Implementation in C:
void dellast()
{ node *temp, *cur=head;
while(cur->next->next!=NULL)
{
cur=cur->next;
}
temp=cur->next;
cur->next=NULL;
free(temp);
}
(c) Deleting the node at the given position (At Middle of the List)
Algorithm DELMID(HEAD, POS)
/* This algorithm delete the middle node at the given position of the list */
1. Start
2. Get the POS to delete the node in that position
3. Move the CUR to the previous node of a node at the POS. If POS is not available print the error.
4. TEMP = CUR->NEXT /* Copy address in CUR->NEXT to TEMP */
5. CUR->NEXT = TEMP->NEXT /* Copy address stored in TEMP->NEXT to CUR->NEXT */
6. free(TEMP) /* Delete the Node at the given POS, using the address stored in the TEMP */
7. Exit
This is illustrated in figure 1.5.
Implementation in C:
void delmid()
{ int i=1, pos;
node *temp, *cur=head;
printf("\nEnter the position to delete...");
scanf("%d", &pos);
while( i != pos - 1 && cur->next!=NULL)
{
cur = cur->next;
i++;
Department of IT, Panimalar Engineering College, Chennai.
12
 CS8391 DATA STRUCTURES

}
if( i == pos -1)
{
temp=cur->next;
cur->next=temp->next;
free(temp);
}
else
printf(“List is Small, Unable to find the Position”);
}

head 7088 1080 7060 1024

7088 8 1080 6 7060 7 1024 2 NULL

(a) Before deletion

head 7088 1080 7060 1024

7088 8 1080 6 7060 7 1024 2 NULL

(b) During deletion operation

head 7088 7060 1024

7088 8 7060 7 1024 2 NULL

(c) After deletion

Figure 1.5 Linked List Deletion Operation

1.11 DOUBLY-LINKED LIST

A more sophisticated kind of linked list is a doubly-linked list or two-way linked list, in which
each node has two links: one points to the previous node, or points to a null value or empty list if it is the
first node; and one points to the next, or points to a null value or empty list if it is the final node.

*prev data *next

Null 15 56 27 Null

First Node Last Node

Figure 1.6 Doubly Linked List

Department of IT, Panimalar Engineering College, Chennai.

13
 CS8391 DATA STRUCTURES

Node Structure:
typedef struct nodetype
{
int info;
struct nodetype *next;
struct nodetype *prev;
}node;
Operation:
(i) Insert new node at the beginning of the list
Algorithm:
INSFIRST(HEAD, ITEM)
/* This algorithm inserts ITEM as the first node in the list */
1. Start
2. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
3. TEMP->INFO = ITEM /* Store the ITEM in the INFO part of the TEMP node */
4. TEMP->NEXT = HEAD /* Address of Starting Node is Copied to NEXT part of the TEMP node
*/
5. TEMP->PREV = NULL
6. HEAD->PREV=TEMP
7. HEAD = TEMP /* Address of New node is copied to the HEAD. Now the new becomes the
first node of the LIST. */
8. Exit
This is illustrated in figure1.7:
During Insertion:
Null 10 20 30 Null

HEAD

Null 5

TEMP

After insertion:

Null 5 10 20 30 Null
HEAD
Figure 1.7 Doubly Linked List Insert Operation
Department of IT, Panimalar Engineering College, Chennai.
14
 CS8391 DATA STRUCTURES

Implementation in C:
/* head is global variable, holds the address of the first node in the linked list and structure node is
defined globally */
void addfirst()
{ node *temp;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->info);
temp->next = head;
temp->prev = NULL;
head->prev = temp;
head = temp;
}
(ii) Insert new node at the middle
Algorithm INSMID(HEAD, POS, ITEM)
1. Start
2. Get the position POS, where the new node should be inserted after the POS.
3. Move the CUR pointer to that POS in the list. If the POS is not available display error message.
4. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
5. TEMP->INFO = ITEM /* Store the ITEM in the INFO part of the TEMP node */
6. TEMP->NEXT = CUR->NEXT /* Address in CUR->NEXT is Copied to NEXT part of the
TEMP node */
7. TEMP->PREV = CUR
8. CUR->NEXT->PREV = TEMP
9. CUR->NEXT = TEMP /* Address in TEMP is copied to the CUR->NEXT. Now the new
node is inserted at the given POS of the LIST. */
10. Exit
This is illustrated in figure 1.8:
During Insertion:
Null 10 20 30 Null

HEAD CUR

25

TEMP
Department of IT, Panimalar Engineering College, Chennai.
15
 CS8391 DATA STRUCTURES

After Insertion:

Null 10 20 25 30 Null

HEAD
Figure 1.8 Doubly Linked List Insert Operation
Implementation in C:
void addmid( )
{
int i=1, pos;
node *cur=head , *temp;
printf("\nEnter the position to insert...");
scanf("%d", &pos);
while( i != pos && cur!=NULL)
{
cur = cur->next;
i++;
}
if( i == pos)
{
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item for the node...");
scanf("%d",&temp->info);
temp->next = cur->next;
temp->prev = cur;
cur->next -> prev = temp;
cur->next = temp;
}
else
printf(“List is Small, Unable to find the Position”);
}

(iii) Inserting at the end of a List

Algorithm INSLAST(HEAD, ITEM)
/* This algorithm inserts ITEM as the last node in the list */
1. Start
2. Move the CUR pointer to the last node of the list.
Department of IT, Panimalar Engineering College, Chennai.
16
 CS8391 DATA STRUCTURES

3. Create a new node using malloc. And store the address of new node in TEMP. Error displayed if
no free memory available.
4. TEMP->INFO = ITEM
5. TEMP->NEXT = NULL
6. TEMP->PREV=CUR;
7. CUR->NEXT = TEMP
8. Exit

Implementation in C:
void addlast()
{ node *temp, *cur = head;
while(cur->next!=NULL)
cur=cur->next;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to insert... ");
scanf("%d", &temp->info);
temp->next = NULL;
temp->prev=cur;
cur->next = temp;
}

iv) Delete the first node

Algorithm DELFIRST(HEAD)
/* This algorithm deletes the first node of the list */
1. Start
2. TEMP = HEAD /* Copy address in HEAD to TEMP */
3. HEAD = HEAD->NEXT /* Copy address in HEAD->NEXT to HEAD */
4. HEAD->PREV = NULL
5. free(TEMP) /* Delete the First Node, using the address stored in the TEMP */
6. Exit

Implementation in C:
void delfirst()
{
node *temp;
temp=head;

Department of IT, Panimalar Engineering College, Chennai.

17
 CS8391 DATA STRUCTURES

head = head->next;
head->prev = NULL;
printf(“ Deleted Node is:%d”,temp->info);
free(temp);
}

v) Delete the middle node

Deleting the node at the given position (At Middle of the List) algorithm:
DELMID(HEAD, POS)
/* This algorithm deletes the last node of the list */
1. Start
2. Get the POS to delete the node in that position
3. Move the CUR to the previous node of the POS positioned node. If POS is not available print the
error.
4. If POS is reached do the following
5. TEMP = CUR -> NEXT
6. CUR->NEXT = TEMP->NEXT
7. TEMP->NEXT->PREV = CUR
8. free(TEMP)
9. Exit
Implementation in C:
void delmid()
{ int i=1, pos;
node *temp, *cur=head;
printf("\nEnter the position to delete...");
scanf("%d", &pos);
while( i != pos - 1 && cur->next!=NULL)
{
cur = cur->next;
i++;
}
if( i == pos -1)
{
temp=cur->next;
cur->next=temp->next;

Department of IT, Panimalar Engineering College, Chennai.

18
 CS8391 DATA STRUCTURES

temp->next->prev=cur;
printf(“The deleted elements is:%d”,temp->info);
free(temp);
}
else
printf(“List is Small, Unable to find the Position”);
}

vi) Delete the Last node

Algorithm DELLAST(HEAD)
/* This algorithm deletes the last node of the list */
1. Start
2. Move CUR pointer to the previous node of the last node
3. TEMP = CUR->NEXT /* Copy address in CUR->NEXT to TEMP */
4. CUR->NEXT = NULL /* Store NULL in CUR->NEXT */
5. free(TEMP) /* Delete the last Node, using the address stored in the TEMP */
6. Exit

Implementation in C:
void dellast()
{ node *temp, *cur=head;
while(cur->next->next!=NULL)
{
cur=cur->next;
}
temp=cur->next;
cur->next=NULL;
free(temp);
}

Circular-linked list
In a circular-linked list, the first and final nodes are linked together. This can be done for both
singly and doubly linked lists. To traverse a circular linked list, we begin at any node and follow the list
in either direction until we return to the original node.

Department of IT, Panimalar Engineering College, Chennai.

19
 CS8391 DATA STRUCTURES

Singly-circular-linked list
In a singly-circular-linked list, each node has one link, similar to an ordinary singly-linked list,
except that the next link of the last node points back to the first node.

First Node Last Node

10 20 30 40

Figure 1.9 Singly Circular Linked List

Creation of Singly Circular Linked List

void create()
{
node *newnode,*curr=head;
int i=1,x;
printf(“Enter the no.of nodes to be created”);
scanf(“%d”,&n);
while(i<=n)
{
newnode=(node*)malloc(sizeof(node));
printf(“Enter the data”);
scanf(“%d”,&x);
newnode->data=x;
newnode->next=NULL;
if(head==NULL)
head=newnode;
else
{
while(curr->next!=NULL)
curr=curr->next;
curr->next=newnode
}
i++;
}
newnode->next=head;
}

Department of IT, Panimalar Engineering College, Chennai.

20
 CS8391 DATA STRUCTURES

Routine – Insertion at the beginning

/* head is global variable, holds the address of the first node in the linked list and structure node is
defined globally */
void addfirst()
{
node *temp, *cur=head;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->data);
temp->next = head;
while(cur->next!=head)
cur=cur->next;
cur->next=temp;
head=temp;
}
Routine for Insertion at the End
/* head is global variable, holds the address of the first node in the linked list and structure node is
defined globally */
void addlast()
{
node *temp, *cur = head;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->data);
while(cur->next!=head)
cur=cur->next;
temp->next=curr->next
cur->next = temp;
}
Routine for Deletion at the Beginning
void delfirst()
{
node *temp =*cur=head;
while(curr->next!=head)
cur=cur->next;
Department of IT, Panimalar Engineering College, Chennai.
21
 CS8391 DATA STRUCTURES

head=temp->next;
cur->next=head;
free(temp);
}
Routine for Deletion at the End
void dellast()
{
node *temp, *cur=head;
while(cur->next->next!=head)
{
cur=cur->next;
}
temp=cur->next;
cur->next=head;
free(temp);
}
Doubly-circular-linked list
In a doubly-circular-linked list, each node has two links, similar to a doubly-linked list, except
that the previous link of the first node points to the last node and the next link of the last node points to
the first node. As in doubly-linked lists, insertions and removals can be done at any point with access to
any nearby node.

First Node Last Node

5 10 15 20

Figure 1.10 Doubly Circular Linked List

Creation of Doubly Circular Linked List

void create()
{
node *newnode,*curr=head;
int i=1,x;
printf(“Enter the no.of nodes to be created”);
scanf(“%d”,&n);
while(i<=n)
Department of IT, Panimalar Engineering College, Chennai.
22
 CS8391 DATA STRUCTURES

{
newnode=(node*)malloc(sizeof(node));
printf(“Enter the data”);
scanf(“%d”,&newnode->data);
newnode->prev=NULL;
newnode->next=NULL;
if(head==NULL)
head=newnode;
else
{
while(curr->next!=NULL)
curr=curr->next;
curr->next=newnode;
newnode->prev=curr;
}
i++
}
newnode->next=head;
head->prev=newnode;
}
Routine – Insertion at the beginning
void addfirst()
{
node *temp,*cur=head;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to push... ");
scanf("%d", &temp->data);
temp->next = head;
head->prev = temp;
while(cur->next!=head)
cur=cur->next;
cur->next=temp;
temp->prev=cur;
head = temp;
}
Department of IT, Panimalar Engineering College, Chennai.
23
 CS8391 DATA STRUCTURES

Routine for Insertion at the End

void addlast()
{
node *temp, *cur = head;
while(cur->next!=head)
cur=cur->next;
temp = (node *) malloc(sizeof(node));
printf("\nEnter the item to insert... ");
scanf("%d", &temp->data);
temp->next = cur->next;
temp->prev=cur;
cur->next = temp;
head->prev=temp;
}
Routine for Deletion at the beginning
void delfirst()
{
node *temp;
temp=head;
cur=head;
temp->next->prev=temp->prev;
while(cur->next!=head)
cur=cur->next;
cur->next=temp->next;
head=temp->next;
printf(“ Deleted Node is:%d”,temp->data); free(temp);
}
Routine for Deletion at the end
void dellast()
{
node *temp,*cur=head;
while(cur->next!=head)
{
cur=cur->next;
}
Department of IT, Panimalar Engineering College, Chennai.
24
 CS8391 DATA STRUCTURES

temp=cur;
cur->prev->next=cur->next;
head->prev=cur->prev;
free(temp);
}
Advantages of Linked List
1. Linked List is dynamic data structure; the size of a list can grow or shrink during the program
execution. So, maximum size need not be known in advance.
2. The Linked List does not waste memory
3. It is not necessary to specify the size of the list, as in the case of arrays.
4. Linked List provides the flexibility in allowing the items to be rearranged.

Pitfalls encountered in single linked list

1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose
link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

Applications of linked list

❖ To implement of Stack, Queue, Tree, Graph etc.,
❖ Polynomial Manipulation
❖ To maintain Free-Storage List in memory
1.6 Polynomial Manipulation:
Linked lists can be used to represent polynomials and the different operations that can be
performed on them.
Polynomial Representation:
A polynomial, p(x) is an expression in variable x of the form (axn + bxn-1 +….+ jx + k) where a, b,
c …., k are real numbers and n is a non-negative integer. The constant factor of a polynomial term is
called the coefficient of the term. The n, n-1…..1 are called the exponents and the degree of the
polynomial is n. A single polynomial term or the sum of two or more polynomial terms is called a
polynomial.
In data structure, a polynomial can be represented as a list of nodes where each node consists of
coefficient and an exponent.
Example:
3x^3 + 4x^2 + 5X is a polynomial expression and it can be represented as linked list as shown below.

Department of IT, Panimalar Engineering College, Chennai.

25
 CS8391 DATA STRUCTURES

co-eff expo *next

3 3 4 2 5 1 null

First Node Last Node

Figure 1.23 Polynomial Expression

Here, each node is composed of co-efficient, exponent and a pointer to the next node. Operations like
addition, subtraction, multiplication can be performed using linked list.

Addition of two polynomial expressions:

Adding polynomial is just a matter of combining the like terms. Like terms are terms whose variables
(and their exponents such as the 2 in x2) are the same.

Example: Add 2x2 + 6x + 5 and 3x2 - 2x - 1

Start with: 2x2 + 6x + 5 + 3x2 - 2x – 1

Place like terms together: 2x2 + 3x2 + 6x - 2x + 5–1

Add the like terms: (2+3)x2 + (6-2)x + (5-1)

= 5x2 + 4x + 4

Program to add two polynomial expressions:

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1=NULL,*poly2=NULL,*poly=NULL;

void create(struct link *node)

{
char ch;
do
{
Department of IT, Panimalar Engineering College, Chennai.
26
 CS8391 DATA STRUCTURES

printf("\n enter coeff:");

scanf("%d",&node->coeff);
printf("\n enter power:");
scanf("%d",&node->pow);
node->next=(struct link*)malloc(sizeof(struct link));
node=node->next;
node->next=NULL;
printf("\n continue(y/n):");
ch=getch();
}
while(ch=='y' || ch=='Y');
}
void show(struct link *node)
{
while(node->next!=NULL)
{
printf("%dx^%d",node->coeff,node->pow);
node=node->next;
if(node->next!=NULL)
printf("+");
}
}
void polyadd(struct link *poly1,struct link *poly2,struct link *poly)
{
while(poly1->next && poly2->next)
{
if(poly1->pow>poly2->pow)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
else if(poly1->pow<poly2->pow)
{
poly->pow=poly2->pow;
Department of IT, Panimalar Engineering College, Chennai.
27
 CS8391 DATA STRUCTURES

poly->coeff=poly2->coeff;
poly2=poly2->next;
}
else
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff+poly2->coeff;
poly1=poly1->next;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
while(poly1->next || poly2->next)
{
if(poly1->next)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
if(poly2->next)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
}
void main()
{
Department of IT, Panimalar Engineering College, Chennai.
28
 CS8391 DATA STRUCTURES

char ch;
do
{
poly1=(struct link *)malloc(sizeof(struct link));
poly2=(struct link *)malloc(sizeof(struct link));
poly=(struct link *)malloc(sizeof(struct link));
printf("\nenter 1st number:");
create(poly1);
printf("\nenter 2nd number:");
create(poly2);
printf("\n1st Number:");
show(poly1);
printf("\n2nd Number:");
show(poly2);
polyadd(poly1,poly2,poly);
printf("\nAdded polynomial:");
show(poly);
printf("\n add two more numbers:");
ch=getch();
}
while(ch=='y' || ch=='Y');
}
PART – A (TWO MARK QUESTIONS AND ANSWERS)
1. Define Data Structure.
A data structure is a way of organizing data that considers not only the items stored, but also their
relationship to each other. Advance knowledge about the relationship between data items allows
designing of efficient algorithms for the manipulation of data.
2. List the operations performed in the Linear Data Structure
a) Traversal – Processing each element in the list
b) Search – Finding the location of the element with a given value.
c) Insertion / Storing – Adding a new element to the list.
d) Deletion – Removing an element from the list.
e) Sorting – Arranging the elements in some type of order.
f) Merging – Combining two lists into a single list.

Department of IT, Panimalar Engineering College, Chennai.

29
 CS8391 DATA STRUCTURES

3. What is ADT?
Abstract data type (ADT) is a specification of a set of data and the set of operations that can be
performed on the data.
The abstract data type is written with the help of instances and operations. In ADT instances
represent the elements on which various operations can be performed.
4. Define Array.
An array is a collection of elements of similar data type that are referred to through a common name.
It is simply a grouping similar data items.
The elements in the array are stored in contiguous memory locations. A specific element in an array is
accessed by an index or subscript. Subscript or index should not be negative. The first element of array will
have index as zero.
5. Write the limitations of arrays.
a) Arrays have a fixed dimension. Once the size of an array is decided it cannot be increased or
decreased during execution.
b) Array elements are always stored in contiguous memory locations. So it need contiguous
locations otherwise memory will not be allocated to the arrays
c) Operations like insertion of a new element in an array or deletion of an existing element from the
array are pretty tedious. This is because during insertion or deletion each element after the
specified position has to be shifted one position to the right or one position to the left.
6. What are the ways to represent the two-dimensional array in memory?
Two-dimensional arrays can be represented in two ways.
1. Row Major Order
2. Column Major Order
7. Calculate the address of the element a[2][4] of an array a[3][5] in row-major order
representation.
Formula: Base address + (Row number * Number of Columns + Column number) * element size
int a[3][5];
The location of a[2,4] can be computed as follows:
Row number = 2
Column number = 4
Number of rows in array = 3
Number of columns in array = 5
Location of a[2,4] = Base address(a) + ( 2 * 5 + 4) * 2
= Base address(a) + 28
We may confirm the fact that a[2][4] is 28 units past of base address(a)
Department of IT, Panimalar Engineering College, Chennai.
30
 CS8391 DATA STRUCTURES

8. What is structure in C?
Representing a collection of different types of data items using a single name is called structure. C
supports a constructed data type known as structures –“a mechanism of packing data of different types”.
9. Explain Linked List
A linked list is a list of elements in which the elements of the list can be placed anywhere in memory,
and these elements are linked with each other using an explicit link field, that is by storing the address of
the next element in the link field of the previous element.
A linked list is a self-referential data type because it contains a pointer or link to another data of the
same type. This permit insertion and removal of nodes at any point in the list in constant time, but do not
allow random access.
10. What is a node?
Each structure in a linked list called node, containing two fields one is data and another is address of
next node.
DATA ADDRESS

11. What are the advantages of Linked List

1. Linked List is dynamic data structure; the size of a list can grow or shrink during the program
execution. So, maximum size need not be known in advance.
2. The Linked List does not waste memory
3. It is not necessary to specify the size of the list, as in the case of arrays.
4. Linked List provides the flexibility in allowing the items to be rearranged.
12. What are the pitfalls encountered in single linked list?
1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose
link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.
13. What are the Applications of linked list?
a) Implementation of Stack
b) Implementation of Queue
c) Implementation of Tree
d) Implementation of Graph
14. What are the different types of Linked list?
There are different kinds of linked list. They are
1. Singly Linked List
2. Circular Linked List
3. Two-way or doubly linked lists
4. Circular doubly linked lists
Department of IT, Panimalar Engineering College, Chennai.
31
 CS8391 DATA STRUCTURES

15. Explain the term dynamic memory.

The dynamic memory allocation means one can allocate the memory of required size, as well as de
allocate (free) it, so that freed memory can be utilized further.
16. What is the difference between Array and Linked List?

Array Linked list

Static memory Dynamic memory
Insertion and deletion required Insertion and deletion are made
to modify the existing element easy.
location
Elements stored as contiguous Element stored as Non-
memory as on block. contiguous memory as pointers
Accessing element is fast Accessing element is slow

17. What is the advantage of circular linked list?

In the circular linked list the next pointer of the last node points to the first node of the linked list. so
one can quickly access the first node when he is accessing the last node, which in turn improves the
efficiency of the algorithm as compared to the singly linked list.
18. What are the advantages of doubly linked list over singly linked list.
The doubly linked list has two pointer fields. One field is previous link field and another is next
link field. Because of these two pointer fields we can access any node efficiently whereas in singly linked
list only one pointer field is there which stores forward pointer, which makes accessing of any node
difficult.
19. Write the algorithm to count the number of nodes in a singly linked list.
void count()
{
node *temp;
int count;
temp = head;
while(temp != NULL)
{
count = count + 1;
temp = temp ->next;
}
printf(“\n the total number of nodes are:%d”,count);
}

Department of IT, Panimalar Engineering College, Chennai.

32