CS8391-Data Structures

Unit-1
Linear Data Structures-List
1.1 Introduction for Data Structure
A data structure is a particular way of collecting, organizing, storing, processing and
retrieving data from computer memory so that it can be used effectively.

For example, we can store a list of items having the same data-type using the array data
structure.

Types of
Data

Structures
Data structures are a very important programming concept. They provide us with a means
to store, organize and retrieve data in an efficient manner. The data structures are used to make
working with our data, easier. There are many data structures which help us with this.
Primitive Data Structures

These are the structures which are supported at the machine level, they can be used to
make non-primitive data structures. These are integral and are pure in form. They have
predefined behavior and specifications.

Examples: Integer, float, character, pointers.

Non-primitive Data Structures

The non-primitive data structures cannot be performed without the primitive data
structures. Although, they too are provided by the system itself yet they are derived data
structures and cannot be formed without using the primitive data structures.

The Non-primitive data structures are further divided into the following categories:

1. Arrays

Arrays are a homogeneous and contiguous collection of same data types. They have a static
memory allocation technique, which means, if memory space is allocated for once, it cannot be
changed during runtime. The arrays are used to implement vectors, matrices and also other data
structures. If we do not know the memory to be allocated in advance then array can lead to
wastage of memory. Also, insertions and deletions are complex in arrays since elements are
stored in consecutive memory allocations.

2. Files

A file is a collection of records. The file data structure is primarily used for managing large
amounts of data which is not in the primary storage of the system. The files help us to process,
manage, access and retrieve or basically work with such data, easily.
3. Lists

The lists support dynamic memory allocation. The memory space allocated, can be changed at
run time also. The lists are of two types:

a) Linear Lists

The linear lists are those which have the elements stored in a sequential order. There will be a
single starting and single ending element.The insertions and deletions are easier in the lists. They
are divided into two types:

 Stacks
 Queues

b) Non Linear Lists

The non linear lists do not have elements stored in a certain manner. The starting element can be
identified and the ending element canot be identified. The types are:

 Graphs
 Trees

Data structures give us a means to work with the data. Since, we already have lots of problems to deal
with, it completely depends on the requirement of our problem which data structure to select. The right
selection of an appropriate data structure for solving a particular problem can prove very beneficial and
also help reduce the complexity of the program.

Abstract Data Types(ADTs)

It is called “abstract” because it gives an implementation-independent view. The process of
providing only the essentials and hiding the details is known as abstraction.

An ADT can be defined as a mathematical model together with a set of well-defined

operations. But it doesn’t mention how it is implemented. This is an extension of modularity.

Objects such as lists, sets , graphs along with their operations are ADTS where as int, char,
Boolean are just data types. For the set ADT, some of the operations are union, intersection,
complement etc.

Advantages:

 Once the operation has been implemented, any other part of program can use this, just by
calling the appropriate function.(Code reuse)
 If any modification has to be done, then changes will take place in only the routine that perform
the ADT operations.(Easier for code maintanence)
Disadvantage:

 Overhead occurs if same function is called several times.

Array implementation of list ADT

In array implementation, elements are stored in contiguous array positions (Figure 1.1).
An array is a viable choice for storing list elements when the elements are sequential, because
it is a commonly available data type and in general algorithm development is
easy.

Figure 1.1 Array Implementation of List ADT

In order to implement lists using arrays we need an array for storing entries –
listArray[0,1,2…..m], a variable curr to keep track of the number of array elements
currently assigned to the list, the number of items in the list, or current size of the list
size and a variable to record the maximum length of the array, and therefore of the list –
maxsize as shown in Figure.
 Figure 1.2 Static Implementation of List ADT

Fix one end of the list at index 0 and elements will be shifted as needed when an element
is added or removed. Therefore insert and delete operations will take O(n). That is if we
want to insert at position 0 (insert as first element),this requires first pushing the entire
array to the right one spot to make room for the new element. Similarly deleting the
element at position 0 requires shifting all the elements in the list left one spot.
One of the important operation associated with lists is the initialization. In this case we
need to first declare the array of list items with maximum number of items say n. This
then requires an estimate of the maximum size of the list. Once we decide the size, then
we `initialize the list with number of items set at 0.

Insertion
What happens if you want to insert an item at a specified position in an existing
array? The item originally at the given index must be moved right one position, and all the
items after that index must be shifted right.

Figure 1.3 Insertion into a List

Let us consider a specific case of Insert operation. Insert (3, K, List)

In this case, 3 is the index or the point of Insertion, K is the element to be inserted & List
is the list in which insertion is to be done.
Figure 1.4 An Example of Insertion into a List

Figure 1.5 List after insertion

//Routine for inserting an element in an array

void insert(int num,int pos, int a[])

int i, size;

if(size==maxsize)

printf(“Array is full”);

else

for(i=size;i>=pos;i--)

a[i+1]=a[i];
 a[pos]=num;

Note:num->new element to be inserted

pos->at which position element has be insrted in array

size->size of array

maxsize->capacity of an array

Deletion from Lists

What happens if you want to remove an item from a specified position in an existing
array? There are two ways in which this can be done:
– Leave gaps in the array, i.e. indices that contain no elements, which in practice,
means that the array element has to be given a special value to indicate that it is
“empty”,

Or

– All the items after the (removed item’s) index must be shifted left similar to what
we did when we wanted to insert – only for insertion we shifted right.
Let us consider a specific case of a Delete operation.
– Delete (3, List). In this case, 3 is the index or the point of Deletion& List is the list
from which deletion is to be done.

Figure 1.6 Deletion from a List

Figure 1.7 After Deletion

//Routine for deleting an element in an array

void Delete(int num,int a[])

int i, j,size;

if(size==0)

printf(“Array is empty”);

else

for(i=0;i<size;i++)

if(a[i]==num)

for(int j=i;j<size;j++)

a[j]=a[j+1];

Note:num->new element to be inserted

pos->at which position element has be insrted in array

 size->size of array

maxsize->capacity of an array

Advantages

 Fast, random access of elements.

 Memory efficient

Disadvantages

 Insertion and deletion are expensive

 Size must be known when the array is created and fixed.