PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
UNIT I - LINEAR DATA STRUCTURES – LIST, STACK AND QUEUE
List ADT– Singly Linked Lists – Doubly Linked Lists-Circular Linked List– Applications of Lists : l
Manipulation on Polynomia –Stack ADT –Implementation of Stack – Applications of Stack – Balancing
Symbols - Conversion of Infix to postfix expression – Expression Evaluation - Queue ADT - Circular
Queue – Double Ended Queue – Applications of queues.
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.
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 on Data Structures:
1.Traversal
2.Search
3.Insertion
4.Deletion
23CS1302 1 DATA STRUCTURES
, PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
CLASSIFICATION OF DATA STRUCTURES
DATA STRUCTURES
PRIMARY DATA STRUCTURES SECONDARY DATA STRUCTURES
INT, CHAR, FLOAT DOUBLE LINEAR DATA NON LINEAR
STRUCTURES DATA
STRUCTURES
TREES GRAPHS
LISTS ARRAYS STACKS QUEUE
Primary Data Strucutres/Primitive Data Structures:
Primitive data structures include all the fundamental data structures that can be directly manipulated by
machine-level instructions. Some of the common primitive data structures include integer, character, real,
boolean etc
Secondary Data Structures/Non-Primitive Data Structures:
Non-primitive data structures refer to all those data structures that are derived from one or more primitive
data structures. The objective of creating non-primitive data structures is to form sets of homogeneous or
heterogeneous data elements.
Linear Data Structures:
Linear data structures are data strucutres in which, all the data elements are arranged in i, linear or
sequential fashion. Examples of data structures include arrays, stacks, queues, linked lists, etc.
Non-Linear Structures:
In non-linear data strucutres, there is definite order or sequence in which data elements are arranged. For
instance, a non-linear data structures could arrange data elements in a hierarchical fashion. Examples of
non-linear data structures are trees and graphs.
23CS1302 2 DATA STRUCTURES
,PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Static and dynamic data structure:
Static Ds:
If a ds is created using static memory allocation, ie. ds formed when the number of data items are known
in advance ,it is known as static data static ds or fixed size ds
Dynamic Ds:
If the ds is created using dynamic memory allocation i.e ds formed when the number of data items are not
known in advance is known as dynamic ds or variable size ds.
Application of data structures:
Data structures are widely applied in the following areas:
Compiler design
Operating system
Statistical analysis package
DBMS
Numerical analysis
Simulation
Artificial intelligence
Graphics
ABSTRACT DATA TYPES (ADTS):
An abstract Data type (ADT) is defined as a mathematical model with a collection of operations defined
on that model. Set of integers, together with the operations of union, intersection and set difference form
a example of an ADT. An ADT consists of data together with functions that operate on that data.
Advantages/Benefits of ADT:
1.Modularity
2.Reuse
3.code is easier to understand
4.Implementation of ADTs can be changed without requiring changes to the program that uses the ADTs.
THE LIST AI)T:
List is an ordered set of elements.
The general form of the list is A1 ,A2 , ……,AN
A1 - First element of the list
st
A2- 1 element of the list
N –Size of the list
If the element at position i is Ai, then its successor is Ai+1 and its predecessor is Ai-1
23CS1302 3 DATA STRUCTURES
, PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Various operations performed on List
1. Insert (X, 5)- Insert the element X after the position 5.
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
Differences between Array based and Linked based implementation
Array Linked List
Definition Array is a collection of elements Linked list is an ordered collection
having same data type with common of elements which are connected by
name links/pointers
Access Elements can be accessed using Sequential access
index/subscript, random access
Memory structure Elements are stored in contiguous Elements are stored at available
memory locations memory space
Insertion & Deletion Insertion and deletion takes more time Insertion and deletion are fast and
in array easy
Memory Allocation Memory is allocated at compile time Memory is allocated at run time i.e
i.e static memory allocation dynamic memory allocation
Types 1D,2D,multi-dimensional SLL, DLL circular linked list
Dependency Each elements is independent Each node is dependent on each
other as address part contains
address of next node in the list
23CS1302 4 DATA STRUCTURES
UNIT I - LINEAR DATA STRUCTURES – LIST, STACK AND QUEUE
List ADT– Singly Linked Lists – Doubly Linked Lists-Circular Linked List– Applications of Lists : l
Manipulation on Polynomia –Stack ADT –Implementation of Stack – Applications of Stack – Balancing
Symbols - Conversion of Infix to postfix expression – Expression Evaluation - Queue ADT - Circular
Queue – Double Ended Queue – Applications of queues.
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.
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 on Data Structures:
1.Traversal
2.Search
3.Insertion
4.Deletion
23CS1302 1 DATA STRUCTURES
, PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
CLASSIFICATION OF DATA STRUCTURES
DATA STRUCTURES
PRIMARY DATA STRUCTURES SECONDARY DATA STRUCTURES
INT, CHAR, FLOAT DOUBLE LINEAR DATA NON LINEAR
STRUCTURES DATA
STRUCTURES
TREES GRAPHS
LISTS ARRAYS STACKS QUEUE
Primary Data Strucutres/Primitive Data Structures:
Primitive data structures include all the fundamental data structures that can be directly manipulated by
machine-level instructions. Some of the common primitive data structures include integer, character, real,
boolean etc
Secondary Data Structures/Non-Primitive Data Structures:
Non-primitive data structures refer to all those data structures that are derived from one or more primitive
data structures. The objective of creating non-primitive data structures is to form sets of homogeneous or
heterogeneous data elements.
Linear Data Structures:
Linear data structures are data strucutres in which, all the data elements are arranged in i, linear or
sequential fashion. Examples of data structures include arrays, stacks, queues, linked lists, etc.
Non-Linear Structures:
In non-linear data strucutres, there is definite order or sequence in which data elements are arranged. For
instance, a non-linear data structures could arrange data elements in a hierarchical fashion. Examples of
non-linear data structures are trees and graphs.
23CS1302 2 DATA STRUCTURES
,PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Static and dynamic data structure:
Static Ds:
If a ds is created using static memory allocation, ie. ds formed when the number of data items are known
in advance ,it is known as static data static ds or fixed size ds
Dynamic Ds:
If the ds is created using dynamic memory allocation i.e ds formed when the number of data items are not
known in advance is known as dynamic ds or variable size ds.
Application of data structures:
Data structures are widely applied in the following areas:
Compiler design
Operating system
Statistical analysis package
DBMS
Numerical analysis
Simulation
Artificial intelligence
Graphics
ABSTRACT DATA TYPES (ADTS):
An abstract Data type (ADT) is defined as a mathematical model with a collection of operations defined
on that model. Set of integers, together with the operations of union, intersection and set difference form
a example of an ADT. An ADT consists of data together with functions that operate on that data.
Advantages/Benefits of ADT:
1.Modularity
2.Reuse
3.code is easier to understand
4.Implementation of ADTs can be changed without requiring changes to the program that uses the ADTs.
THE LIST AI)T:
List is an ordered set of elements.
The general form of the list is A1 ,A2 , ……,AN
A1 - First element of the list
st
A2- 1 element of the list
N –Size of the list
If the element at position i is Ai, then its successor is Ai+1 and its predecessor is Ai-1
23CS1302 3 DATA STRUCTURES
, PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Various operations performed on List
1. Insert (X, 5)- Insert the element X after the position 5.
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
Differences between Array based and Linked based implementation
Array Linked List
Definition Array is a collection of elements Linked list is an ordered collection
having same data type with common of elements which are connected by
name links/pointers
Access Elements can be accessed using Sequential access
index/subscript, random access
Memory structure Elements are stored in contiguous Elements are stored at available
memory locations memory space
Insertion & Deletion Insertion and deletion takes more time Insertion and deletion are fast and
in array easy
Memory Allocation Memory is allocated at compile time Memory is allocated at run time i.e
i.e static memory allocation dynamic memory allocation
Types 1D,2D,multi-dimensional SLL, DLL circular linked list
Dependency Each elements is independent Each node is dependent on each
other as address part contains
address of next node in the list
23CS1302 4 DATA STRUCTURES
