Data Structure

Data Structure is a set of algorithms that we can use in programming languages such as:

• C
• Python
• Java
• C++
• Ruby
• Swift
• Others

For example, suppose we have data containing:

• Student Name – Ramesh
• Age – 24

Here, Ramesh is a string data type and 24 is an integer data type.

We can organize this data as a student record containing both name and age.

Name	Age
Ramesh	24

Here:

• Name and Age are attributes or fields.
• Ramesh and 24 form a row or tuple.

The student record can then be collected and stored in a database as a data structure.

In simple terms, a data structure should be designed and implemented in such a way that it reduces the complexity of a program and increases efficiency.

Classification of Data Structure

Data structures can be broadly classified into:

1. Primitive Data Structure
2. Non-Primitive Data Structure

Primitive Data Structure

A Primitive Data Structure is directly operated by machine instructions.

It can be further classified into:

Integer

The integer data type is used to store integer values.

Float

The float data type is used to store decimal numbers with single precision.

It takes 4 bytes of memory space.

Examples:

• 4.5
• 23.9

Double

Double is used to store decimal numbers with double precision.

It takes 8 bytes of memory space.

Pointer

A pointer is a variable used to hold the address of another variable.

Non-Primitive Data Structure

A Non-Primitive Data Structure is a complex data structure derived from primitive data structures.

It can be classified into two categories:

1. Linear Data Structure
2. Non-Linear Data Structure

Linear Data Structure

A Linear Data Structure consists of data elements arranged in a sequential manner where every element is connected to its previous and next elements.

Some common linear data structures are:

• Array
• Stack
• Queue
• Linked List

Array

An Array is a collection of similar data types.

It stores multiple values in a single variable in contiguous memory locations.

The elements of an array can be accessed using their indexes.

An array cannot contain dissimilar types of data.

Its indexing begins from 0.

Syntax:

data type array-name[array-size];

Types of Array

There are mainly two types of arrays:

1. Single-Dimensional Array
2. Multi-Dimensional Array

1. Single-Dimensional Array

A Single-Dimensional Array uses one subscript [ ].

It is also called a 1D Array.

Syntax:

data type array-name[array-size];

2. Multi-Dimensional Array

A Multi-Dimensional Array uses two or more subscripts.

The most common multi-dimensional array is a Two-Dimensional Array (2D Array).

Syntax:

data type array-name[row-size][column-size];

Stack

A Stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle.

In a stack, elements are added and removed from the top only.

This means the most recently added item is the first item to be removed.

The main stack operations are:

1. Push
2. Pop

Push Operation

Push adds an element to the top of the stack.

For every new element added to the stack, the value of top is incremented by 1.

If the stack array is full and no new element can be added, it is called Stack Overflow.

Algorithm for Push Operation

Step 1: START.

Step 2: Store the element to push into the array.

Step 3: Check if:

top == (MAXSIZE – 1)

If true, the stack is full. Otherwise, go to Step 4.

Step 4: Increment top:

top = top + 1

Step 5: Add the element:

stack[top] = num

Step 6: STOP.

Pop Operation

Pop removes the top element from the stack.

After every POP operation, the value of top is decreased by 1.

If a POP operation is performed when there is no element in the stack, it is called Stack Underflow.

Algorithm for POP Operation

Step 1: START.

Step 2: Check if:

top == -1

If true, the stack is empty.

Step 3: Access the element pointed to by top:

number = stack[top]

Step 4: Decrease top by 1:

top = top – 1

Step 5: Continue the operation as required.

Step 6: STOP.

Queue

A Queue is a fundamental data structure that follows the First In, First Out (FIFO) principle.

In a queue:

• Elements are added at the rear.
• Elements are removed from the front.

This ensures that the oldest element is processed first.

The main queue operations are:

1. Enqueue
2. Dequeue

Enqueue

Enqueue adds an element to the rear of the queue.

Algorithm for Enqueue

Step 1: START.

Step 2: Check if the queue is full.

Step 3: If the queue is full, produce an overflow error and exit.

Step 4: If the queue is not full, increment the rear pointer to point to the next space.

Step 5: Add the data element to the queue location where the rear is pointing.

Step 6: End the process and exit.

Dequeue

Dequeue removes an element from the front of the queue.

Algorithm for Dequeue

Step 1: START.

Step 2: Check if the queue is empty.

Step 3: If the queue is empty, print underflow and exit.

Step 4: If the queue is not empty, access the data where the front is pointing.

Step 5: Increment the front pointer to point to the next available data element.

Step 6: Set the front and rear as -1 for the last element.

Step 7: End the process and exit.

Linked List

A Linked List is a linear data structure consisting of a sequence of elements called nodes.

Each node contains two main parts:

1. Data
2. Reference or pointer to another node

Unlike arrays:

• Linked lists do not have a fixed size in memory.
• Elements are not stored in contiguous memory locations.

Each node points to the next node, creating a chain-like structure.

There are two main types of linked lists:

1. Singly Linked List
2. Doubly Linked List

Singly Linked List

In a Singly Linked List, each node contains:

• Data
• A single pointer to the next node

The last node normally points to NULL, indicating the end of the list.

Only the next node can be accessed directly.

Figure: Add Single Linked List diagram here.

Doubly Linked List

In a Doubly Linked List, each node contains:

• Data
• Pointer to the next node
• Pointer to the previous node

This allows traversal in both:

• Forward direction
• Backward direction

Figure: Add Doubly Linked List diagram here.

Operations on Linked List

Some common linked list operations are:

1. Inserting a node at the beginning
2. Inserting a node at the end
3. Deleting the first node
4. Deleting the last node

1. Inserting a Node at the Beginning

Algorithm

Step 1: Create a new node with the given data.

newNode = CreateNode(newData)

Step 2: Set the next pointer of the new node to point to the current head.

newNode.next = head

Step 3: Update the head pointer to point to the new node.

head = newNode

Step 4: Return the updated head pointer.

2. Inserting a Node at the End

Algorithm

Step 1: Create a new node with the given data.

newNode = Node(newData)

Step 2: If the linked list is empty:

• Set head to point to the new node.
• Return head.

Step 3: Otherwise, traverse the list until the last node is reached.

Set:

currentNode = head

Then repeat until:

currentNode.next is NULL

Step 4: Set the next pointer of the last node to the new node.

currentNode.next = newNode

Step 5: Return the head pointer.

3. Deleting the First Node of a Linked List

Algorithm

Step 1: If head is NULL:

Return NULL because there is nothing to delete.

Step 2: Set temp to point to the node after the head.

temp = head.next

Step 3: Set head to point to temp.

head = temp

Step 4: Optionally free the memory occupied by the original head node.

Step 5: Return the updated head pointer.

4. Deleting the Last Node of a Linked List

Algorithm

Step 1: If head is NULL or head.next is NULL:

Set head to NULL and return.

Step 2: Set:

currentNode = head

Step 3: Continue until:

currentNode.next.next is NULL

Then set:

currentNode = currentNode.next

Step 4: Set:

currentNode.next = NULL

Step 5: Optionally free the memory occupied by the last node.

Step 6: Return the head pointer.

Non-Linear Data Structure

A Non-Linear Data Structure is a data structure in which each element can be connected to more than one adjacent element.

Unlike linear data structures, the elements are not necessarily arranged sequentially.

Common examples include:

• Tree
• Graph

Tree

A Tree is a hierarchical data structure consisting of nodes connected by edges.

Each node contains data.

The first node of a tree is called the Root Node.

Basic Terminologies of Tree

Path

A Path is a sequence of nodes where each node is connected to its adjacent node by an edge.

It starts from one node and ends at another node.

Root

The Root is the topmost node of a tree.

It is the starting point of the tree and has no parent.

Node

A Node is the fundamental unit of a tree.

It contains data and may have zero or more child nodes.

Parent Node

A Parent Node is a node that has one or more child nodes.

Child Node

A Child Node is a node directly connected to another node while moving away from the root.

Leaf Node

A Leaf Node is a node that does not have any child nodes.

It is located at the end of a branch.

Non-Leaf Node or Internal Node

A Non-Leaf Node is a node that has one or more child nodes.

Siblings

Siblings are nodes that share the same parent.

They are located at the same level in the tree.

Sub-Tree

A Sub-Tree is a portion of a tree consisting of a node and all of its descendants.

It can be considered a smaller tree inside a larger tree.

Ancestors

The Ancestors of a node are the nodes that lie on the path from the root to that node, excluding the node itself.

Descendants

The Descendants of a node are all nodes that can be reached from that node by following its child nodes recursively.

Degree of a Node

The Degree of a Node is the number of children it has.

Degree of a Tree

The Degree of a Tree is the maximum degree of any node in the tree.

Level of a Node

The Level of a Node is its distance from the root.

According to the notes:

• Root = Level 0
• Children of root = Level 1
• Next level = Level 2

Depth of a Node

The Depth of a Node is the length of the path from the root to that node.

Tree Traversal

Tree Traversal is the process of accessing or operating on each node in a tree.

A tree can be traversed in three main orders:

1. Pre-Order
2. In-Order
3. Post-Order

1. Pre-Order Traversal

Pre-Order follows:

VLR

Where:

• V = Visit Root
• L = Left Sub-Tree
• R = Right Sub-Tree

Algorithm

Step 1: Visit the root node.

Step 2: Traverse the left sub-tree using Pre-Order.

Step 3: Traverse the right sub-tree using Pre-Order.

2. In-Order Traversal

In-Order follows:

LVR

Where:

• L = Left Sub-Tree
• V = Visit Root
• R = Right Sub-Tree

Algorithm

Step 1: Traverse the left sub-tree using In-Order.

Step 2: Visit the root node.

Step 3: Traverse the right sub-tree using In-Order.

3. Post-Order Traversal

Post-Order follows:

LRV

Where:

• L = Left Sub-Tree
• R = Right Sub-Tree
• V = Visit Root

Algorithm

Step 1: Traverse the left sub-tree using Post-Order.

Step 2: Traverse the right sub-tree using Post-Order.

Step 3: Visit the root node.

Traversal of the Given Tree

According to the provided notes:

PRE-ORDER:

8, 3, 1, 6, 4, 7, 10, 13, 14

IN-ORDER:

1, 3, 4, 6, 7, 8, 10, 13, 14

POST-ORDER:

1, 4, 7, 6, 3, 13, 14, 10, 8

Figure: Add the provided tree diagram here.

Construct a Binary Tree Using Given Traversal

Pre-Order:

1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7

In-Order:

8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7

Binary Search Tree

A Binary Search Tree (BST) is a tree in which smaller elements are stored on the left side with respect to the root node, while larger elements are stored on the right side.

Figure: Add Binary Search Tree diagram here.

Graph

A Graph is the pictorial representation of edges and vertices.

It is used to represent relationships between objects.

Terminologies of Graph

Vertex or Node

A Vertex, also called a Node, is a fundamental unit of a graph.

It represents an entity or element.

For example, a vertex may represent:

• A person
• A city
• A website

Edge

An Edge is a connection between two vertices.

It may represent:

• A relationship
• An interaction
• A connection

In a directed graph, edges have a direction.

Adjacent Vertices

Two vertices are called Adjacent Vertices when they are connected by an edge.

In an undirected graph, if vertex A is adjacent to vertex B, then vertex B is also adjacent to vertex A.

In a directed graph, adjacency may depend on direction.

Path

A Path is a sequence of vertices where each adjacent pair is connected by an edge.

The length of a path is determined by the number of edges it contains.

Degree of a Node

The Degree of a Node in a graph is the number of edges connected to that node.

In a directed graph, degree may be divided into:

• In-Degree
• Out-Degree

In-Degree: Number of incoming edges.

Out-Degree: Number of outgoing edges.

Types of Graph

There are two main types of graphs:

1. Undirected Graph
2. Directed Graph

1. Undirected Graph

In an Undirected Graph, edges have no direction.

If vertex A is connected to vertex B, vertex B is also connected to vertex A.

Undirected graphs can represent relationships such as:

• Friendships in social networks
• Roads between cities

2. Directed Graph

In a Directed Graph, also called a Digraph, each edge has a direction.

The connection between two vertices is one-way.

Directed graphs can represent:

• Following relationships on social media
• Traffic flow
• Other directional relationships

Operations in Data Structure

The major operations performed on data structures include:

1. Inserting
2. Deleting
3. Searching
4. Sorting
5. Traversing
6. Merging

Inserting

Insertion involves adding a new element to a data structure at a specified position.

The insertion process depends on the type of data structure.

Example: Adding a new node at the end of a linked list.

Deleting

Deleting involves removing an existing element from a data structure.

Deletion may require modifying the data structure to maintain its properties.

Example: Removing a node from a binary search tree while maintaining its properties.

Searching

Searching means finding a specific element within a data structure.

The efficiency of searching depends on the type of data structure being used.

For example, a sorted array can be searched efficiently using binary search.

Examples:

• Searching for a value in a hash table.
• Searching for a key in a binary search tree.

Sorting

Sorting is the process of arranging elements in a particular order.

The order may be:

• Ascending
• Descending

Common sorting algorithms mentioned in the notes include:

• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Traversing

Traversing involves visiting and processing each element of a data structure.

Traversal may be used for:

• Printing elements
• Calculating the sum of elements
• Performing operations on each element

Example: Traversing a binary tree using Pre-Order, In-Order, or Post-Order.

Merging

Merging involves combining two or more data structures into a single data structure.

Examples include:

• Merging two sorted arrays into one sorted array.
• Merging two binary search trees into one binary search tree.

Advantages of Data Structure

The advantages of data structures include:

1. Easier processing of data.
2. Efficient storage.
3. Efficient designing of algorithms.
4. Secure way of storing data.
5. Accessing data anytime and anywhere.
6. Graphs can model real-life problems.

Applications of Data Structure

Data structures are used for many purposes, including:

1. Storing data in computers and other electronic devices.
2. Organizing data efficiently for easier processing.
3. Making traversal of large amounts of data easier and more effective.
4. Developing video games.
5. Storing data in memory before it is permanently saved.
6. Providing an abstract view of data.
7. Problem solving and developing effective algorithms.