DS - Unit 1

An Introduction to Data Structures
Data is a collection of facts and figures or a set of values or values of a specific format that refers to a single set of
item values. The data items are then classified into sub-items, which is the group of items that are not known as the
simple primary form of the item.
What is Data Structure?
Data Structure is a branch of Computer Science. The study of data structure allows us to understand the
organization of data and the management of the data flow in order to increase the efficiency of any process or
program. Data Structure is a particular way of storing and organizing data in the memory of the computer so that
these data can easily be retrieved and efficiently utilized in the future when required. The data can be managed in
various ways, like the logical or mathematical model for a specific organization of data is known as a data
structure.
The scope of a particular data model depends on two factors:
1. First, it must be loaded enough into the structure to reflect the definite correlation of the data with a real-
world object.
2. Second, the formation should be so straightforward that one can adapt to process the data efficiently
whenever necessary. Some examples of Data Structures are Arrays, Linked Lists, Stack, Queue, Trees, etc.
Understanding the Need for Data Structures
As applications are becoming more complex and the amount of data is increasing every day, which may lead to
problems with data searching, processing speed, multiple requests handling, and many more. Data Structures
support different methods to organize, manage, and store data efficiently. With the help of Data Structures, we can
easily traverse the data items. Data Structures provide Efficiency, Reusability, and Abstraction.
Why should we learn Data Structures?

1. Data Structures and Algorithms are two of the key aspects of Computer Science.
2. Data Structures allow us to organize and store data, whereas Algorithms allow us to process that data
meaningfully.
3. Learning Data Structures and Algorithms will help us become better Programmers.
4. We will be able to write code that is more effective and reliable.
5. We will also be able to solve problems more quickly and efficiently.
Basic Terminologies related to Data Structures
Data Structures are the building blocks of any software or program. Selecting the suitable data structure for a
program is an extremely challenging task for a programmer.
The following are some fundamental terminologies used whenever the data structures are involved:
1. Data: We can define data as an elementary value or a collection of values. For example, the Employee's
name and ID are the data related to the Employee.
2. Data Items: A Single unit of value is known as Data Item.
3. Group Items: Data Items that have subordinate data items are known as Group Items. For example, an
employee's name can have a first, middle, and last name.
4. Elementary Items: Data Items that are unable to divide into sub-items are known as Elementary Items.
For example, the ID of an Employee.
5. Entity and Attribute: A class of certain objects is represented by an Entity. It consists of different
Attributes. Each Attribute symbolizes the specific property of that Entity. For example,
Attributes ID Name Gender Job Title
Values 1234 Stacey M. Hill Female Software Developer
Entities with similar attributes form an Entity Set. Each attribute of an entity set has a range of values, the set of
all possible values that could be assigned to the specific attribute.
The term "information" is sometimes utilized for data with given attributes of meaningful or processed data.
1. Field: A single elementary unit of information symbolizing the Attribute of an Entity is known as Field.
2. Record: A collection of different data items are known as a Record. For example, if we talk about the
employee entity, then its name, id, address, and job title can be grouped to form the record for the
employee.
3. File: A collection of different Records of one entity type is known as a File. For example, if there are 100
employees, there will be 25 records in the related file containing data about each employee.
Classification of Data Structures
A Data Structure delivers a structured set of variables related to each other in various ways. It forms the basis of a
programming tool that signifies the relationship between the data elements and allows programmers to process the
data efficiently.
We can classify Data Structures into two categories:
1. Primitive Data Structure

2. Non-Primitive Data Structure
The following figure shows the different classifications of Data Structures.

Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't be divided further
Non-Primitive Data Structures

1. Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by machine-level instructions.
3. The focus of these data structures is on forming a set of data elements that is either homogeneous (same
data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data structures into two sub-categories
-
a. Linear Data Structures
b. Non-Linear Data Structures
Linear Data Structures
A data structure that preserves a linear connection among its data elements is known as a Linear Data Structure.
The arrangement of the data is done linearly, where each element consists of the successors and predecessors
except the first and the last data element. However, it is not necessarily true in the case of memory, as the
arrangement may not be sequential.
Based on memory allocation, the Linear Data Structures are further classified into two types:
1. Static Data Structures: The data structures having a fixed size are known as Static Data Structures. The
memory for these data structures is allocated at the compiler time, and their size cannot be changed by the
user after being compiled; however, the data stored in them can be altered.
The Array is the best example of the Static Data Structure as they have a fixed size, and its data can be
modified later.
2. Dynamic Data Structures: The data structures having a dynamic size are known as Dynamic Data
Structures. The memory of these data structures is allocated at the run time, and their size varies during the
run time of the code. Moreover, the user can change the size as well as the data elements stored in these
data structures at the run time of the code.
Linked Lists, Stacks, and Queues are common examples of dynamic data structures
Types of Linear Data Structures
The following is the list of Linear Data Structures that we generally use:
1. Arrays
An Array is a data structure used to collect multiple data elements of the same data type into one variable. Instead
of storing multiple values of the same data types in separate variable names, we could store all of them together
into one variable. This statement doesn't imply that we will have to unite all the values of the same data type in any
program into one array of that data type. But there will often be times when some specific variables of the same
data types are all related to one another in a way appropriate for an array.
An Array is a list of elements where each element has a unique place in the list. The data elements of the array
share the same variable name; however, each carries a different index number called a subscript. We can access
any data element from the list with the help of its location in the list. Thus, the key feature of the arrays to
understand is that the data is stored in contiguous memory locations, making it possible for the users to traverse
through the data elements of the array using their respective indexes.
Figure 3. An Array
Arrays can be classified into different types:
a. One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
b. Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
c. Multidimensional Array: We can define Multidimensional Array as an Array of Arrays.
Multidimensional Arrays are not bounded to two indices or two dimensions as they can include as many
indices are per the need.
Some Applications of Array:
a. We can store a list of data elements belonging to the same data type.
b. Array acts as an auxiliary storage for other data structures.
c. The array also helps store data elements of a binary tree of the fixed count.
d. Array also acts as a storage of matrices.
2. Linked Lists
A Linked List is another example of a linear data structure used to store a collection of data elements
dynamically. Data elements in this data structure are represented by the Nodes, connected using links or pointers.
Each node contains two fields, the information field consists of the actual data, and the pointer field consists of the
address of the subsequent nodes in the list. The pointer of the last node of the linked list consists of a null pointer,
as it points to nothing. Unlike the Arrays, the user can dynamically adjust the size of a Linked List as per the
requirements.
Figure 4. A Linked List
Linked Lists can be classified into different types:
a. Singly Linked List: A Singly Linked List is the most common type of Linked List. Each node has data and
a pointer field containing an address to the next node.
b. Doubly Linked List: A Doubly Linked List consists of an information field and two pointer fields. The
information field contains the data. The first pointer field contains an address of the previous node, whereas
another pointer field contains a reference to the next node. Thus, we can go in both directions (backward as
well as forward).
c. Circular Linked List: The Circular Linked List is similar to the Singly Linked List. The only key
difference is that the last node contains the address of the first node, forming a circular loop in the Circular
Linked List.
Some Applications of Linked Lists:
a. The Linked Lists help us implement stacks, queues, binary trees, and graphs of predefined size.
b. We can also implement Operating System's function for dynamic memory management.
c. Linked Lists also allow polynomial implementation for mathematical operations.
d. We can use Circular Linked List to implement Operating Systems or application functions that Round
Robin execution of tasks.
e. Circular Linked List is also helpful in a Slide Show where a user requires to go back to the first slide after
the last slide is presented.
f. Doubly Linked List is utilized to implement forward and backward buttons in a browser to move forward
and backward in the opened pages of a website.
3. Stacks
A Stack is a Linear Data Structure that follows the LIFO (Last In, First Out) principle that allows operations like
insertion and deletion from one end of the Stack, i.e., Top. Stacks can be implemented with the help of contiguous
memory, an Array, and non-contiguous memory, a Linked List. Real-life examples of Stacks are piles of books, a
deck of cards, piles of money, and many more.
The primary operations in the Stack are as follows:
a. Push: Operation to insert a new element in the Stack is termed as Push Operation.
b. Pop: Operation to remove or delete elements from the Stack is termed as Pop Operation.
Figure 6. A Stack
Some Applications of Stacks:
a. The Stack is used as a Temporary Storage Structure for recursive operations.

b. Stack is also utilized as Auxiliary Storage Structure for function calls, nested operations, and
deferred/postponed functions.
c. We can manage function calls using Stacks.
d. Stacks are also utilized to evaluate the arithmetic expressions in different programming languages.
e. Stacks are also helpful in converting infix expressions to postfix expressions.
f. Stacks allow us to check the expression's syntax in the programming environment.
g. We can match parenthesis using Stacks.
h. Stacks can be used to reverse a String.
i. Stacks are helpful in solving problems based on backtracking.
j. We can use Stacks in depth-first search in graph and tree traversal.
k. Stacks are also used in Operating System functions.
l. Stacks are also used in UNDO and REDO functions in an edit.
4. Queues
A Queue is a linear data structure similar to a Stack with some limitations on the insertion and deletion of the
elements. The insertion of an element in a Queue is done at one end, and the removal is done at another or opposite
end. Thus, we can conclude that the Queue data structure follows FIFO (First In, First Out) principle to manipulate
the data elements. Implementation of Queues can be done using Arrays, Linked Lists, or Stacks. Some real-life
examples of Queues are a line at the ticket counter, an escalator, a car wash, and many more.
Figure 7. A Real-life Example of Queue
The above image is a real-life illustration of a movie ticket counter that can help us understand the Queue where
the customer who comes first is always served first. The customer arriving last will undoubtedly be served last.
Both ends of the Queue are open and can execute different operations. Another example is a food court line where
the customer is inserted from the rear end while the customer is removed at the front end after providing the
service they asked for.
The following are the primary operations of the Queue:
a. Enqueue: The insertion or Addition of some data elements to the Queue is called Enqueue. The element
insertion is always done with the help of the rear pointer.
b. Dequeue: Deleting or removing data elements from the Queue is termed Dequeue. The deletion of the
element is always done with the help of the front pointer.
Figure 8. A Queue
Some Applications of Queues:
a. Queues are generally used in the breadth search operation in Graphs.

b. Queues are also used in Job Scheduler Operations of Operating Systems, like a keyboard buffer queue to
store the keys pressed by users and a print buffer queue to store the documents printed by the printer.
c. Queues are responsible for CPU scheduling, Job scheduling, and Disk Scheduling.
d. Priority Queues are utilized in file-downloading operations in a browser.
e. Queues are also used to transfer data between peripheral devices and the CPU.
f. Queues are also responsible for handling interrupts generated by the User Applications for the CPU.
Non-Linear Data Structures
Non-Linear Data Structures are data structures where the data elements are not arranged in sequential order. Here,
the insertion and removal of data are not feasible in a linear manner. There exists a hierarchical relationship
between the individual data items.
Types of Non-Linear Data Structures
The following is the list of Non-Linear Data Structures that we generally use:
1. Trees
A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of nodes such that each node of the
tree stores a value and a list of references to other nodes (the "children").
The Tree data structure is a specialized method to arrange and collect data in the computer to be utilized more
effectively. It contains a central node, structural nodes, and sub-nodes connected via edges. We can also say that
the tree data structure consists of roots, branches, and leaves connected.
Figure 9. A Tree
Trees can be classified into different types:
a. Binary Tree: A Tree data structure where each parent node can have at most two children is termed a
Binary Tree.
b. Binary Search Tree: A Binary Search Tree is a Tree data structure where we can easily maintain a sorted
list of numbers.
c. AVL Tree: An AVL Tree is a self-balancing Binary Search Tree where each node maintains extra
information known as a Balance Factor whose value is either -1, 0, or +1.
d. B-Tree: A B-Tree is a special type of self-balancing Binary Search Tree where each node consists of
multiple keys and can have more than two children.
Some Applications of Trees:
a. Trees implement hierarchical structures in computer systems like directories and file systems.
b. Trees are also used to implement the navigation structure of a website.
c. We can generate code like Huffman's code using Trees.
d. Trees are also helpful in decision-making in Gaming applications.
e. Trees are responsible for implementing priority queues for priority-based OS scheduling functions.
f. Trees are also responsible for parsing expressions and statements in the compilers of different
programming languages.
g. We can use Trees to store data keys for indexing for Database Management System (DBMS).
h. Spanning Trees allows us to route decisions in Computer and Communications Networks.
i. Trees are also used in the path-finding algorithm implemented in Artificial Intelligence (AI), Robotics, and
Video Games Applications.
2. Graphs
A Graph is another example of a Non-Linear Data Structure comprising a finite number of nodes or vertices and
the edges connecting them. The Graphs are utilized to address problems of the real world in which it denotes the
problem area as a network such as social networks, circuit networks, and telephone networks. For instance, the
nodes or vertices of a Graph can represent a single user in a telephone network, while the edges represent the link
between them via telephone.
The Graph data structure, G is considered a mathematical structure comprised of a set of vertices, V and a set of
edges, E as shown below:
G = (V,E)
Figure 10. A Graph

The above figure represents a Graph having seven vertices A, B, C, D, E, F, G, and ten edges [A, B], [A, C], [B,
C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F], and [E, G].
Depending upon the position of the vertices and edges, the Graphs can be classified into different types:
a. Null Graph: A Graph with an empty set of edges is termed a Null Graph.
b. Trivial Graph: A Graph having only one vertex is termed a Trivial Graph.
c. Simple Graph: A Graph with neither self-loops nor multiple edges is known as a Simple Graph.
d. Multi Graph: A Graph is said to be Multi if it consists of multiple edges but no self-loops.
e. Pseudo Graph: A Graph with self-loops and multiple edges is termed a Pseudo Graph.
f. Non-Directed Graph: A Graph consisting of non-directed edges is known as a Non-Directed Graph.
g. Directed Graph: A Graph consisting of the directed edges between the vertices is known as a Directed
Graph.
h. Connected Graph: A Graph with at least a single path between every pair of vertices is termed a
Connected Graph.
i. Disconnected Graph: A Graph where there does not exist any path between at least one pair of vertices is
termed a Disconnected Graph.
j. Regular Graph: A Graph where all vertices have the same degree is termed a Regular Graph.
k. Complete Graph: A Graph in which all vertices have an edge between every pair of vertices is known as a
Complete Graph.
l. Cycle Graph: A Graph is said to be a Cycle if it has at least three vertices and edges that form a cycle.
m. Cyclic Graph: A Graph is said to be Cyclic if and only if at least one cycle exists.
n. Acyclic Graph: A Graph having zero cycles is termed an Acyclic Graph.
o. Finite Graph: A Graph with a finite number of vertices and edges is known as a Finite Graph.
p. Infinite Graph: A Graph with an infinite number of vertices and edges is known as an Infinite Graph.
q. Bipartite Graph: A Graph where the vertices can be divided into independent sets A and B, and all the
vertices of set A should only be connected to the vertices present in set B with some edges is termed a
Bipartite Graph.
r. Planar Graph: A Graph is said to be a Planar if we can draw it in a single plane with two edges
intersecting each other.
s. Euler Graph: A Graph is said to be Euler if and only if all the vertices are even degrees.
t. Hamiltonian Graph: A Connected Graph consisting of a Hamiltonian circuit is known as a Hamiltonian
Graph.
Some Applications of Graphs:
a. Graphs help us represent routes and networks in transportation, travel, and communication applications.
b. Graphs are used to display routes in GPS.
c. Graphs also help us represent the interconnections in social networks and other network-based applications.
d. Graphs are utilized in mapping applications.
e. Graphs are responsible for the representation of user preference in e-commerce applications.
f. Graphs are also used in Utility networks in order to identify the problems posed to local or municipal
corporations.
g. Graphs also help to manage the utilization and availability of resources in an organization.
h. Graphs are also used to make document link maps of the websites in order to display the connectivity
between the pages through hyperlinks.
i. Graphs are also used in robotic motions and neural networks.
Basic Operations of Data Structures
In the following section, we will discuss the different types of operations that we can perform to manipulate data in
every data structure:
1. Traversal: Traversing a data structure means accessing each data element exactly once so it can be
administered. For example, traversing is required while printing the names of all the employees in a
department.
2. Search: Search is another data structure operation which means to find the location of one or more data
elements that meet certain constraints. Such a data element may or may not be present in the given set of
data elements. For example, we can use the search operation to find the names of all the employees who
have the experience of more than 5 years.
3. Insertion: Insertion means inserting or adding new data elements to the collection. For example, we can
use the insertion operation to add the details of a new employee the company has recently hired.
4. Deletion: Deletion means to remove or delete a specific data element from the given list of data elements.
For example, we can use the deleting operation to delete the name of an employee who has left the job.
5. Sorting: Sorting means to arrange the data elements in either Ascending or Descending order depending
on the type of application. For example, we can use the sorting operation to arrange the names of
employees in a department in alphabetical order or estimate the top three performers of the month by
arranging the performance of the employees in descending order and extracting the details of the top three.
6. Merge: Merge means to combine data elements of two sorted lists in order to form a single list of sorted
data elements.
7. Create: Create is an operation used to reserve memory for the data elements of the program. We can
perform this operation using a declaration statement. The creation of data structure can take place either
during the following:
a. Compile-time
b. Run-time
For example, the malloc() function is used in C Language to create data structure.
Selection: Selection means selecting a particular data from the available data. We can select any particular data by
specifying conditions inside the loop.
Update: The Update operation allows us to update or modify the data in the data structure. We can also update any
particular data by specifying some conditions inside the loop, like the Selection operation.
Splitting: The Splitting operation allows us to divide data into various subparts decreasing the overall process
completion time.
Built in Data Types in C
void As the name suggests, it holds no value and is generally

used for specifying the type of function or what it returns.
If the function has a void type, it means that the function
will not return any value.
int Used to denote an integer type.
char Used to denote a character type.
float, double Used to denote a floating point type.
int *, float *, char * Used to denote a pointer type.
What is an Algorithm?
An algorithm is a set of guidelines or rules used to solve a problem or carry out a task. It is a methodical approach
that may be used to solve a mathematical riddle, run a computer program, or carry out a task like sorting a list.
An algorithm can also be used to specify a set of guidelines for carrying out a certain activity. Algorithms can be
designed to solve a wide range of problems and tasks, from the mundane to the complex.
Characteristics of Algorithm
 Unambiguous: Algorithms must have a clear and well-defined set of instructions that are easy to understand
and follow.
 Effective: The algorithm must produce the correct result in a finite amount of time.
 Feasible: The algorithm must be physically applicable and must be able to run on a computer.
 Input and Output: Algorithms must take inputs and produce outputs.
 Finite: The algorithm must terminate after a finite number of steps and must not go into an infinite loop.
 Deterministic: The algorithm must produce the same output for the same input every time it is run.
Time and Space Complexity

Time complexity is defined in terms of how many times it takes to run a given algorithm, based on the length of
the input. Time complexity is a measurement of how much time it takes to execute a particular algorithm because
such factors as programming language, operating system, and processing power are also considered.
When an algorithm is run on a computer, it necessitates a certain amount of memory space. The amount of
memory used by a program to execute it is represented by its space complexity. Because a program requires
memory to store input data and temporal values while running, the space complexity is auxiliary and input space.
Asymptotic notations
The main idea of asymptotic analysis is to have a measure of the efficiency of algorithms that don’t depend on
machine-specific constants and don’t require algorithms to be implemented and time taken by programs to be
compared. Asymptotic notations are mathematical tools to represent the time complexity of algorithms for
asymptotic analysis.
 Ο − Big Oh Notation
 Ω − Big Omega Notation
 Θ − Theta Notation
 o − Little Oh Notation
 ω − Little Omega Notation
Ο − Big Oh Notation: The notation Ο(n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to
complete.
The general step wise procedure for Big-O runtime analysis is as follows:
1. Figure out what the input is and what n represents.
2. Express the maximum number of operations, the algorithm performs in terms of n.
3. Eliminate all excluding the highest order terms.
4. Remove all the constant factors.
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n)
Example: Let us consider a given function, f(n) = 4n3+10n2+5n+1.
Considering g(n) = n3
f(n) ≥ 5.g(n) for all the values of n > 2.
Hence, the complexity of f(n) can be represented as O (g (n) ) ,i.e. O (n3).
Big Omega Notation, Ω: The notation Ω(n) is the formal way to express the lower bound of an algorithm's
running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take
to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
Example
Let us consider a given function, f(n) = 4.n3+10.n2+5.n+1
Considering g(n) = n3 , f(n) ≥ 4.g(n) for all the values of n > 0.
Hence, the complexity of f(n) can be represented as Ω (g (n) ) ,i.e. Ω (n3).
Theta Notation, θ: The notation θ(n) is the formal way to express both the lower bound and the upper bound of an
algorithm's running time. Some may confuse the theta notation as the average case time complexity; while big
theta notation could be almost accurately used to describe the average case, other notations could be used as well.
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
Example
Let us consider a given function, f(n) = 4.n3+10.n2+5.n+1
Considering g(n) = n3 , 4.g(n)≤ f(n)≤ 5.g(n) for all the values of n.
Hence, the complexity of f(n) can be represented as Ɵ (g (n) ) ,i.e. Ɵ (n3).
Difference Between Big oh, Big Omega and Big Theta :
S.No. Big Oh (O) Big Omega (Ω) Big Theta (Θ)
It is like (<=) rate of growth It is like (>=) rate of It is like (==) meaning the
1 of an algorithm is less than or growth is greater than or rate of growth is equal to a
equal to a specific value. equal to a specified value. specified value.
The upper bound of algorithm The algorithm’s lower The bounding of function
is represented by Big O bound is represented by from above and below is
notation. Only the above Omega notation. The represented by theta
2
function is bounded by Big O. asymptotic lower bound is notation. The exact
Asymptotic upper bound given by Omega notation. asymptotic behavior is done
is given by Big O notation. by this theta notation.
3 Big oh (O) – Upper Bound Big Omega (Ω) – Lower Big Theta (Θ) – Tight
Bound Bound
It is define as upper bound It is define as lower bound It is define as tightest bound

and upper bound on an and lower bound on an and tightest bound is the best
algorithm is the most amount algorithm is the least of all the worst case times
4 of time required ( the worst amount of time required ( that the algorithm can take.
case performance). the most efficient way
possible, in other words
best case).
Mathematically: Big Oh is 0 Mathematically: Big Mathematically – Big Theta

5 <= f(n) <= Cg(n) for all n >= Omega is 0 <= Cg(n) <= is 0 <= C2g(n) <= f(n) <=
n0 f(n) for all n >= n0 C1g(n) for n >= n0
Time Space Trade Off:

It is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving
a problem in very little space by spending a long time. Example involving the concept of Time Space Tradeoff:
1.If data is stored uncompressed, it takes more space but less time.
2.Storing only the source and rendering it as an image everytime the page is requested would be trading time for
space. More time used but less space.
Abstract Data Type (ADT):
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values 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.
Arrays:
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the
same type together. This makes it easier to calculate the position of each element by simply adding an offset to a
base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
One Dimensional Array:

 It is a list of the variable of similar data types.
 It allows random access and all the elements can be accessed with the help of their index.
 The size of the array is fixed.
 For a dynamically sized array, vector can be used in C++.
 Representation of 1D array:
Two Dimensional Array:
 It is a list of lists of the variable of the same data type.

 It also allows random access and all the elements can be accessed with the help of their index.
 It can also be seen as a collection of 1D arrays. It is also known as the Matrix.
 Its dimension can be increased from 2 to 3 and 4 so on.
 They all are referred to as a multi-dimension array.
 The most common multidimensional array is a 2D array.
 Representation of 2 D array:
Basis One Dimension Array Two Dimension Array

Store a single list of the element of a Store a ‘list of lists’ of the element of a
Definition
similar data type. similar data type.
Represent multiple data items as a Represent multiple data items as a table
Representation
list. consisting of rows and columns.
The declaration varies for different The declaration varies for different
programming language: programming language:
1. For C++, 1. For C++,

Declaration
datatype variable_name[row] datatype variable_name[row][column]
2. For Java, 2. For Java,

datatype [] variable_name= new datatype [][] variable_name= new
datatype[row] datatype[row][column]
Dimension One Two
size of (datatype of the variable of the
size of(datatype of the variable of the
Size(bytes) array)* the number of rows* the number
array) * size of the array
of columns.
Address of a[i][j] can be calculated in two

ways row-major and column-major
Address of a[index] is equal to (base
Address calculation. Address+ Size of each element of 1. Column Major: Base Address + Size
array * index). of each element (number of rows(j-lower
bound of the column)+(i-lower bound of
the rows))
2. Row Major: Base Address + Size of
each element (number of columns(i-lower
bound of the row)+(j-lower bound of the
column))
int arr[5]; //an array with one row int arr[2][5]; //an array with two rows and
and five columns will be created. five columns will be created.
Example
{a , b , c , d , e} a b c d e
f g h i j
Row Major Order:

Row major ordering assigns successive elements, moving across the rows and then down the next row, to
successive memory locations. In simple language, the elements of an array are stored in a Row-Wise fashion.
To find the address of the element using row-major order uses the following formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
I = Row Subset of an element whose address to be found,

J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume it as zero),
N = Number of column given in the matrix.
Example: Given an array, arr[1………10][1………15] with base value 100 and the size of each element is 1 Byte in
memory. Find the address of arr[8][6] with the help of row-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
Formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
Solution:
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
Column Major Order:

If elements of an array are stored in a column-major fashion means moving across the column and then to the next
column then it’s in column-major order. To find the address of the element using column-major order use the
following formula:
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of matrix(If not given assume it as zero),
M = Number of rows given in the matrix.
Example: Given an array arr[1………10][1………15] with a base value of 100 and the size of each element is 1 Byte in memory find
the address of arr[8][6] with the help of column-major order.
Solution:
Given:
Storage size of one element store in any array W = 1 Bytes
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10
Formula: used
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[I][J] = 157
Calculate the address of any element in the 3-D Array:

A 3-Dimensional array is a collection of 2-Dimensional arrays. It is specified by using three subscripts:
1. Block size
2. Row size
3. Column size
More dimensions in an array mean more data can be stored in that array.
To find the address of any element in 3-Dimensional arrays there are the following two ways-
 Row Major Order
 Column Major Order
1. Row Major Order:
To find the address of the element using row-major order, use the following formula:
Address of A[i][j][k] = B + W *(M * N(i-x) + N *(j-y) + (k-z))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
Example: Given an array, arr[1:9, -4:1, 5:10] with a base value of 400 and the size of each element is 2
Bytes in memory find the address of element arr[5][-1][8] with the help of row-major order?
Solution:
Given:
Column Subset of an element whose address to be found J = -1
Block Subset of an element whose address to be found K = 8
Storage size of one element store in any array(in Byte) W = 2
Lower Limit of row/start row index of matrix x = 1
Lower Limit of column/start column index of matrix y = -4
Lower Limit of blocks in matrix z = 5
M(row) = Upper Bound – Lower Bound + 1 = 9 – 1 + 1 = 9
N(Column)= Upper Bound – Lower Bound + 1 = 1 – (-4) + 1 = 6
Formula used:
Address of[I][J][K] =B + W (M * N(i-x) + N *(j-y) + (k-z))
Solution:
Address of arr[5][-1][8] = 400 + 2 * {[9 * 6 * (5 – 1)] + 6 * [(-1 + 4)]} + [8 – 5]
= 400 + 2 * (9*6*4)+(6*3)+3
= 400 + 2 * (237)
= 874
2. Column Major Order:
To find the address of the element using column-major order, use the following formula:
Address of A[i][j][k]= B + W(M * N(i – x) + M *(k – z) + (j – y))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
Example: Given an array arr[1:8, -5:5, -10:5] with a base value of 400 and the size of each element is 4
Bytes in memory find the address of element arr[3][3][3] with the help of column-major order?
Solution:
Given:
Block Subset of an element whose address to be found K = 3
Storage size of one element store in any array(in Byte) W = 4
Lower Limit of row/start row index of matrix x = 1
Lower Limit of column/start column index of matrix y = -5
Lower Limit of blocks in matrix z = -10
M (row)= Upper Bound – Lower Bound + 1 = 8-1+1 = 8
N (column)= Upper Bound – Lower Bound + 1 = 5 +5 + 1 = 11
Formula used:
Address of[i][j][k] = B + W(M * N(i – x) + M * (j-y) + (k – z))
Solution:
Address of arr[3][3][3] = 400 + 4 * ((8*11*(3-1)+8*(3-(-5)+(3-(-10)))
= 400 + 4 * ((88*2 + 8*8+13)
= 400 + 4 * (253)
= 400 + 1012
= 1412
Sparse Matrices and their representations
A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If
most of the elements of the matrix have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?

 Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only
those elements.
 Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero
elements.
Example:
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no
use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements.
This means storing non-zero elements with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
 Next node: Address of the next node
Linked lists: A linked list is a linear data structure, in which the elements are not stored at contiguous memory
locations.
o Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
o A node contains two fields i.e. data stored at that particular address and the pointer which contains the
address of the next node in the memory.
o The last node of the list contains pointer to the null.
The elements in a linked list are linked using pointers as shown below:
Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside any where in the
memory and linked together to make a list. This achieves optimized utilization of space.
o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node cannot be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.
Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be stored individually in
the memory. However, Array has several advantages and disadvantages which must be known in order to decide
the data structure which will be used throughout the program.
Array contains following limitations:
1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array
at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any element in the
array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful
because,
1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the
memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows
as per the program's demand and limited to the available memory space.
Singly linked list or One way chain
Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary
according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data
part of the node stores actual information that is to be represented by the node while the link part of the node stores
the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each
node contains only next pointer, therefore we cannot traverse the list in the reverse direction.
Data Space
Structure Time Complexity Complexity
Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion
Singly
Linked List
θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)
Operations on Singly Linked List
Node Creation
1. struct node
2. {
3. int data;
4. struct node *next;
5. };
6. struct node *head, *ptr;
7. ptr = (struct node *)malloc(sizeof(struct node *));
Traversal
struct node * temp = start;

printf(“\n list empty are-”);
while (temp!= NULL)
{
printf(‘%d “, temp -> data)
temp=temp -> next;
}
Insertion
You can add a node at the beginning, middle, and end.
Insert at the Beginning
 Create a memory for a new node.

 Store data in a new node.
 Change next to the new node to point to start.
 Change starts to tell the recently created node.
struct node *NewNode;

NewNode=malloc(sizeof(struct node));
NewNode -> data = 40;
NewNode -> next= start;
start= NewNode;
The insertion into a singly linked list can be performed at different positions. Based on the position of the new
node being inserted, the insertion is categorized into the following categories.
SN Operation Description
Insertion at It involves inserting any element at the front of the list. We just need to a few
1 beginning link adjustments to make the new node as the head of the list.
It involves insertion at the last of the linked list. The new node can be
Insertion at
2 inserted as the only node in the list or it can be inserted as the last one.
end of the list
Different logics are implemented in each scenario.
It involves insertion after the specified node of the linked list. We need to
Insertion after
3 skip the desired number of nodes in order to reach the node after which the
specified node
new node will be inserted. .
Deletion and Traversing
The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the
operation is categorized into the following categories.
Deletion at It involves deletion of a node from the beginning of the list. This is the simplest operation
1 beginning among all. It just need a few adjustments in the node pointers.
Deletion at It involves deleting the last node of the list. The list can either be empty or full. Different
2 the end of logic is implemented for the different scenarios.
the list
Deletion It involves deleting the node after the specified node in the list. we need to skip the desired
after number of nodes to reach the node after which the node will be deleted. This requires
3
specified traversing through the list.
node
Traversing In traversing, we simply visit each node of the list at least once in order to perform some
4 specific operation on it, for example, printing data part of each node present in the list.
Searching In searching, we match each element of the list with the given element. If the element is
5 found on any of the location then location of that element is returned otherwise null is
returned. .
Linked List in C: Menu Driven Program

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n
5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?

1
Enter value
1
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

2
Enter value?
2
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

3
Enter element value1
Enter the location after which you want to insert 1
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

8
printing values . . . . .
1
2
1
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

2
Enter value?
123
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

1
Enter value
1234
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

4
Node deleted from the begining ...
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

5
Deleted Node from the last ...
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

6
Enter the location of the node after which you want to perform deletion
1
Deleted node 2
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

8
printing values . . . . .
1
1
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

7
Enter item which you want to search?

1
item found at location 1
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
8.Show
9.Exit
Enter your choice?

9
Doubly Linked List
A doubly linked list (DLL) is a special type of linked list in which each node contains a pointer to the previous node
as well as the next node of the linked list.
Advantages of Doubly Linked List over the singly linked list:

 A DLL can be traversed in both forward and backward directions.
 The delete operation in DLL is more efficient if a pointer to the node to be deleted is given.
 We can quickly insert a new node before a given node.
 In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node,
sometimes the list is traversed. In DLL, we can get the previous node using the previous pointer.
Disadvantages of Doubly Linked List over the singly linked list:
 Every node of DLL Requires extra space for a previous pointer. It is not possible to implement DLL with a
single pointer though (See this and this).
 All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify
previous pointers together with the next pointers. For example in the following functions for insertions at
different positions, we need 1 or 2 extra steps to set the previous pointer.
Applications of Doubly Linked List:
 It is used by web browsers for backward and forward navigation of web pages
 LRU ( Least Recently Used ) / MRU ( Most Recently Used ) Cache are constructed using Doubly Linked Lists.
 Used by various applications to maintain undo and redo functionalities.
 In Operating Systems, a doubly linked list is maintained by thread scheduler to keep track of processes that are
being executed at that time.
In C, structure of a node in doubly linked list can be given as :

1. struct node
2. {
3. struct node *prev;
4. int data;
6. }
The prev part of the first node and the next part of the last node will always contain null indicating end in each
direction.
Memory Representation of a doubly linked list
Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list
consumes more space for every node and therefore, causes more expansive basic operations such as insertion and
deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the
directions (forward and backward).
In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the
starting address 1. Since this is the first element being added to the list therefore the prev of the list contains null.
The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer.
We can traverse the list in this way until we find any node containing null or -1 in its next part.
Operations on doubly linked list
Node Creation
1. struct node
2. {
4. int data;
6. };
7. struct node *head;
All the remaining operations regarding doubly linked list are described in the following table.
1 Insertion at beginning Adding the node into the linked list at beginning.
2 Insertion at end Adding the node into the linked list to the end.
Insertion after Adding the node into the linked list after the specified node.
3
specified node
4 Deletion at beginning Removing the node from beginning of the list
5 Deletion at the end Removing the node from end of the list.
Deletion of the node Removing the node which is present just after the node containing the given data.
6
having given data
Comparing each node data with the item to be searched and return the location of
7 Searching the item in the list if the item found else return null.
Visiting each node of the list at least once in order to perform some specific
8 Traversing operation like searching, sorting, display, etc.
Menu Driven Program in C to implement all the operations of doubly linked list
1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
7. int data;
8. };
9. struct node *head;
10. void insertion_beginning();
11. void insertion_last();
12. void insertion_specified();
13. void deletion_beginning();
14. void deletion_last();
15. void deletion_specified();
16. void display();
17. void search();
18. void main ()
19. {
20. int choice =0;
21. while(choice != 9)
22. {
23. printf("\n*********Main Menu*********\n");
24. printf("\nChoose one option from the following list ...\n");
25. printf("\n===============================================\n");
26. printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n
27. 5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");
28. printf("\nEnter your choice?\n");
29. scanf("\n%d",&choice);
30. switch(choice)
31. {
32. case 1:
33. insertion_beginning();
34. break;
35. case 2:
36. insertion_last();
37. break;
38. case 3:
39. insertion_specified();
40. break;
41. case 4:
42. deletion_beginning();
43. break;
44. case 5:
45. deletion_last();
46. break;
47. case 6:
48. deletion_specified();
49. break;
50. case 7:
51. search();
52. break;
53. case 8:
54. display();
55. break;
56. case 9:
57. exit(0);
58. break;
59. default:
60. printf("Please enter valid choice..");
61. }
62. }
63. }
64. void insertion_beginning()
65. {
66. struct node *ptr;
67. int item;
68. ptr = (struct node *)malloc(sizeof(struct node));
69. if(ptr == NULL)
70. {
71. printf("\nOVERFLOW");
72. }
73. else
74. {
75. printf("\nEnter Item value");
76. scanf("%d",&item);
77.
78. if(head==NULL)
79. {
80. ptr->next = NULL;
81. ptr->prev=NULL;
82. ptr->data=item;
83. head=ptr;
84. }
85. else
86. {
87. ptr->data=item;
88. ptr->prev=NULL;
89. ptr->next = head;
90. head->prev=ptr;
91. head=ptr;
92. }
93. printf("\nNode inserted\n");
94. }
95.
96. }
97. void insertion_last()
98. {
99. struct node *ptr,*temp;
100. int item;
101. ptr = (struct node *) malloc(sizeof(struct node));
102. if(ptr == NULL)
103. {
104. printf("\nOVERFLOW");
105. }
106. else
107. {
108. printf("\nEnter value");
110. ptr->data=item;
111. if(head == NULL)
112. {
114. ptr->prev = NULL;
115. head = ptr;
116. }
117. else
118. {
119. temp = head;
120. while(temp->next!=NULL)
121. {
122. temp = temp->next;
123. }
124. temp->next = ptr;
125. ptr ->prev=temp;
127. }
128.
129. }
130. printf("\nnode inserted\n");
131. }
132. void insertion_specified()
133. {
134. struct node *ptr,*temp;
135. int item,loc,i;
136. ptr = (struct node *)malloc(sizeof(struct node));
138. {
139. printf("\n OVERFLOW");
140. }
141. else
142. {
143. temp=head;
144. printf("Enter the location");
145. scanf("%d",&loc);
146. for(i=0;i<loc;i++)
147. {
148. temp = temp->next;
149. if(temp == NULL)
150. {
151. printf("\n There are less than %d elements", loc);
152. return;
153. }
154. }
155. printf("Enter value");
157. ptr->data = item;
158. ptr->next = temp->next;
159. ptr -> prev = temp;
160. temp->next = ptr;
161. temp->next->prev=ptr;
162. printf("\nnode inserted\n");
163. }
164. }
165. void deletion_beginning()
166. {
169. {
170. printf("\n UNDERFLOW");
171. }
172. else if(head->next == NULL)
173. {
174. head = NULL;
175. free(head);
176. printf("\nnode deleted\n");
177. }
178. else
179. {
180. ptr = head;
181. head = head -> next;
182. head -> prev = NULL;
183. free(ptr);
185. }
186.
187. }
188. void deletion_last()
189. {
192. {
193. printf("\n UNDERFLOW");
194. }
195. else if(head->next == NULL)
196. {
197. head = NULL;
198. free(head);
200. }
201. else
202. {
203. ptr = head;
204. if(ptr->next != NULL)
205. {
206. ptr = ptr -> next;
207. }
208. ptr -> prev -> next = NULL;
209. free(ptr);
211. }
212. }
213. void deletion_specified()
214. {
215. struct node *ptr, *temp;
216. int val;
217. printf("\n Enter the data after which the node is to be deleted : ");
218. scanf("%d", &val);
219. ptr = head;
220. while(ptr -> data != val)
222. if(ptr -> next == NULL)
223. {
224. printf("\nCan't delete\n");
225. }
226. else if(ptr -> next -> next == NULL)
227. {
228. ptr ->next = NULL;
229. }
230. else
231. {
232. temp = ptr -> next;
233. ptr -> next = temp -> next;
234. temp -> next -> prev = ptr;
235. free(temp);
237. }
238. }
239. void display()
240. {
242. printf("\n printing values...\n");
243. ptr = head;
244. while(ptr != NULL)
245. {
246. printf("%d\n",ptr->data);
247. ptr=ptr->next;
248. }
249. }
250. void search()
251. {
253. int item,i=0,flag;
254. ptr = head;
256. {
257. printf("\nEmpty List\n");
258. }
259. else
260. {
261. printf("\nEnter item which you want to search?\n");
263. while (ptr!=NULL)
264. {
265. if(ptr->data == item)
266. {
267. printf("\nitem found at location %d ",i+1);
268. flag=0;
269. break;
270. }
271. else
272. {
273. flag=1;
274. }
275. i++;
277. }
278. if(flag==1)
279. {
280. printf("\nItem not found\n");
281. }
282. }
283.
284. }
Output
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit
Enter your choice?

8
printing values...
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

1
Enter Item value12
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

1
Enter Item value123
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

1
Enter Item value1234
Node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

8
printing values...
1234
123
12
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

2
Enter value89
node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

3
Enter the location1
Enter value12345
node inserted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

8
printing values...
1234
123
12345
12
89
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

4
node deleted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

5
node deleted
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

8
printing values...
123
12345
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

6
Enter the data after which the node is to be deleted : 123
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

8
printing values...
123
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

7
Enter item which you want to search?

123

*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

6
Enter the data after which the node is to be deleted : 123
Can't delete
*********Main Menu*********
===============================================
2.Insert at last
5.Delete from last
7.Search
8.Show
9.Exit
Enter your choice?

9
Exited..
Circular Singly Linked List
In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have
circular singly linked list as well as circular doubly linked list.
We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked
list has no beginning and no ending. There is no null value present in the next part of any of the nodes.
Circular Doubly Linked List
Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two
consecutive elements are linked or connected by the previous and next pointer and the last node points to the first
node by the next pointer and also the first node points to the last node by the previous pointer.
Polynomial Representation
P(x) = 4x3 + 9x2 + 6x + 7

This is a univariate polynomial. It is defined in terms of just a single variable ‘x’. It is the summation of terms.
There is more than one term being added together. If we know the value of ‘x’ we can evaluate and get a result of
this polynomial. We want to represent this in our applications. So, for representation, we have to store the data
about that polynomial. That data can be stored either in an array or a linked list. So, we have already seen array
representation. Now we will see how to represent the data related to polynomials. If we observe the above
polynomial, each term is having its coefficient and exponent.
Points to keep in Mind while working with Polynomials:
 The sign of each coefficient and exponent is stored within the coefficient and the exponent itself
 Additional terms having equal exponent is possible one
 The storage allocation for each term in the polynomial must be done in ascending and descending order of
their exponent
Representation of Polynomial
Polynomial can be represented in the various ways. These are:
 By the use of arrays

 By the use of Linked List
Representation of Polynomial Using Arrays

There may arise some situation where you need to evaluate many polynomial expressions and perform basic
arithmetic operations like addition and subtraction with those numbers. For this, you will have to get a way to
represent those polynomials. The simple way is to represent a polynomial with degree 'n' and store the coefficient
of n+1 terms of the polynomial in the array. So every array element will consist of two values:
 Coefficient and
 Exponent
Consider a polynomial with two variables: 2x2+5x+2.
The array representation of the polynomial is give below:
2 2 0 5 1 1 2 0 2
Representation of polynomial using linked list
An ordered list of non-zero terms can be thought of as a polynomial. Each non-zero term consists of three sections
namely coefficient part, exponent part, and then a pointer pointing to the node containing the next term of the
polynomial.
Key Points in Polynomial Representation
 Coefficients and exponents are stored with their signs.

 Polynomials may have terms with equal exponents.
 Terms are typically arranged in order of descending or ascending exponent value.
Adding two polynomials using Linked List
Given two polynomial numbers represented by a linked list. The task is to add these lists meaning the coefficients
with the same variable powers will be added.
Note: Given polynomials are sorted in decreasing order of power.
Example:
Input:
head1: [[5, 2], [4, 1], [2, 0]]
head2: [[5, 1], [5, 0]]
Output: [[5, 2], [9, 1], [7, 0]]
Explanation:

DS - Unit 1

Uploaded by

Document Informationclick to expand document informationData science

Document Informationclick to expand document information

Copyright:

Available Formats

DS - Unit 1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS - Unit 1

Uploaded by

Copyright:

Available Formats

An Introduction to Data Structures

What is Data Structure?

The scope of a particular data model depends on two factors:

Understanding the Need for Data Structures

Why should we learn Data Structures?

Attributes ID Name Gender Job Title

Values 1234 Stacey M. Hill Female Software Developer

Classification of Data Structures

We can classify Data Structures into two categories:

1. Primitive Data Structure

The following figure shows the different classifications of Data Structures.

Non-Primitive Data Structures

Linear Data Structures

Types of Linear Data Structures

Arrays can be classified into different types:

Some Applications of Array:

Figure 4. A Linked List

Linked Lists can be classified into different types:

Some Applications of Linked Lists:

Some Applications of Stacks:

a. The Stack is used as a Temporary Storage Structure for recursive operations.

Figure 7. A Real-life Example of Queue

The following are the primary operations of the Queue:

a. Queues are generally used in the breadth search operation in Graphs.

Non-Linear Data Structures

Types of Non-Linear Data Structures

Trees can be classified into different types:

Some Applications of Trees:

Figure 10. A Graph

Some Applications of Graphs:

Built in Data Types in C

void As the name suggests, it holds no value and is generally

Time and Space Complexity

Difference Between Big oh, Big Omega and Big Theta :

S.No. Big Oh (O) Big Omega (Ω) Big Theta (Θ)

It is define as upper bound It is define as lower bound It is define as tightest bound

Mathematically: Big Oh is 0 Mathematically: Big Mathematically – Big Theta

Time Space Trade Off:

Abstract Data Type (ADT):

One Dimensional Array:

 It is a list of lists of the variable of the same data type.

Basis One Dimension Array Two Dimension Array

1. For C++, 1. For C++,

2. For Java, 2. For Java,

Address of a[i][j] can be calculated in two

Row Major Order:

Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

I = Row Subset of an element whose address to be found,

Column Major Order:

Calculate the address of any element in the 3-D Array:

Sparse Matrices and their representations

Why to use Sparse Matrix instead of simple matrix ?

Method 2: Using Linked Lists

Uses of Linked List

Why use linked list over array?

Array contains following limitations:

Singly linked list or One way chain