Department of
Computer Science and Engineering
DATA STRUCTURES
Unit 1-Linear structures
Year/Sem : II/III
Subject Code: 1151CS102
Topic : Abstract Data Type
Faculty Name : Vijitha.S
Date : 07.08.2020
School of Computing
Vel Tech Rangarajan Dr. Sagunthala R&D Institute of
Science and Technology
Contents
Abstract Data Type - Definition
Types of ADT
List - Definition
List ADT - Definition
Operations of List ADT
Implementation of list ADT
Array ADT
Array implementation of a list
How to store a list in an array
and Project
Array ADT-operations
Management
(SEPM)
Advantages
8/07/2020 Department of Computer Science and Engineering
Abstract Data Type - Definition
Definition:
Abstract Data type (ADT) is a type for objects
whose behaviour is defined by a set of value and a
set of operations.
Abstract Data type (ADT) only mentions what
operations are to be performed but not how these
operations will be implemented.
The process ofManagement
providing only the essentials and
and Project
hiding the details
(SEPM)
is known as abstraction.
8/07/2020 Department of Computer Science and Engineering
Abstract Data Type - Definition
It does not specify how data will be organized in
memory and what algorithms will be used for
implementing the operations. It is called “abstract”.
“Abstract” it gives an implementation-independent
view.
The user of data type does not need to know how
that data type is implemented.
and Project
A user only needs to know what a data type can do,
Management
(SEPM)
but not know how it will be implemented.
8/07/2020 Department of Computer Science and Engineering
Abstract Data Type
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Types of ADT
Types of ADT:
Abstract Data Type(ADT) has three types
1.List ADT
2.Stack ADT
3.Queue ADT.
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
List
List – Definition:
List is a sequential data structure a collection of
items accessible one after another, it is beginning at
the head and ending at the tail.
Addition and removals can be made at any
position in the list.
Lists are normally in the form of a1,a2,a3.....an. The
and Project
size of this listManagement
is n.
(SEPM)
8/07/2020 Department of Computer Science and Engineering
List ADT
List – Definition:
The first element of the list is a1,and the last
element is an. The position of element ai in a list is i.
List of size 0 is called as null list.
A list is said to be empty when it contains no
elements.
and Project
The number of elements currently stored is called
Management
(SEPM)
the length of the list.
8/07/2020 Department of Computer Science and Engineering
List ADT
List ADT– Definition:
List ADT is the data is generally stored in key
sequence in a list which has a head structure
consisting of i) count,
ii) pointers and
iii) address of compare
function needed to compare the data in the list.
The data node contains the pointer to a data
structure and a self-referential pointer which points
to the next node in the list.
8/07/2020 Department of Computer Science and Engineering
List ADT
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Operations of List ADT
Basic Operations on a List ADT:
Creating a list
Traversing the list
Inserting an item in the list
Deleting an item from the list
Concatenating two lists into one
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Creating a list
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Traversing the list
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Insertion
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Deletion
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Concatenating the two lists
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Other operations
Some Operations on a List ADT:
get() – Return an element from the list at any given
position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any
element from a non-empty list.
removeAt() – Remove the element at a specified
location from a non-empty list.
8/07/2020 Department of Computer Science and Engineering
Other operations of List ADT
replace() – Replace an element at any position by
another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty,
otherwise return false.
isFull() – Return true if the list is full, otherwise
return false. and Project
Management
(SEPM)
toString - Returns a string representation of the list.
8/07/2020 Department of Computer Science and Engineering
Other operations
add - Adds an element to the list (in the correct
place)
addToFront - Adds an element to the front of the list
addToRear - Adds an element to the rear of the list.
addafter - Adds an element after a particular
element already in the list.
and Project
Indexof - Returns the index of the specified element.
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Other operations
removeFirst - Removes the first element from the
list.
removeLast - Removes the last element from the
list.
first - Examines the element at the front of the list.
last - Examines the element at the rear of the list.
and Project
contains - Determines if a particular element is in the
Management
(SEPM)
list.
8/07/2020 Department of Computer Science and Engineering
Implementation of list ADT
Implementation of List ADT:
A list can be implemented in two ways:
1.Array ADT
2.Linked list ADT
8/07/2020 Department of Computer Science and Engineering
Array ADT
Array is a “linear list” or a “contiguous list” where
elements are stored in contiguous array positions.
The implementation specifies an array of a particular
maximum length, and all storage is allocated before
run-time.
It is a sequence of n-elements where the items in the
array are stored with the index of the array related to
the position of the item in the list.
and Project
Management
In array implementation, elements are stored in
(SEPM)
contiguous array positions.
8/07/2020 Department of Computer Science and Engineering
Array ADT
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Array implementation of a list ADT
An array is used for storing list elements when the
elements are sequential.
To implement lists using arrays we need an array for
storing entries – listArray[0,1,2…..m].
The variable keep track of the number of array
elements currently assigned to the list.
The number of anditems
Project
in the list, or current size of the
list size and a variable
Management
(SEPM)
to record the maximum length
of the array.
8/07/2020 Department of Computer Science and Engineering
Time complexity
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
How to store a lists in an array
This implementation stores the list in an array.
The position of each element is given by an index
from 0 to n-1, where n is the number of elements.
The element with the index can be accessed in
constant time ie., the time to access does not
depend on the size of the list.
and Project
The time takenManagement
to add an element at the end of the
(SEPM)
list does not depend on the size of the list.
8/07/2020 Department of Computer Science and Engineering
How to store a lists in an array
But the time taken to add an element at any other
point in the list depends on the size of the list
because the subsequent elements must be shifted to
next index value.
So the additions near the start of the list take longer
time than the additions near the middle or end.
Similarly when an element is removed, subsequent
elements must be shifted to the previous index value.
So removals near the start of the list take longer time
than removalsDepartment
8/07/2020
near ofthe middle or end of the list.
Computer Science and Engineering
How to store a lists in an array
8/07/2020 Department of Computer Science and Engineering
How to store a lists in an array
8/07/2020 Department of Computer Science and Engineering
Array ADT – operations
Array ADT performs the following operations
Insertion
Deletion
Search
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-INSERTION
Pseudocode:
Insert()
declare array A
read n
for (i=0;i<n;i++)
read A[i]
set i=0,j=n
get position k
n=n+1
while( j >= k)
A[j+1] = A[j] and Project
j=j-1 Management
(SEPM)
A[k] =item
print array A
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-INSERTION
Sample code:
int main()
{
int A[] = {1,3,5,7};
int item = 8, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
{
printf("A[%d] = %d \n", i, A[i]);
and Project
Management
} (SEPM)
n = n + 1;
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-INSERTION
while( j >= k)
{
A[j+1] = A[j];
j = j - 1;
}
A[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++)
{
printf("A[%d] = %d \n", i, A[i]);
and Project
} Management
(SEPM)
}
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-INSERTION
Before Insertion:
1 3 5 7
After Insertion:
1 3 5 7 8
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-DELETION
Pseudocode:
delete()
declare array A
read n
for (i=0;i<n;i++)
read A[i]
get position k
j=k
while( j < n)
A[j-1] = A[j]
and Project
j = j + 1 Management
(SEPM)
n=n-1
print array A
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-DELETION
Sample code:
int main()
{
int A[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
{
printf("A[%d] = %d \n", i, A[i]);
and Project
Management
} (SEPM)
j = k;
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-DELETION
while( j < n)
{
A[j-1] = A[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++)
{
printf("A[%d] = %d \n", i, A[i]);
and Project
Management
} (SEPM)
}
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT-DELETION
Before Deletion
1 3 5 7 8
After Deletion:
1 3 7 8
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT- SEARCH
Pseudocode:
search()
declare array A
read n
for (i=0;i<n;i++)
read A[i]
read k(element to be searched)
set f=0
for(i=0;i<n;i++)
if(A[i]==k)
f=1
print i and Project
break Management
(SEPM)
if(f==0)
print “Element not found”
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT- SEARCH
Sample code:
int main()
{
int list[20],size,i,sElement;
printf("Enter size of the list: ");
scanf("%d",&size);
printf("Enter any %d integer values: ",size);
for(i = 0; i < size; i++)
and Project
Management
(SEPM)
scanf("%d",&list[i]);
printf("Enter the element
8/07/2020
to be Search: ");
Department of Computer Science and Engineering
ARRAY ADT- SEARCH
scanf("%d",&sElement);
for(i = 0; i < size; i++)
{
if(sElement == list[i])
{
printf("Element is found at %d index", i);
break;
}
}
and Project
if(i == size) Management
(SEPM)
printf("Given element is not found in the list!!!");
}
8/07/2020 Department of Computer Science and Engineering
ARRAY ADT- SEARCH
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Advantages
Arrays are suitable for
1.Randomly accessing any element.
2.Searching the list for a particular value
3.Inserting or deleting an element at the end.
and Project
Management
(SEPM)
8/07/2020 Department of Computer Science and Engineering
Thank You
Department of Computer Science and Engineering
