Introduction to Data Structures .

1. Introduction to data structures and their types.
2. Linear, non-linear, homogeneous, non-homogeneous, static and
dynamic data structures.
3. Linear data structures - array, stack, queue and linked list.
4. Non-linear data structures - tree and graph.

1. Introduction to Data Structures
Dr. Ashutosh Satapathy
Assistant Professor, Department of CSE
VR Siddhartha Engineering College
Kanuru, Vijayawada
March 12, 2024
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

2. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

3. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

4. Introduction
Computers can manipulate onlyprimitive data, i.e., data in terms of
of0’s and 1’s.
Manipulation of primitive datais inherent within the computer and
need not require any extra effortfrom the user’s side.
Various kinds of data, other than primitive data, are involved in
real-life applications.
Manipulation of real-life data, which can also be termeduser-defined
datarequires the following essential tasks:
1
Storage representation of user data:User data should be stored in
such a way that a computer can understand it.
2
Retrieval of stored data:Data stored on a computer should be
retrieved in such a way that the user can understand it.
3
Transformation of user data:Various operations that require
performed on user data so that it can be transformed from one form to
other.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

5. Introduction
Knowledge of data structuresis required for people whodesign
and develop computer programsof any kind: system software or
application software.
Data are represented by values heldtemporarily within programs
and data areasorrecorded permanently on a file.
Often, the different data values are related to each other. To enable
programs to make use of these relationships, these data values must
be in an organized form.
Theorganized collection of datais called adata structure. The
programs have to follow certain rules to access and process the
structured data.
Data Structures = Organized Data + Allowed Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

6. Introduction
Data may be organized in many different ways: thelogical or
mathematical modelof a particular organization of data is called a
data structure.
The choice of a particular data model depends on two considerations.
First, it must be rich enough in structure tomirror the actual
relationship of the datain the real world.
On the other hand, the structure should besimple enoughthat one
caneffectively process the datawhen necessary.
Data structures may be classified asArrays, lists, and files. These
are derived from theprimitive data types(int, char, float, double).
These data structures emphasize the structuring of a group of
homogeneous(same type) orheterogeneous(different type) data
items.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

7. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

8. Data Structure Types
Figure 1.1:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

9. Classification
Table 1.1:
Linear Non-Linear
In linear data structures, the data items
are arranged in alinear sequencelike in
an array.Example:Array, Stack, Queue
and linked list
In non-linear data structures, the data
items arenot in sequence.
Example:Tree, Graph and Trie
Homogeneous Non-Homogeneous
In a homogeneous data structure, all the
elements arethe same type.
Example:Array
In a non-homogeneous data structure
the elements may or maynot be the
same type.Example:Records
Static Dynamic
Static structures are ones whose sizes and
structures are associated with memory
locationsfixed at compile time.
Example:Array
Dynamic structuresexpand or shrink
as requiredduring program execution.
Example:Linked List
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

10. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

11. Array
An array is defined as aset of finite number of homogeneous
elementsor data items.
It means an array can contain one type of data only, either all
integers, all floating-point numbers, or all characters.
Declaration of arrays is as follows: int a[10], whereint specifies the
data typeortype of elements array stores.
a is the name of the array and the number specified inside the square
brackets is the number of elements an array can store; this is also
called size or length of the array.
The individual element of an array can be accessed by specifying the
array’s name, followed byindex or subscript(an integer number
specifying the location of a clement in the array) inside square
brackets.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

12. Array
For example, to access thefifth element of array a, we have to give
the following statement:a[4];
The first element of the array has anindex of zero (0). It means the
firstandlast elementswill be specified asa[0] and a[9],
respectively.
The element of the array will always be stored inconsecutive
memory locations.
The number of elements that can be stored in an array, i.e., the size
of an array or itslength, is given by the following equation:(upper
bound - lower bound) + 1
For the above array, it would be(9 - 0) + 1 = 10, where0 is the
lower boundand9 is the upper bound.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

13. Array
Arrays can always be read or written through the loop.
Reading aone-dimensional array requires one loopfor reading and
another for writing (printing) the array.
Reading atwo-dimensional array requires two loopsfor reading
and two loops for writing (printing) the array.
Similarly, the array ofn dimensions would require n loops.
Some common operations performed on arrays are:
1
Creation of an array.
2
Traversing an array (accessing array elements).
3
Insertion of new elements.
4
Deletion of the required element.
5
Modification of an element.
6
Merging of arrays.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

14. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

15. Linked List
Alist (linear linked list)can be defined asa collection of a
variable number of data items. Linked lists are the most commonly
used data structures.
An element of a list must containat least two fields, one for storing
data or informationand the other for storing theaddress of the
next node.
For storing addresses, we have derived data types in C called pointers.
Hence, thesecond fieldof the list must bea pointer type.
Technically, each such element is referred to asa node. Therefore,a
listcan be defined asa collection of nodes.
Figure 2.1:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

16. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

17. Stack
Astackis also anordered collection of elements like arrays, but
it has a special feature that deletion and insertion of elements can be
done only from one end, called thetop of the stack (TOP).
Due to this property, it is also called alast in, first outtype of data
structure(LIFO).
It could be like a stack of plates placed on the table. A guest always
removes a fresh plate from the top, and the new plates are placed
onto the stack at the top.
Figure 2.2:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

18. Stack
Figure 2.3:
When an element is inserted into or removed from a stack, itsbase
remains fixed, whereas thetop of the stack changes.
Inserting an elementinto the stack is calledPush, anddeletion of
an elementfrom the stack is calledPop.
Stacks can be implemented in two ways:
1
Using arrays (static implementation)
2
Using linked list (dynamic implementation)
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

19. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

20. Queue
Queuesarefirst in, first outtype of data structure (i.e.,FIFO).
In a queue,new elements are addedto the queue from one end,
called therear end, and the elements are alwaysremoved from the
other end, called thefront end.
The people standing in a railway reservation row are an example of a
queue. Each new person comes and stands at the end of the row (the
rear endof the queue), and people get their reservations confirmed.
Get out from thefront end.
Queues can also be implemented in two ways:
1
Using arrays (static implementation)
2
Using linked list (dynamic implementation)
Figure 2.4:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

21. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

22. Tree
Atreecan be defined asfinite set of data items (nodes).
Tree isa non-linear type of data structurein which data items are
arranged or stored in a sorted sequence.
Trees represent thehierarchical relationshipbetween various
elements.
Here is a special data item at thetop of the hierarchycalled the
rootof the tree.
The remaining data items are partitioned intoseveral mutually
exclusive (i.e., disjoint) subsets, each of which is itself a tree,
which is called thesub-tree.
The tree alwaysgrows in length toward the bottomof the data
structures, unlike natural trees, which grow upwards.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

23. Tree
The tree structureorganizes the data into branches, as shown in
the next figure. This type of structure is very useful in general.
Figure 2.5:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

24. Outline
1
Data Structures
Introduction
Classification
2
Types of Data Structures
Array
Linked List
Stack
Queue
Tree
Graph
3
Data Structure Operations
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

25. Graph
A graph is amathematical non-linear data structurecapable of
structures.
It represents many physicalapplications in geography, chemistry,
and engineering sciences.
A graphG(V,E) is aset of verticesvandedgese.
Anedge connects a pair of verticesthat may haveweight, such as
length,cost, or another measuring instrument for recording a graph.
Vertices on the graph are shown aspointsorcirclesandedges as
arcs or line segments.
Thus, anedgecan be represented ase= (v,w), wherevandware
pairs of vertices. The verticesvandwlie one.
Verticesmay be consideredcities, andedges, arcs, and line
segmentsmay be consideredroadsin aroad network.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

26. Graph
(a)(b)(c)(d)(e) (f)
Figure 2.6:
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

27. Data Structure Operations
A large number of operations can be performed on data structures. Some
of the important operations are listed below.
1
Creating:A data structure is created.
2
Inserting:New items are added to the data structure.
3
Modifying:The values of a data structure are modified by replacing
old values.
4
Traversing:Each item in the data structure is visited for processing
purposes.
5
Searching:A data item is searched in the structure; the item may or
may not exist in the data structure.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

28. Data Structure Operations
6
Deleting:Deleting is a process of removing an item from the data
structure.
7
Sorting:Data items are sorted in ascending or descending order.
8
Merging:Data items in more than one sorted data structure are
merged together to produce a single sorted new data structure.
9
Copying:Data items from one structure are copied to another
structure.
10
Concatenating:Data items of a structure are appended at the end
of another type of structure.
11
Splitting:Data items in a very big structure are split into smaller
structures for processing.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

29. Summary
Here, we have discussed
Introduction to data structures and their types.
Linear, non-linear, homogeneous, non-homogeneous, static and
dynamic data structures.
Linear data structures - array, stack, queue and linked list.
Non-linear data structures - tree and graph.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024

30. For Further Reading
E. Horowitz, S. Sahni and S. A. Freed.
Fundamentals of Data Structures in C (2
nd
edition).
Universities Press, 2008.
A. K. Rath and A. K. Jagadev.
Data Structures Using C (2
nd
edition).
Scitech Publications, 2011.
M. A. Weiss
Data Structures and Algorithm Analysis in C (2
nd
edition).
Pearson India, 2022.
Dr. Ashutosh Satapathy Introduction to Data Structures March 12, 2024