Data Structure Class XII
What is a Data Structure?
A data structure is a way to organize and store data in computers efficiently, so
that it can be accessed and modified easily. Different data structures suit different
types of tasks and help programmers manage data efficiently, which is important
for solving complex problems in computer science.
Types of Data Structures
Data structures can be broadly categorized into:
Linear Data Structures
Non-linear Data Structures
1. Linear Data Structures
These organize data sequentially. Each element has a direct relationship
(previous/next) with neighbors.
Type Description Example
Array Fixed-size collection of same-type int arr[5] = {10, 20, 30, 40, 50};
elements
Linked Each element points to the next 10 → 20 → 30 → NULL
List element
Stack LIFO - last in, first out Adding plates one after another,
remove last one
Queue FIFO - first in, first out People in a line, first person served first
a)Example 1: Array
int scores[4] = {90, 80, 70, 60};
// Each element can be accessed directly by its index.
// scores[2] gives 70.
Arrays are quick for access but their size is fixed during creation.
b)Linked List
// Definition of a Node in a singly linked list
public class Node {
int data;
Node next;
// Constructor to initialize the node with data
public Node(int data)
{
[Link] = data;
[Link] = null;
}
}
Example 2: Stack
A stack works like a pile of books: you add (push) a book on
top, and only remove (pop) from the top.
Stack<Integer> stack = new Stack<>();
[Link](5); // Push 5
[Link](10); // Push 10
int last_item = [Link](); // Pops 10 out
It follows LIFO (Last In, First Out).
RAMAKRISHNA ACADEMY 7003793770
1
Data Structure Class XII
c) Example 3: Queue
Imagine people waiting in a line – the first person in is the first person out.
Queue<String> queue = new LinkedList<>();
[Link]("A"); // A enters
[Link]("B"); // B enters
[Link](); // Removes "A"
It uses FIFO (First In, First Out).
2. Non-linear Data Structures
Data is organized in hierarchical or interconnected forms. Items don’t follow a
direct sequence.
Type Description Easy Example
Tree Hierarchical, parent-child nodes Family tree: grandparent → parent → child
Graph Nodes are connected freely Map of cities with roads joining some cities
a)Tree
A tree starts with a root node and branches out.
Helps organize hierarchical information, like files in folders.
b)Graph
A graph is a set of points (nodes) connected by links (edges).
Useful for representing social networks, road maps, etc.
RAMAKRISHNA ACADEMY 7003793770
2
Data Structure Class XII
Link List:
Linked lists are dynamic data structures that store data in non-contiguous memory
locations, allowing flexibility in size and efficient memory utilization.
Why Link list more efficient than an Array?
Arrays are one of the fundamental data structures in programming. While versatile and
efficient for many use cases, they come with certain limitations:
Fixed Size: Once an array is declared, its size cannot be dynamically altered. This
can lead to either inefficient memory usage or insufficient space to hold data.
Sequential Memory Allocation: Arrays store their elements in contiguous
memory locations. This requirement can cause memory fragmentation issues when
sufficient contiguous memory is unavailable.
A linked list is a linear data structure where each element, called a node, contains
two components:
1. Data: The value stored in the node.
2. Next: A pointer to the next node in the sequence.
The nodes are dynamically allocated and linked together using pointers, making linked
lists inherently dynamic and capable of growing or shrinking as needed. Unlike arrays,
linked lists eliminate the need for contiguous memory allocation, making them resilient
to fragmentation.
Key Advantages of Linked Lists
Dynamic Size: Linked lists can grow or shrink during runtime without the need to
pre-allocate or reallocate memory.
Efficient Insertions and Deletions: Adding or removing elements in a linked list
is faster than in arrays, especially in the middle of the structure.
No Contiguous Memory Requirement: Nodes can be stored anywhere in
memory, eliminating fragmentation issues.
Types of Linked Lists
1. Singly Linked List: It consists
of nodes where each node
contains a data field and
a reference to the next node in
the linked list. The next of the
last node is null, indicating the
end of the list. Linked Lists
support efficient insertion and deletion operations.
2. Doubly Linked List: A doubly linked list is that it allows for efficient traversal of the
list in both directions. This is
because each node in the list
contains a pointer to the
previous node and a pointer to
the next node. This allows for
RAMAKRISHNA ACADEMY 7003793770
3
Data Structure Class XII
quick and easy insertion and deletion of nodes from the list, as well as efficient
traversal of the list in both directions.
3. Circular Linked List: A circular linked list is a data structure where the last node
points back to the first node, forming a closed loop.
o Structure: All nodes are connected in a circle, enabling continuous traversal
without encountering NULL.
o Difference from Regular Linked List: In a regular linked list, the last node
points to NULL, whereas in a circular linked list, it points to the first node.
o Uses: Ideal for tasks like scheduling and managing playlists, where smooth and
repeated.
Types of Circular Linked Lists
We can create a circular linked list from both singly linked lists and doubly linked lists. So,
circular linked lists are basically of two types:
i) Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer called the "next"
pointer. The next
pointer of the last
node points back
to the first node
and this results in
forming a circle.
In this type of
Linked list, we can only move through the list in one direction.
2. Circular Doubly Linked List:
In circular doubly linked list, each node has two pointers prev and next, similar to
doubly linked list.
The prev pointer
points to the
previous node
and the next
points to the next
node. Here, in
addition to the last node storing the address of the first node, the first node will also
store the address of the last node.
RAMAKRISHNA ACADEMY 7003793770
4