DATA STRUCTURE

UNIT 1:

Arrays are fundamental data structures in computer science used to store

collections of elements. Understanding how arrays are represented and managed in
memory is crucial for efficient programming and algorithm design. Here’s a
detailed explanation of array representation:

1.1 Basic Concept

An array is a collection of elements, each identified by an index or a key. All

elements in an array are of the same type, and they are stored in contiguous
memory locations.

1.2. Memory Representation

 Contiguous Memory Allocation: Arrays are stored in contiguous memory

blocks. This means that if an array starts at memory location L, the next
element is stored at L + size_of_element, and so on. This allows for
constant-time access to any element using its index.
 Indexing: Arrays are usually indexed starting from 0. For an array arr of
size n, the index of the first element is 0, and the index of the last element is
n-1.

1.3. Array Representation in Memory

 1D Arrays: A one-dimensional array arr with n elements can be visualized

in memory as:

Memory Location: | arr[0] | arr[1] | arr[2] | ... | arr[n-1] |

Each element arr[i] is located at base_address + i * element_size.

 2D Arrays: A two-dimensional array matrix with dimensions m x n can be

represented in memory as a single contiguous block. For a 2D array, there
are two common ways to access elements:

1.4. Applications of arrays

1. Data Storage
  Lists and Collections: Arrays are often used to store lists of items where
each item can be accessed using an index. For example, storing a list of
student names or a collection of integers.

2. Matrix and Grid Representations

 Mathematical Matrices: Arrays can represent mathematical matrices,

which are used in linear algebra for operations such as addition,
multiplication, and finding determinants.
 Game Boards: In games like chess or tic-tac-toe, a 2D array can represent
the game board.

3. Data Analysis

 Histograms: Arrays can be used to count occurrences of different values

and create histograms.
 Sorting and Searching Algorithms: Arrays are the underlying data
structure for many sorting and searching algorithms, such as QuickSort,
MergeSort, and Binary Search.

4. Caching and Buffering

 Data Caching: Arrays are used in caching mechanisms to temporarily store

frequently accessed data and improve performance.
 Buffering: Arrays are employed in buffering techniques to manage data
flow, such as in streaming applications or data transmission.

5. Algorithm Implementation

 Dynamic Programming: Arrays are used in dynamic programming to store

intermediate results and avoid redundant computations.
 Sliding Window Techniques: Arrays are used to implement sliding window
algorithms for problems like finding the maximum sum of a subarray.

6. Image Processing

 Pixel Data: Images are often represented as 2D arrays where each element
corresponds to a pixel's color value.
 Filters and Transformations: Arrays are used to apply filters and
transformations to images, such as blurring or edge detection.
7. Database Management

 Indexing: Arrays can be used to implement indexing techniques for faster

data retrieval.
 Data Storage: Some databases use arrays to store records or columns of
data.

8. Networking

 Packet Data: Arrays are used to manage data packets in networking

protocols.
 Routing Tables: Arrays can represent routing tables that store paths to
different network destinations.

9. Scientific Computing

 Simulations: Arrays are used to represent data in simulations, such as

physical systems or biological processes.
 Numerical Analysis: Arrays are used for numerical methods, including
solving systems of equations and performing statistical analysis.

10. Operating Systems

 Memory Management: Arrays are used in memory management

techniques, such as page tables or process scheduling.
 File Systems: Arrays can be used to manage file system blocks and
directory structures.

11. Compilers and Interpreters

 Symbol Tables: Arrays are used to implement symbol tables that store
variable names and their associated attributes.
 Syntax Parsing: Arrays are used in parsers to handle expressions and syntax
trees.

12. Financial Systems

 Time Series Analysis: Arrays are used to manage and analyze time series
data, such as stock prices over time.
 Portfolio Management: Arrays are used to handle and compute financial
portfolios, including risk and return calculations.
1.5 Sparse Matrix

Sparse matrix is a matrix in which most of the elements are zero. Representing a
sparse matrix efficiently is crucial because storing all elements of a large matrix,
where the majority are zeros, would be wasteful in terms of both memory and
computation. Here’s a detailed look at sparse matrices and their various
representations:

A. Definition

 A sparse matrix is characterized by having a majority of its elements as zero.

This contrasts with a dense matrix, where most elements are non-zero.
B. Representation Methods

 To efficiently store and manipulate sparse matrices, several specialized

representations are used:

B.1. Coordinate list (coo) format

 Description: stores a list of non-zero elements along with their row and
column indices.
 Structure: three separate lists (or arrays):
o Values: stores the non-zero values.
o Row_indices: stores the row indices of the non-zero values.
o Col_indices: stores the column indices of the non-zero values.

Example: for a matrix:

[0 0 3 0 4 0 5 0 0]

Coo representation would be:

o Values = [3, 4, 5]
o Row_indices = [0, 1, 2]
o Col_indices = [2, 1, 0]

B.2 Compressed sparse row (csr) format

 Description: efficiently stores matrix data by compressing row and column

indices.
 Structure:
 o Values: stores non-zero values.
o Column_indices: stores column indices for each non-zero value.
o Row_pointers: stores the index in values where each row starts. The
length of this list is number_of_rows + 1.

Example: for the same matrix as above:

o Values = [3, 4, 5]
o Column_indices = [2, 1, 0]
o Row_pointers = [0, 1, 2, 3]

This indicates:

o Row 0 starts at index 0 in values and ends at index 1.

o Row 1 starts at index 1 and ends at index 2.
o Row 2 starts at index 2 and ends at index 3.

B.3 Compressed sparse column (csc) format

 Description: similar to csr but compresses columns instead of rows.

 Structure:
o Values: stores non-zero values.
o Row_indices: stores row indices for each non-zero value.
o Column_pointers: stores the index in values where each column starts.
The length of this list is number_of_columns + 1.

Example: for the same matrix:

o Values = [5, 4, 3]
o Row_indices = [2, 1, 0]
o Column_pointers = [0, 1, 2, 3]

This indicates:

o Column 0 starts at index 0 in values and ends at index 1.

o Column 1 starts at index 1 and ends at index 2.
o Column 2 starts at index 2 and ends at index 3.
B.4. Diagonal storage

 Description: used for matrices where non-zero elements are concentrated

along diagonals.
 Structure: stores non-zero elements along with their diagonals.
 Example: for a tridiagonal matrix, only the main diagonal and the two
diagonals directly above and below it are stored.

Example: for a matrix:

[1 2 0 4 5 6 0 8 9]

Diagonal representation would be:

o Diagonal 0 (main diagonal): [1, 5, 9]

o Diagonal -1 (below main): [4, 8]
o Diagonal 1 (above main): [2, 6]

1.6 Linear List

A linear list is a collection of elements arranged in a sequential order where each

element is accessible by its position or index. The linear list is often contrasted
with non-linear data structures like trees and graphs.

1.6.1. Types of Linear Lists

Linear lists can be implemented using various data structures, each with different
characteristics:

A. Array

 Description: An array is a fixed-size, contiguous block of memory where

each element is accessible by its index.
 Characteristics:
o Fixed Size: The size of an array is defined when the array is created
and cannot be changed.
o Direct Access: Allows direct access to elements using an index (O(1)
time complexity).
o Example:

Int arr[5] = {1, 2, 3, 4, 5};

 o Pros: Fast access time, simple structure.
o Cons: Fixed size, insertion, and deletion can be costly if resizing is
needed.

B. Linked List

 Description: A linked list is a collection of nodes where each node contains

data and a reference (or pointer) to the next node in the sequence.
 Types:
o Singly Linked List: Each node has a reference to the next node.
 Example:
 Struct Node {

Int data;
Node* next;
};

o Doubly Linked List: Each node has references to both the next and
previous nodes.
 Example:

Struct Node {
Int data;
Node* next;
Node* prev;

A singly linked list is a linear data structure where each element (node) contains
data and a reference (or pointer) to the next node in the sequence. Here’s a
comprehensive overview of its implementation, as well as insertion, deletion, and
searching operations.

1. Implementation

Here is a basic implementation of a singly linked list in C++:

#include <iostream>

Using namespace std;

// Define a Node structure

Struct Node {
Int data;
Node* next;

// Constructor to initialize a new node

Node(int value) : data(value), next(nullptr) {}
};

// Define the singlylinkedlist class

Class singlylinkedlist {
Private:
Node* head;

Public:
// Constructor to initialize the list
Singlylinkedlist() : head(nullptr) {}

// Destructor to clean up memory

~singlylinkedlist() {
Node* current = head;
Node* nextnode;

While (current != nullptr) {

Nextnode = current->next;
Delete current;
Current = nextnode;
}
}

// Insert a new node at the end of the list

Void insert(int value) {
Node* newnode = new Node(value);
If (head == nullptr) {
Head = newnode;
} else {
Node* current = head;
While (current->next != nullptr) {
Current = current->next;
}
Current->next = newnode;
}
}

// Delete a node with a given value

Void deletevalue(int value) {
If (head == nullptr) return;

// Handle deletion of the head node

If (head->data == value) {
Node* temp = head;
Head = head->next;
Delete temp;
Return;
}

Node* current = head;

While (current->next != nullptr && current->next->data != value) {
Current = current->next;
}

// Node with the value not found

If (current->next == nullptr) return;

Node* temp = current->next;

Current->next = temp->next;
Delete temp;
}

// Search for a node with a given value

Bool search(int value) {
Node* current = head;
While (current != nullptr) {
If (current->data == value) {
Return true;
}
Current = current->next;
}
Return false;
}

// Display the list

Void display() {
Node* current = head;
While (current != nullptr) {
Cout << current->data << " ";
Current = current->next;
}
Cout << endl;
}
};

Int main() {
Singlylinkedlist list;

List.insert(10);
List.insert(20);
List.insert(30);

Cout << "List: ";

List.display();

Cout << "Searching for 20: " << (list.search(20) ? "Found" : "Not Found") << endl;

List.deletevalue(20);
Cout << "List after deleting 20: ";
List.display();

Return 0;
}
2. Operations

 Insertion: Adds a new node to the end of the list.

 Deletion: Removes a node with a specific value.
 Searching: Checks whether a node with a specific value exists in the list.

A. Insertion

To insert a new node into a singly linked list, follow these steps:
 1. Create a New Node: Allocate memory for a new node and set its data.
2. Insert at the End: If the list is empty, make the new node the head.
Otherwise, traverse to the end of the list and link the new node there.

Insertion Example:

Void insert(int value) {

Node* newnode = new Node(value);
If (head == nullptr) {
Head = newnode;
} else {
Node* current = head;
While (current->next != nullptr) {
Current = current->next;
}
Current->next = newnode;
}
}
B. Deletion

To delete a node from a singly linked list:

1. Find the Node: Traverse the list to find the node to be deleted.
2. Update Pointers: If the node to delete is found, update the pointer of the
previous node to skip the node to be deleted and delete the node.

Deletion Example:

Void deletevalue(int value) {

If (head == nullptr) return;

// Handle deletion of the head node

If (head->data == value) {
Node* temp = head;
Head = head->next;
Delete temp;
Return;
}

Node* current = head;

While (current->next != nullptr && current->next->data != value) {
Current = current->next;
}

// Node with the value not found

If (current->next == nullptr) return;

Node* temp = current->next;

Current->next = temp->next;
Delete temp;
}
C. Searching

To search for a node with a specific value:

1. Traverse the List: Start from the head and traverse through each node.
2. Check Value: Compare each node's data with the target value.

Search Example:

Bool search(int value) {

Node* current = head;
While (current != nullptr) {
If (current->data == value) {
Return true;
}
Current = current->next;
}
Return false;
}