DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS8391 DATA STRUCTURE

BABU G
AP / CSE
1
 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).

2
Introduction to DS
Data:
A collection of facts, concepts, figures, observations, occurrences or instructions
in a formalized manner.
Information:
The meaning that is currently assigned to data by means of the conventions
applied to those data(i.e. processed data)
Record:
Collection of related fields.
Data type:
Set of elements that share common set of properties used to solve a program.

3
Data Structures:
Data Structure is the way of organizing, storing, and retrieving
data and their relationship with each other.

Characteristics of data structures:

1. It depicts the logical representation of data in computer memory.
2. It represents the logical relationship between the various data
elements.
3. It helps in efficient manipulation of stored data elements.
4. It allows the programs to process the data in an efficient manner.

Operations of data structures:

1. Operating System
2. Compiler Design
3. Statistical and Numerical Data Analysis
4. Database Management System
5. Network Analysis 4
Classification of Data Structure

5
• Primitive Data Structure:
• A Primitive Data Structure used to represent the standard data types of any one
of the computer languages (integer, Character, float etc.).

• Non - Primitive Data Structure :

• A Non - Primitive Data Structure can be constructed with the help of any
one of the primitive data structure.
• It can be structure and it is having a specific functionality.
• It can be designed by user.
• It can be classified as Linear and Non-Linear Data Structure.

6
Linear Data Structures:
A linear data structure traverses the data elements sequentially, in which only one
data element can directly be reached.

Ex: Arrays, Linked Lists ,Stacks, Queues

1. Static Linear Data Structures:(Fixed in Size)
In this type DS is created using Static memory allocation. (i.e) DS is
formed when the No. of data items are needed must known in advance.
2. Dynamic Linear Data Structures:(Variable in Size)
In this type DS is created using Dynamic memory allocation. (i.e) DS is
formed when the No. of data items are needed is not known in advance.

Non-Linear Data Structures:

Data Elements are arranged in hierarchical arrangements. The data items are not
arranged in a sequential structure.

Ex: Trees, Graphs ,Heaps 7

Operations on Data Structures
• The basic operations that are performed on data structures are as follows:
• Traversal: Traversal of a data structure means processing all the data elements
present in it exactly once.
• Insertion: Insertion means addition of a new data element in a data structure.
• Deletion: Deletion means removal of a data element from a data structure if it is
found.
• Searching: Searching involves searching for the specified data element in a data
structure.
• Sorting: Arranging data elements of a data structure in a specified order is called
sorting.
• Merging: Combining elements of two similar data structures to form a new data
structure of the same type, is called merging.

8
 Abstract Data Types (ADTs)
• The process of providing only the essentials and hiding the other details
is known as abstraction.
• An Abstract Data Type is a mathematical model of a data structure. It
describes a container which holds a finite number of objects where the
objects may be associated through a given binary relationship.
• The implementation is not visible to the others (or) users
Some of the ADT’s are: List, Stack, Queue, Trees, Graphs
Example for Stack ADT:
long stack_create();
void push(items);
void pop();
void delete(stack); 9
The above ADT can be used in the following ways as:

long stack;
struct st*s;
stack= stack_create();
push(s);
display(stack);
pop(stack);

10
11
 The LIST ADT
• A list or sequence is an abstract data type that represents a countable number of
ordered values, where the same value may occur more than once.
A sequence of zero or more elements
A1 , A2 , A 3 , … A N
N: length of the list
A1: first element
AN: last element Ai: position i
If N=0, then empty list
Linearly ordered
Ai precedes Ai+1
Ai follows Ai-1

Lists are a basic example of containers, as they contain other values. If the same
value occurs multiple times, each occurrence is considered a distinct item. 12
Operations
• A list contains elements of same type arranged in sequential order and
following operations can be performed on the list.
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.
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.

13
 Implementation of LIST
ADT
• Each operation associated with the ADT is implemented by one or
more subroutines

• Two standard implementations for the list ADT

• Array-based implementations
• Linked list implementations
• An array is a random access data structure, where each element can be
accessed
directly and in constant time.
• A typical illustration of random access is a book - each page of the book can be
open independently of others.
• A linked list is a sequential access data structure, where each element can
be accessed only in particular order.
• A typical illustration of sequential access is a roll of paper or tape - all prior material must
be unrolled in order to get to data you want.
14
 An Array-based Implementation (LIST)
• An Array is a data structure which can store a fixed-size sequential collection
of elements of the same type.
(An array is used to store a collection of data, but it is often more useful to think of an array as
a collection of variables of the same type.)
• Instead of declaring individual variables, such as number0, number1, ..., and
number99, you declare one array variable such as numbers and use
numbers[0], numbers[1], and ..., numbers[99] to represent individual variables.
• A specific element in an array is accessed by an index.
• All arrays consist of contiguous memory locations. The lowest address
corresponds to the first element and the highest address to the last element.

15
16
Operations:
Is Empty(LIST)
If (Current Size==0) "LIST is Empty"
else "LIST is not Empty"
Is Full(LIST)
If (Current Size=Max Size) "LIST is
FULL"
else "LIST is not
FULL“
Insert Element to End of the
LIST
1. Check that weather the List is full
or not
1. If List is full return error
message ”List is full. Can’t
Insert”.
2. If List is not full.
1. Get the position to 17
Delete Element from End of the LIST
1. Check that weather the List is empty or not
1. If List is empty return error message ”List is Empty. Can't Delete”.
2. If List is not Empty.
1. Get the position of the element to delete by Position=Current Size
2. Delete the element from the Position
3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1

Insert Element to front of the LIST

2. Check that weather the List is full or not
1. If List is full return error message ”List is full. Can't Insert”.
2. If List is not full.
1. Free the 1st Position of the list by moving all the Element to one position forward i.e New
Position=Current Position + 1.
2. Insert the element to the 1st Position
3. Increase the Current Size by 1 i.e. Current Size=Current Size+1

18
Delete Element from front of the LIST
1. Check that weather the List is empty or not
1. If List is empty return error message ”List is Empty. Can't Delete”.
2. If List is not Empty.
1. Move all the elements except one in the 1st position to one position backward i.e New Position=
Current Position -1
2. After the 1st step, element in the 1st position will be automatically deleted.
3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1
Insert Element to nth Position of the LIST
2. Check that weather the List is full or not
1. If List is full return error message ”List is full. Can't Insert”.
2. If List is not full.
1. If List is Empty, Insert element at Position 1.
2. If (nth Position > Current Size)
1. Return message “nth Position Not available in List”
3. else
1. Free the nth Position of the list by moving all Elements to one
position
forward except n-1,n-2,... 1 Position i.e move only from n to current
size position Elements. i.e New Position=Current Position + 1.
2. Insert the element to the nth Position
3. Increase the Current Size by 1 i.e. Current Size=Current Size+1
19
Delete Element from nth Position of the LIST
1. Check that weather the List is Empty or not
1. If List is Empty return error message ”List is Empty.”
2. If List is not Empty.
1. If (nth Position > Current Size)
1. Return message “nth Position Not available in List”
2. If (nth Position == Current Size)
1. Delete the element from nth Position
2. Decrease the Current Size by 1 i.e. Current Size=Current Size-1
3. If (nth Position < Current Size)
1. Move all the Elements to one position backward except n,n-1,n-2,... 1 Position i.e move
only
from n+1 to current size position Elements. i.e New Position=Current Position - 1.
2. After the previous step, nth element will be deleted automatically.
3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1

20
Search Element in the LIST
1. Check that weather the list is empty or not.
1. If List is empty, return error message “List is Empty”.
2. If List is not Empty
1. Find the Position where the last element available in the List by Last Position = Current Size
2. For( Position 1 to Last Position)
1. If(Element @ Position== Search Element)//If Element matches the search element
2. return the Position by message “Search Element available in Position”
3. Else return message “Search Element not available in the List”
Print the Elements in the LIST
2. Check that weather the list is empty or not.
1. If List is empty, return error message “List is Empty”.
2. If List is not Empty
1. Find the Position where the last element available in the List by Last Position = Current Size
2. For( Position 1 to Last Position)
3. Print the Position and Element available at the position of List.

21
Advantages of array implementation:
1.The elements are faster to access using random access
2.Searching an element is easier

Limitation of array implementation :

1. An array store its nodes in consecutive memory locations
2. The number of elements in the array is fixed and it is not possible to change the number
of elements
3. Insertion and deletion operation in array are expensive.

Applications of arrays:
Arrays are particularly used in programs that require storing large collection of similar type data
elements.

22
Linked List Implementation - LIST
• Like arrays, Linked List is a linear data structure.

• Unlike arrays, linked list elements are not stored at contiguous

location; the elements are linked using pointers.

23
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have
following limitations.

1)The size of the arrays is fixed: So we must know the upper

limit on the number of elements in advance. Also, generally, the
allocated memory is equal to the upper limit irrespective of the usage.

2)Inserting a new element in an array of elements is expensive,

because room has to be created for the new elements and to create room
existing elements have to shifted.

24
For example, in a system if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].

And if we want to insert a new ID 1005, then to maintain the sorted order, we
have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques
are used. For example, to delete 1010 in id[], everything after 1010 has to be
moved.
• Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
• Drawbacks:
1)Random access is not allowed. We have to access elements sequentially
starting from the first node. So we cannot do binary search with linked lists.
2)Extra memory space for a pointer is required with each element of the
list.
25
Representation in C:
A linked list is represented by a pointer to the first node of the linked
list. The first node is called head. If the linked list is empty, then value
of head is NULL.

Each node in a list consists of at least two parts:

1) data
2) pointer to the next node
In C, we can represent a node using structures. Below is an example of a
linked list node with an integer data.

26
 nod
ListStart e next
data null
pointe
r

27
Singly Linked List

28
Doubly Linked List

29
Singly Circular Linked List

30
Doubly Circular Linked List

31
 Comparison of array-based lists and linked lists

Array-based lists Linked lists

no wasted space for an only need space for the

Pro
individual element objects actually on the list

size must be predetermined;

overhead for links (an extra
Con wasted space for lists with
pointer added to every
empty slots
node)

Space complexity Ω(n) (or greater) Θ(n)

32
Applications of List
• Lists can be used to store a list of elements. However, unlike in
traditional arrays, lists can expand and shrink, and are stored
dynamically in memory.

• In computing, lists are easier to implement than sets.

• Lists also form the basis for other abstract data types including the
queue, the stack, and their variations.

33
Polynomial Manipulation

• A polynomial is a mathematical expression consisting of a sum of terms,

each term including a variable or variables raised to a power and
multiplied by a coefficient. The
simplest polynomials have one variable.

• Representation of a Polynomial: A polynomial is an expression

that contains more than two terms. A term is made up of coefficient
and exponent. An example of polynomial is

• P(x) = 4x3+6x2+7x+9

34
A polynomial thus may be represented using arrays or linked lists.
• Array representation assumes that the exponents of the given expression are
arranged from 0 to the highest value (degree), which is represented by the
subscript of the array beginning with 0.
• The coefficients of the respective exponent are placed at an
appropriate index in the array.
• The array representation for the above polynomial expression is
given below:

35
• A polynomial may also be represented using a linked list. A structure
may be defined such that it contains two parts- one is the coefficient and
second is the corresponding exponent. The structure
definition may be given as shown below:
struct polynomial
{
int coefficient;
int exponent;
struct polynomial *next;
};
• Thus the above polynomial may be represented using linked list as shown
below:

36
Here are the most common operations on a
polynomial:
• Add & Subtract
• Multiply
• Differentiate
• Integrate
• etc…
There are different ways of implementing the polynomial ADT:
• Array (not recommended)
• Linked List (preferred and recommended)
Array Implementation:
• p1(x) = 8x3 + 3x2 + 2x + 6
• p2(x) = 23x4 + 18x - 3

• This is why arrays aren’t good to represent polynomials:

• p3(x) = 16x21 - 3x5 + 2x + 6

37
• Advantages of using an Array:

• only good for non-sparse polynomials.

• ease of storage and retrieval.

• Disadvantages of using an Array:

• have to allocate array size ahead of time.

• huge array size required for sparse polynomials. Waste of space and runtime.

38
Linked list Implementation:
• p1(x) = 23x9 + 18x7 + 41x6 + 163x4 + 3
• p2(x) = 4x6 + 10x4 + 12x + 8

Representation

struct polynode {
int coef;
int exp;
struct polynode * coef exp next
next;
};

typedef struct
polynode 39
*polyptr;
• Advantages of using a Linked list:

• save space (don’t have to worry about sparse polynomials) and

easy to maintain
• don’t need to allocate list size and can declare nodes (terms) only as
needed

• Disadvantages of using a Linked list :

• can’t go backwards through the list
• can’t jump to the beginning of the list from the end.

40
Addition of two Polynomials:
• For adding two polynomials using arrays is straightforward method,
since both the arrays may be added up element wise beginning from 0
to n-1, resulting in addition of two polynomials.
• Addition of two polynomials using linked list requires comparing the
exponents, and wherever the exponents are found to be same, the
coefficients are added up.
• For terms with different exponents, the complete term is simply added
to the result thereby making it a part of addition result.

41
Adding polynomials using a Linked list representation: (storing the result in p3)

To do this, we have to break the process down to cases:

Case 1: exponent of p1 > exponent of p2
• Copy node of p1 to end of p3.
• [go to next node]
Case 2: exponent of p1 < exponent of p2
• Copy node of p2 to end of p3.
• [go to next node]
Case 3: exponent of p1 = exponent of p2
• Create a new node in p3 with the same exponent and with the sum of the
coefficients of p1 and p2.
CODING

42
Multiplication of two 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 first polynomial 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.

43
 All Operations (Insertion, Deletion, Merge, Traversal)
• Insertion
• Deletion
• Merge two sorted linked lists
• Traversal
• Assume, that we have a list with some nodes. Traversal is the very basic
operation, which presents as a part in almost every operation on a singly-
linked list.
• For instance, algorithm may traverse a singly-linked list to find a value, find
a position for insertion, etc. For a singly-linked list, only forward direction
traversal is possible.
Traversal algorithm
• Beginning from the head,
• check, if the end of a list hasn't been reached yet;
• do some actions with the current node, which is specific for particular
algorithm; 44
Example
• As for example, let us see an
example of summing up values in
a singly-linked list.

CS8351 - DATA STRUCTURES 41

45