UNIT - I

L Abstract Data Types (ADTs): List ADT, Arraybased implementation, Linked list
implementation, Singly linked lists, applications of lists: Polynomial Manipulation,
All operations (Insertion, Deletion, Merge, Traversal).

Data Structures
Data Structures is a way of organizing the data which also includes several operations
to perform on that data.

Applications of Data Structures

 List: used in implementation of File allocation Table (FAT), Process Control Block
(PCB) etc.
 Stack: It is always implicitly used in a program, whether or not we declare it
explicitly, during the program execution.
 Queue: It is used to order the task as they arrive to get the attention of the CPU.
 Tree: Directory Structure is implemented using tree DS.
 Graph: used in Networking and mapping of tasks to processors in multiprocessor
Platforms.
Abstract Data Types (ADTs)
ADT is defined as a mathematical model with a set of operations.
Basic Idea of ADT: The operations are written once in the program. Any other part of
the program can access this operation by calling the appropriate function.
Examples
 Objects such as lists, sets, graph etc along with their operations are ADTs.
 Set of integers together with the operations Union, Intersection and difference form
an example ADT.
 Similarly real Boolean have operations associated with them. So it is ADTs.
Advantages of ADT
1. Modularity
2. Reuse
1
3. Easy to understand
4. Implementation of ADTs can be changed anytime without changing the program that
uses it.
The List ADT
List is an ordered set of elements. General Form of List ADT is
A1, A2, A3, ….AN , Where N is the size of the List.
A1 - First element of the list, A2 - Second element of the list, AN - Last element of
the list
If the element at position i is Ai, Ai-1is the predecessor element, Ai+1 is the successor
element.
Various operations performed on List
1. Insert (X, 3)- Insert the element X after the position 3.
2. Delete (X) - The element X is deleted
3. Find (X) - Returns the position of X.
4. Next (i) - Returns the position of its successor element i+1.
5. Previous (i) Returns the position of its predecessor i-1.
6. Print list - Contents of the list is displayed.
7. Makeempty- Makes the list empty.

Implementation of list ADT

1. Array based Implementation
2. Linked List based implementation
Array Implementation of list
Array is a collection of specific number of same type of data stored in consecutive
memory locations. Array is a static data structure.
i.e., size of the array should be allocated in advance and the size is fixed.
 Insertion and Deletion operation are expensive as it requires more data
movements. Worst case it requires O(N) Movements. Best case it requires O(1).

Fig 1.2 Array Implementation of List

2
The basic operations performed are
 Creation of List.
 Insertion / Deletion of data from the List
 Display all data in the List
 Searching for a data in the list
Creation of List: Create operation is used to create the list with “n” number of elements.
If “n” exceeds the array’s maxsize, then elements cannot be inserted into the list.
Otherwise the array elements are stored in the consecutive array locations (i.e.) list [0],
list [1] and so on.
Insertion / Deletion of data in the List: Insert / Delete operation is used to Insert/ Deletean
element at particular position in the existing list. Inserting/ deleting the element in thelast
position of an array is easy.
But inserting/ Deleting the element at a particular position in an array is quite difficult
since it involves all the subsequent elements to be shifted one position to the right / left.
Display/ Traversal all data in the List: Traversal is the process of visiting the elements
in an array. Display( ) operation is used to display all the elements stored in the list from
the index 0 to n-1.
Searching for a data in the list: Search( ) operation is used to determine whether a
particular element is present in the list or not.

3
Procedure to create / insert / delete
Create Insert Delete
void Insert() void Delete( )
void Create() { int i,pos;
{ int i, data, pos; printf("Enter
{ int i; printf("Enter the
data to insert");scanf("%d",
printf("Enter number of position to delete”);
elements"); &data);
scanf("%d", &pos);
scanf("%d",&n); printf("Enter the position to
insert"); printf("The data
printf("Enter the array deleted is: %d",
elements"); scanf("%d", &pos); list[pos-1]);
for(i=0; i<n; i++) for(i = n-1; i >= pos-1 ; i--) for(i=pos-1;i<n-1;
{scanf("%d", &list[i]); } {list[i+1] = list[i];} i++)
// swap // {list[i]=list[i+1]; }
Display();
list[pos-1] = data; n=n-1;
}
n= n+1; Display(); } Display(); }
Procedure to display / search
Display Search
void Display() void Search()
{ { int search, i, count = 0;
int i; printf("Enter the element to be searched");scanf("%d",
printf("Elements in the &search);
array"); for(i=0; i<n; i++)
for(i=0;i<n;i++) { if(search == list[i])
printf("%d",list[i]); count++; }
} if(count==0)
printf("Element not present ");else
printf("Element present"); }

4
Linked List based implementation
Linked list is an ordered collection of elements. Each element in the list is referred
as a node. Each node contains two fields namely,
1. Data field-The data field contains the actual data of the elements to be stored in the
list.
2. Next / Pointer field- The next field contains the address of the next node in the list

Fig 1.3 Linked Implementation of List

The nodes in the linked list are not necessarily adjacent in memory.

Advantages of Linked list

1. Insertion and deletion of elements can be done efficiently
2. It uses dynamic memory allocation
3. Memory utilization is efficient compared to arrays
Disadvantages of linked list
1. Linked list does not support random access
2. Extra Memory space is required to store next field
3. Searching takes time compared to arrays
Types of Linked List
1. Singly Linked List or One-Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List

5
}

Singly Linked List

A singly linked list is a linked list in which each node contains data field and only one
link field pointing to the next node in the list.

Fig 1.5 Singly Linked List

Head node which always points to the first node. Head node is also called as sentinel
node.

Basic operations on a singly linked list are

1. Insert – Inserts a new node in the list.
2. Delete – Deletes any node from the list.
3. Find – Finds the position (address) of any node in the list.
4. FindPrevious - Finds the position (address) of the previous node.
5. FindNext - Finds the position(address) of the next node in the list.
6. Display - displays the data in the list

6
7. Search - finds whether an element is present in the list or not

Insertion: The insertion into a singly linked list can be performed in 3 ways.

1. Insertion at beginning: It involves inserting any element at the front of the list.

Fig 1.6 Inserting a new element into a Singly Linked List at beginning

2. Insertion at end of the list: It involves insertion at the last of the linked list. It can
be done in 2 ways
a. The node is being added to an empty list (only one node in the list)
b. The node can be inserted as the last one.

Fig 1.7 Inserting a new element into a Singly Linked List at end of the list

7
3. Insertion at a given position (after specified node): It involves insertion after the
specified node of the linked list.

Fig 1.8 Inserting a new element at a given position

Procedure for Inserting a new element into a singly linked list
Insertion at end of the Insertion at a given
Insertion at beginning
list position
void beginsert() void lastinsert() void randominsert()
{struct node *ptr; {struct node *ptr, *temp; {int i,loc,item;
int item; int item; struct node *ptr, *temp;
ptr = (struct node *) ptr = (struct node*) ptr = (struct node *)
malloc(sizeof(struct node)); malloc(sizeof(struct malloc (sizeof(struct
node)); node));
if(ptr == NULL)
if(ptr == NULL) if(ptr == NULL)
{printf("overflow"); }
{printf("overflow"); } {printf("overflow"); }
else
else else
{printf("Enter value");
{printf(“Enter value"); {printf("Enter value");
scanf("%d",&item);
scanf("%d",&item); scanf("%d",&item);
ptrdata = item;
ptrdata = item; ptrdata = item;
ptrnext = head;
if(head == NULL) printf("Enter the
head = ptr;
{ptr  next = NULL; location after which you
printf("Node inserted"); want to insert ");
head = ptr;
} } printf("Node inserted");} scanf("%d",&loc);

8
else temp=head;
{temp = head; for(i=0;i<loc;i++)
while (temp  next != { temp = tempnext;
NULL) if(temp == NULL)
{temp = temp  next; } {printf("can't insert");
tempnext = ptr; return; }
ptrnext = NULL; }
printf("Node inserted");} ptr next =
} tempnext;
} temp next = ptr;
printf("Node inserted");
}
}

Deletion: The deletion into a singly linked list can be performed in 3 ways.
1. Deletion at beginning: deleting an element at the front of the list.

Fig 1.9 Deleting an element at the beginning

2. Deletion at end of the list: It can be done in 2 ways

a. There is only one node in the list and that needs to be deleted.
b. There are more than one node in the list and the last node of the list will be
deleted.
9
Fig 1.10 Deleting a node at end of the list

3. Deletion at a given position (after specified node): It involves deletion after the
specified node of the linked list.

Fig 1.11 Deleting a node at a given position

Procedure for Deleting a node into a singly linked list

Deletion at a given
Deletion at beginning Deletion at end of the list
position
void begin_delete() void last_delete() void random_delete()
{ struct node *ptr; { struct node *ptr,*ptr1; {struct node *ptr,*ptr1;
if(head == NULL) if(head == NULL) int loc,i;
{ printf("List is empty"); {printf("list is empty"); } printf("Enter the location
} else if(head  next == of the node after which
else NULL) you want to perform
deletion");
{ptr = head; { head = NULL;
scanf("%d",&loc);
head = ptrnext;
ptr=head;

10
free(ptr); free(head); printf("Only for(i=0;i<loc;i++)
printf("Node deleted from the node of the list deleted {ptr1 = ptr;
begining ..."); ..."); }
ptr = ptrnext;
} else
if(ptr == NULL)
} {ptr = head;
{printf("Can't delete");
while(ptrnext != NULL)
return; }
{ptr1 = ptr;
}
ptr = ptr next; }
ptr1 next = next;
ptr1next = NULL;
free(ptr); printf("Deleted
free(ptr); node %d ", loc+1);
printf("Deleted Node from }
the last ...");
}
}

Traversing / Display in singly linked list

Traversing means visiting each node of the list once in order to perform some operation
on that. Display the content of linked list.

Search in singly linked list

Comparing each node data with the item to be searched and return the location of the
item in the list if the item found else return null.

Procedure for Display and Search

Display Search
void display() void search()
{ struct node *ptr; { struct node *ptr; int item,i=0,flag;
ptr = head; ptr = head;

11
if(ptr == NULL) if(ptr == NULL)
{ printf("Empty List "); } {printf("Empty List"); }
else else
{ printf("printing values"); {printf("Enter item to search");
while (ptr!=NULL) scanf("%d",&item);
{printf("%d",ptrdata); while (ptr!=NULL)
ptr = ptr -> next; } {if(ptrdata == item)
} {printf("item found at location %d ",i+1);
} flag=0; } else { flag=1; }
i++; ptr = ptr -> next; }
if(flag==1)
{ printf("Item not found\n"); } } }

Applications of lists:
1. Polynomial ADT
2. Radix sort
3. Multilist

Polynomial Manipulation – All operations (Insertion, Deletion, Merge,

Traversal).
Polynomial Implementation:

A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + ….
+ jx + k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.

 i.e A polynomial is an expression that contains more than two terms.

 one is the coefficient
 other is the exponent
P(x) = 4x +6x2+7x+9, here 4,6,7, and 9 are coefficients and 3, 2, 1 is its exponential
3

value 12

Polynomial can be represented in the various ways. These are:

 By the use of arrays

 By the use of Linked List
 Polynomial manipulations such as insertion, deletion, Merge, Traversal , addition,
subtraction & differentiation etc.. can be performed using linked list / array.

Procedure for Polynomial Addition subtraction & differentiation using

linked list:

Declaration of Linked list implementation of Polynomial:

struct poly{

{ int coeff;

int power;

struct poly *next;

} *list1, *list2, *list3;

Creation of Polynomial:

poly create(poly *head, poly *newnode)

{ poly*ptr;
if(head==NULL)

{ head=newnode;

return(head); }
13
else
{ ptr=head;

while(ptr-> next!=NULL)

ptr=ptr->next;

ptr->next=newnode; }

return(head);

}
Addition of Polynomials:
To add two polynomials we need to scan them once. If we find terms with the same
exponent in the two polynomials, then we add the coefficients; otherwise, we copy the
term of larger exponent into the sum and go on. When we reach at the end of one of the
polynomial, then remaining part of the other is copied into the sum.

To add two polynomials follow the following steps:

• Read two polynomials.

• Add them.

• Display the resultant polynomial.

Addition of Polynomials:

void add()

poly *ptr1, *ptr2, *newnode;

ptr1=list1;

ptr2=list2;

while(ptr1!=NULL && ptr2!= NULL)

{ newnode=malloc(sizeof(struct poly));

14
if(ptr1->power==ptr2->power)
{ newnode->coeff = ptr1->coeff + ptr2->coeff;

newnode->power=ptr1->power;

newnode->next=NULL;

list3=create(list3,newnode);

ptr1=ptr->next;

ptr2=ptr2->next;
}

else

{ if(ptr1->power > ptr2->power)

{ newnode->coeff = ptr1->coeff

newnode->power=ptr1->power;

newnode->next=NULL;

list3=create(list3,newnode);

ptr1=ptr1->next; }

else

{ newnode->coeff = ptr2->coeff

newnode->power=ptr2->power;

newnode->next=NULL;

list3=create(list3,newnode);

ptr2=ptr2->next; }

}
15
SUBTRACTION OF POLYNOMIALS:
(add this statement in the above program)

newnode->coeff = ptr1->coeff - ptr2->coeff

MULTIPLICATION OF POLYNOMIALS:
 Multiplication of two polynomials however requires manipulation of each node
such that the exponents are added up and the coefficients are multiplied.
 After each term of firstpolynomial is operated upon with each term of the second
polynomial,
 Then the result has to be added up by comparing the exponents and adding the
coefficients for similar exponents and including terms as such with dissimilar
exponents in the result

void Mul()

poly *ptr1, *ptr2, *newnode;

ptr1=list1;

ptr2=list2;

if(ptr1 == NULL && ptr2 == NULL)

return;

if(ptr1 == NULL) // I polynomial does not exist

list3 = list2;
elsif(ptr2 ==NULL) // II polynomial does not exist

list3 =list1;

else // Both polynomial exist

{ if(ptr1!=NULL && ptr2!= NULL)

16
{ while(ptr1!=NULL)

{ newnode=malloc(sizeof(struct poly));

while(ptr2!=NULL)

{ newnode->coeff = ptr1->coeff * ptr2 ->coeff;

newnode->power=ptr1->power + ptr2->power;

list3=create(list3,newnode);

ptr2=ptr2->next;

}
ptr2=list2;

ptr1=ptr1->next;

} }

}}

17