DATA STRUCTURES

BASIC TERMINOLOGY
• We know how to write, debug, and run simple programs in C language.
• Our aim has been to design good programs, where a good program is defined as a
program that
– runs correctly
– is easy to read and understand
– is easy to debug
– is easy to modify
• A program should give correct results, but along with that it should also run
efficiently.
• A program is said to be efficient when it executes in minimum time and with
minimum memory space.
• In order to write efficient programs we need to apply certain data management
concepts.
• Data structure is a crucial part of data management.
• A data structure is basically a group of data elements that are put together under one
name, and which defines a particular way of storing and organizing data in a
computer so that it can be used efficiently.
What is Data Structure?

• A data structure is a particular way of storing and organizing data in a computer so

that it can be used efficiently.
• They provide a means to manage large amounts of data efficiently, such as large
databases.
• Data are simply values or set of values and Database is organized collection of data.
• A data structure is a logical and mathematical model of a particular organization of
data.
• Data structures are used in almost every program or software system.
• Some common examples of data structures are arrays, linked lists, queues, stacks,
binary trees, and hash tables.
• Representing information is fundamental to computer science.
• The primary goal of a program or software is not to perform calculations or
operations but to store and retrieve information as fast as possible.
• The application of an appropriate data structure provides the most efficient solution.
• A solution is said to be efficient if it solves the problem within the required resource
constraints like the total space available to store the data and the time allowed to
perform each subtask.
• And the best solution is the one that requires fewer resources than known
alternatives.
• Moreover, the cost of a solution is the amount of resources it consumes.
• The cost of a solution is basically measured in terms of one key resource such as
time, with the implied assumption that the solution meets the other resource
constraints.
• Today computer programmers do not write programs just to solve a problem but to
write an efficient program.
• For this, they first analyze the problem to determine the performance goals that must
be achieved and then think of the most appropriate data structure for that job.
• However, program designers with a poor understanding of data structure concepts
ignore this analysis step and apply a data structure with which they can work
comfortably.
• The applied data structure may not be appropriate for the problem at hand and
therefore may result in poor performance (like slow speed of operations).
The choice of particular data structure depends upon following consideration:

1.It must be able to represent the inherent relationship of data in the real world.

2.It must be simple enough so that it can be processed efficiently as and when
necessary.

THE STUDY OF DATA STRUCTURE INCLUDE:

• Logical description of data structure
• Implementation of data structure
• Quantitative analysis of data structure, this include amount of memory, processing
time
Elementary Data Structure Organization
• Data structures are building blocks of a program.
• A program built using improper data structures may not work as expected.
• So as a programmer it is mandatory to choose most appropriate data structures for a
program.
• The term data means a value or set of values.
• It specifies either the value of a variable or a constant (e.g., marks of students, name
of an employee, address of a customer, value of pi, etc.).
• While a data item that does not have subordinate data items is categorized as an
elementary item, the one that is composed of one or more subordinate data items is
called a group item.
• For example, a student’s name may be divided into three sub-items—first name,
middle name, and last name—but his roll number would normally be treated as a
single item.
• A record is a collection of data items.
• For example, the name, address, course, and marks obtained are individual data
items.
• But all these data items can be grouped together to form a record.
• A file is a collection of related records.
• For example, if there are 60 students in a class, then there are 60 records of the
students.
• All these related records are stored in a file.
• Similarly, we can have a file of all the employees working in an organization, a file
of all the customers of a company, a file of all the suppliers, so on and so forth.
Data structures are generally categorized into two classes: primitive and non-primitive
data structures.
Primitive and Non-primitive Data Structures
• Primitive data structures are the fundamental data types which are supported by a
programming language.
• Some basic data types are integer, real, character, and boolean.
• The terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are often used
interchangeably.
• Non-primitive data structures are those data structures which are created using
primitive data structures.
• Examples of such data structures include linked lists, stacks, trees, and graphs.
• Non-primitive data structures can further be classified into two categories: linear and
non-linear data structures.
Linear and Non-linear Structures
• If the elements of a data structure are stored in a linear or sequential order, then it is a
linear data structure.
• Examples include arrays, linked lists, stacks, and queues.
• Linear data structures can be represented in memory in two different ways.
• One way is to have to a linear relationship between elements by means of sequential
memory locations.
• The other way is to have a linear relationship between elements by means of links.
• However, if the elements of a data structure are not stored in a sequential order, then
it is a non-linear data structure.
• The relationship of adjacency is not maintained between elements of a non-linear
data structure. Examples include trees and graphs.
• C supports a variety of data structures
Arrays
• An array is a collection of similar data elements. These data elements have the same
data type.
• The elements of the array are stored in consecutive memory locations and are
referenced by an index (also known as the subscript).
• In C, arrays are declared using the following syntax:
type name[size];
For example,
int marks[10];
• The above statement declares an array marks that contains 10 elements. In C, the
array index starts from zero.
• This means that the array marks will contain 10 elements in all.
• The first element will be stored in marks[0], second element in marks[1], so on and
so forth.
• Therefore, the last element, that is the 10th element, will be stored in marks[9].
• In the memory, the array will be stored as shown
Arrays are generally used when we want to store large amount of similar type of data.
But they have the following limitations:
• Arrays are of fixed size.
• Data elements are stored in contiguous memory locations which may not be always
available.
• Insertion and deletion of elements can be problematic because of shifting of elements
from their positions.
Linked Lists
• A linked list is a very flexible, dynamic data structure in which elements (called
nodes) form a sequential list.
• In contrast to static arrays, a programmer need not worry about how many elements
will be stored in the linked list.
• This feature enables the programmers to write robust programs which require less
maintenance.
• In a linked list, each node is allocated space as it is added to the list.
• Every node in the list points to the next node in the list.
• Therefore, in a linked list, every node contains the following two types of data:
1. The value of the node or any other data that corresponds to that node
2. A pointer or link to the next node in the list
• The last node in the list contains a NULL pointer to indicate that it is the end or tail
of the list.
• Since the memory for a node is dynamically allocated when it is added to the list, the
total number of nodes that may be added to a list is limited only by the amount of
memory available.
Stacks
• A stack is a linear data structure in which insertion and deletion of elements are done
at only one end, which is known as the top of the stack.
• Stack is called a last-in, first-out (LIFO) structure because the last element which is
added to the stack is the first element which is deleted from the stack.
• Every stack has a variable top associated with it.
• top is used to store the address of the topmost element of the stack.
• It is this position from where the element will be added or deleted.
• There is another variable MAX, which is used to store the
• maximum number of elements that the stack can store.
• If top = NULL, then it indicates that the stack is empty and if top = MAX–1, then the
stack is full.
• A stack supports three basic operations: push, pop, and peep.
• The push operation adds an element to the top of the stack.
• The pop operation removes the element from the top of the stack.
• And the peep operation returns the value of the topmost element of the stack (without
deleting it).
• However, before inserting an element in the stack, we must check for overflow
conditions.
• An overflow occurs when we try to insert an element into a stack that is already full.
• Similarly, before deleting an element from the stack, we must check for underflow
conditions.
• An underflow condition occurs when we try to delete an element from a stack that is
already empty.
Queues
• A queue is a first-in, first-out (FIFO) data structure in which the element that is
inserted first is the first one to be taken out.
• The elements in a queue are added at one end called the rear and removed from the
other end called the front.
• Like stacks, queues can be implemented by using either arrays or linked lists.
• Every queue has front and rear variables that point to the position from where
deletions and insertions can be done, respectively.
• Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic
operations associated with queues −
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
• peek() − Gets the element at the front of the queue without removing it.
In queue, we always dequeue (or access) data, pointed by front pointer and while
enqueing (or storing) data in the queue we take help of rear pointer.
Enqueue Operation
• Queues maintain two data pointers, front and rear. Therefore, its operations are
comparatively difficult to implement than that of stacks.
• The following steps should be taken to enqueue (insert) data into a queue −
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success.
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to perform
dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Trees
• A tree is a non-linear data structure which consists of a collection of nodes arranged
in a hierarchical order.
• One of the nodes is designated as the root node, and the remaining nodes can be
partitioned into disjoint sets such that each set is a sub-tree of the root.
• The simplest form of a tree is a binary tree.
• A binary tree consists of a root node and left and right sub-trees, where both sub-trees
are also binary trees.
• Each node contains a data element, a left pointer which points to the left sub-tree, and
a right pointer which points to the right sub-tree.
• The root element is the topmost node which is pointed by a ‘root’ pointer.
• If root = NULL then the tree is empty.
• Path − Path refers to the sequence of nodes along the edges of a tree.
• Root − The node at the top of the tree is called root. There is only one root per tree
and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to a node called parent.
• Child − The node below a given node connected by its edge downward is called its
child node.
• Leaf − The node which does not have any child node is called the leaf node.
• Subtree − Subtree represents the descendants of a node.
• Visiting − Visiting refers to checking the value of a node when control is on the node.
• Traversing − Traversing means passing through nodes in a specific order.
• Levels − Level of a node represents the generation of a node. If the root node is at
level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
• keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.
Graphs
• A graph is a non-linear data structure which is a collection of vertices (also called
nodes) and edges that connect these vertices.
• A graph is often viewed as a generalization of the tree structure, where instead of a
purely parent-to-child relationship between tree nodes, any kind of complex
relationships between the nodes can exist.
• In a tree structure, nodes can have any number of children but only one parent, a
graph on the other hand relaxes all such kinds of restrictions.
• Vertex − Each node of the graph is represented as a
vertex. In the following example, the labeled circle
represents vertices. Thus, A to G are vertices.
• Edge − Edge represents a path between two vertices or a
line between two vertices. In the following example, the
lines from A to B, B to C, and so on represents edges.
• Adjacency − Two node or vertices are adjacent if they
are connected to each other through an edge. In the
following example, B is adjacent to A, C is adjacent to
B, and so on.
• Path − Path represents a sequence of edges between the
two vertices. In the following example, ABCD
represents a path from A to D.
OPERATIONS ON DATA STRUCTURES
• Traversing It means to access each data item exactly once so that it can be
processed. For example, to print the names of all the students in a class.
• Searching It is used to find the location of one or more data items that satisfy the
given constraint. Such a data item may or may not be present in the given collection
of data items. For example, to find the names of all the students who secured 100
marks in mathematics.
• Inserting It is used to add new data items to the given list of data items. For
example, to add the details of a new student who has recently joined the course.
• Deleting It means to remove (delete) a particular data item from the given collection
of data items. For example, to delete the name of a student who has left the course.
• Merging Lists of two sorted data items can be combined to form a single list of
sorted data items.
• Sorting Data items can be arranged in some order like ascending order or descending
order depending on the type of application. For example, arranging the names of
students in a class in an alphabetical order, or calculating the top three winners by
arranging the participants’ scores in descending order and then extracting the top
three.
ABSTRACT DATA TYPE
• An abstract data type (ADT) is the way we look at a data structure, focusing on what
it does and ignoring how it does its job.
• Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined
by a set of value and a set of operations.
• The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented.
• It does not specify how data will be organized in memory and what algorithms will
be used for implementing the operations.
• 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.
• For example, when we use a stack or a queue, the user is concerned only with the
type of data and the operations that can be performed on it.
• Therefore, the fundamentals of how the data is stored should be invisible to the user.
• They should not be concerned with how the methods work or what structures are
being used to store the data.
• They should just know that to work with stacks, they have push() and pop() functions
available to them.
• Using these functions, they can manipulate the data (insertion or deletion) stored in
the stack.
Advantage of using ADTs
• In the real world, programs evolve as a result of new requirements or constraints, so a
modification to a program commonly requires a change in one or more of its data
structures.
• For example, if you want to add a new field to a student’s record to keep track of
more information about each student, then it will be better to replace an array with a
linked structure to improve the program’s efficiency.
• In such a scenario, rewriting every procedure that uses the changed structure is not
desirable.
• Therefore, a better alternative is to separate the use of a data structure from the
details of its implementation.
• This is the principle underlying the use of abstract data types.