Data structures

UNIT I LINEAR DATA STRUCTURES

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 operation (Insertion, Deletion, Merge, Traversal).

1. INTRODUCTION TO DATA STRUCTURES

Data structures

Data Structures is a means of storing a collection of data. It is the specification of the elements
of the structure, the relationship between them and the operations that may be performed upon
them.

Types of Data Structures

Data structures can be classified based on the organization and the operations defined on it.




Fig: 1.1 Types of Data Structures

Linear and non-linear structure: Simple data structures can be combined in various ways to
form more complex structure. There are two kinds of complex data structure. They are linear
& non-linear, depending on the complexity of the logical relationship they represent

 Linear data structure: Stacks, queues, linear linked list, arrays

 Non- linear data structure: Tree and graph tables, sets.

Linear Data Structures

All the elements form a sequence or maintain a linear ordering. Data‟s are organized in
a sequential manner.

,Non Linear Data Structures

If all the elements are organized in a distributed manner then it was termed as Non-linear data
structures

2. EXPLAIN THE ABSTRACT DATA TYPE.(5 M)

 Abstract data type (ADT) is a specification of a set of data and the set of operations
that can be performed on the data.
 Objects such as lists, sets, and graphs, along with their operations, can be viewed
as abstract data types, just as integers, real, and Booleans are data types.
 Set of operations --- each operation does a specific task.
 ADT is a small function, a subprogram, which cannot be implemented as such, as it
contains only the essential things and lacks the rest.

Operations on ADT :

1. Insertion at first, last and middle
2. Deletion at first, last and middle
3. Modifying the list,
4. Reversing the list,
5. Merging the list

Uses of ADT: -
1. It helps to efficiently develop well designed program
2. Facilitates the decomposition of the complex task of developing a software system into
a number of simpler subtasks
3. Helps to reduce the number of things the programmer has to keep in mind at any time
4. Breaking down a complex task into a number of earlier subtasks also simplifies testing
and debugging

3. EXPLAIN THE THE LIST ADT(5 M)

 List is the collection of related data items.
 Eg: Name list (collection of names)

List of ADT’s:
1. Insertion at first,middle,last
2. Deletion at first,middle,last
3. Searching
4. Reversing
5. Traversing

,Implementation of LIST ADT:
1) Array Implementation
2) Linked List Implementation(using Pointers)

4. DESCRIBE THE ARRAY IMPLEMENTATION.(10 M)

Arrays
 It is the collection of related data items, stored in a continuous way.
 The very common linear structure is array. Since arrays are usually easy to traverse,
search and sort, they are frequently used to store relatively permanent collections of data.
 An array is a list of a finite number n of homogeneous data elements (i.e., data elements
of the same type) such that:
a) The elements of the array are referenced respectively by an index consisting of n
consecutive numbers.
b) The elements of the array are stored respectively in successive memory locations.

ARRAY ADTS:

1. Creation:
Void create(int a[20], int n)
{
int i; for(i=0;i<n;i+
+)
scanf(“%d”,&a[i]);
}
Example: Let n=5
1020 1022 1024 1026 1028




2. Insertion at first:
Void ins_first(int a[ ],int x,int n)
{
int i;
for(i=n-1;i>=0;i--)
a[i+1]=a[i];
a[0]=x;
}
Let the no to be inserted be 2

, 3. Insertion at middle:
Void ins_middle(int a[ ], int num,int n,int pos)
{
int i;
for(i=n-1;i>=pos;i--)
a[i+1]=a[i];
a[pos]=num;
}
Let the no to be inserted be 6 at pos 4

4. Insertion at LAST:
Void ins_end(int a[ ],int num,int n)
{
a[n]=x;
n=n+1;
}

5. Deletion at first: Let the no to be inserted at last be 16
Void del_first(int a[ ],int n)
{
int i; n=n-1;
for(i=0;i<n;i++)
a[i]=a[i+1];

}
After deletion at the first the array looks like


6. Deletion at middle:
Void del_middle(int a[ ],int pos,int n)
{
int i; n=n-1;
for(i=pos;i<n;i++)
a[i]=a[i+1];
Afer deletio at the middle at pisitio 3
}

7. Deletion at end:
Void del_end(int a[ ],int n)
{




4