Unit 1: Introduction to data structure

Introduction to Data Structure

Data refers to raw facts, figures, symbols, or values that are collected but do not carry any meaningful information by themselves.

Examples:

• Numbers: 25, 100
• Characters: A, B
• Dates: 12-08-2024
• Words: Student

Data is the input for information processing.

Entity

An entity is a real-world object or concept about which data is stored.

Examples:

• Student
• Employee
• Book
• Bank Account

Each entity has attributes (e.g., Student → Roll No, Name, Marks).

Information

Information is processed, organized, and meaningful data that helps in decision-making.

Example:

• Data: Marks = 85
• Information: Jay scored 85 marks in Data Structures.

Difference Between Data and Information

Basis	Data	Information
Meaning	Raw facts	Processed data
Organization	Unorganized	Organized
Usefulness	Not directly useful	Useful
Decision Making	No	Yes
Example	500	Salary is ₹500 per day

Data Type

A data type specifies:

• Type of data
• Size in memory
• Range of values
• Operations allowed

It helps the compiler allocate proper memory.

Built-in Data Types

These are predefined data types provided by programming languages.

Common Built-in Data Types

Data Type	Description	Example
int	Integer numbers	10
float	Decimal values	3.14
double	Large decimals	123.456
char	Single character	'A'
boolean	True / False	true

Abstract Data Type (ADT)

An Abstract Data Type (ADT) defines what operations are performed on data, not how they are implemented.

Example: Stack ADT

Operations:

• push()
• pop()
• peek()
• isEmpty()

Implementation can be done using:

• Array
• Linked List

Definition of Data Structure

A data structure is a method of organizing, storing, and managing data in memory so that it can be used efficiently.

Why Data Structures Are Important?

• Faster access
• Efficient memory usage
• Better performance

Types of Data Structures

Data structures are classified into two major categories:

Linear Data Structure

In a linear data structure, data elements are arranged one after another in a sequence.

Characteristics:

• Single level
• Sequential arrangement
• Easy traversal

Types of Linear Data Structures

Data Structure	Description
Array	Fixed size, index-based
Linked List	Dynamic size, pointer-based
Stack	LIFO (Last In First Out)
Queue	FIFO (First In First Out)

Example: Array: 10 → 20 → 30 → 40

Non-Linear Data Structure

In a non-linear data structure, elements are not arranged sequentially and may have multiple relationships.

Characteristics:

• Multi-level structure
• Complex relationships
• Hierarchical arrangement

Types of Non-Linear Data Structures

Data Structure	Description
Tree	Parent-child structure
Graph	Network structure
Heap	Priority-based tree
Trie	String-based tree

Example: Tree:

• Root → Child → Sub-child

Linear vs Non-Linear Data Structure

Basis	Linear	Non-Linear
Arrangement	Sequential	Hierarchical
Levels	Single	Multiple
Complexity	Simple	Complex
Examples	Array, Stack	Tree, Graph

Important Exam Definitions

• Data: Raw facts and figures.
• Information: Processed data.
• Entity: Real-world object.
• ADT: Logical view of data.
• Data Structure: Organized way to store data.

Introduction to Algorithms

An algorithm is a finite sequence of well-defined steps used to solve a specific problem or perform a computation.

Example:

Algorithm to add two numbers:

1. Start
2. Read A, B
3. Sum = A + B
4. Print Sum
5. Stop

Difference Between Algorithm and Program

Basis	Algorithm	Program
Definition	Step-by-step solution	Implementation of algorithm
Language	Language-independent	Language-dependent
Purpose	Problem solving	Execution
Written in	Plain English / Pseudocode	C, Java, Python
Compilation	Not required	Required

Properties (Characteristics) of Algorithm

A good algorithm must have the following properties:

1. Input – Zero or more inputs
2. Output – At least one output
3. Definiteness – Each step is clear and unambiguous
4. Finiteness – Terminates after finite steps
5. Effectiveness – Steps are basic and feasible
6. Correctness – Produces correct output
7. Efficiency – Uses minimum resources

Algorithm Design Techniques

Algorithm design techniques are strategies used to create efficient algorithms.

Major Techniques:

Technique	Description	Example
Brute Force	Try all possibilities	Linear search
Divide & Conquer	Divide problem into sub-problems	Merge sort
Greedy	Choose best option at each step	Kruskal’s algorithm
Dynamic Programming	Store sub-problem results	Fibonacci
Backtracking	Try and undo	N-Queens
Branch & Bound	Optimization problems	Traveling Salesman

Performance Analysis of Algorithms

Performance analysis evaluates efficiency in terms of:

1. Time Complexity – Execution time
2. Space Complexity – Memory usage

Types of Performance Analysis

A. Time Complexity

Measures number of operations executed.

B. Space Complexity

Measures memory used including:

• Input storage
• Auxiliary variables
• Recursive stack

Complexity of Various Code Structures

Constant Time

x = a + b;

Time Complexity → O(1)

Single Loop

for(i = 1; i <= n; i++)

Time Complexity → O(n)

Nested Loop

for(i = 1; i <= n; i++)
 for(j = 1; j <= n; j++)

Time Complexity → O(n²)

Loop with Halving

for(i = n; i > 1; i = i/2)

Time Complexity → O(log n)

Order of Growth

Order of growth shows how running time increases with input size.

Common Orders of Growth

Order	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linear Log
O(n²)	Quadratic
O(2ⁿ)	Exponential

Asymptotic Notations

Asymptotic notations describe algorithm performance for large input sizes.

Big-O Notation (O)

Represents worst-case complexity.

Example:

T(n) = 3n² + 2n + 1
O(n²)

Big-Ω Notation (Omega)

Represents best-case complexity.

Example:

Ω(n)

Big-Θ Notation (Theta)

Represents average-case complexity.

Example:

Θ(n²)

Summary Table of Asymptotic Notations

Notation	Case
O	Worst
Ω	Best
Θ	Average

Important Exam Tips

• Write definition first
• Use tables for differences
• Explain complexity with examples
• Draw growth-rate graph if needed

Arrays

An array is a linear data structure that stores a fixed number of elements of the same data type in contiguous memory locations.

Features:

• Same data type
• Fixed size
• Indexed access
• Stored in continuous memory

Example: int a[5] = {10, 20, 30, 40, 50};

Single Dimensional Array (1-D Array)

A 1-D array stores elements in a linear form.

Representation: A[0], A[1], A[2], ..., A[n-1]

Example: Marks of students:

int marks[5];

Multidimensional Array

An array having more than one dimension.

Common Type:

• Two-Dimensional Array (2-D)

Example:

int a[3][3];

Represents a matrix with rows and columns.

Representation of Arrays in Memory

Although arrays appear multi-dimensional, memory is always linear. Therefore, mapping techniques are used.

Row Major Order

In row major order, elements of a row are stored one after another.

Used By:

• C, C++, Java

Memory Sequence:

Row 1 → Row 2 → Row 3

Address Formula for 2-D Array (Row Major):

Let:

• Base Address = B
• Element size = W
• Array A[M][N]

• Index A[i][j]

$$Address(A[i][j])=B+W\times (i\times N+j)$$

Column Major Order

In column major order, elements of a column are stored one after another.

Used By:

• FORTRAN, MATLAB

Memory Sequence:

Column 1 → Column 2 → Column 3

Address Formula for 2-D Array (Column Major):

$$Address(A[i][j])=B+W\times (j\times M+i)$$

Index Formula for 1-D Array

Let:

• Base Address = B
• Element size = W
• Index = i

$$Address(A[i])=B+W\times i$$

Applications of Arrays

• Storing marks, salaries, records
• Matrix operations
• Polynomial representation
• Sorting and searching algorithms
• Image processing

Sparse Matrix

A sparse matrix is a matrix in which most elements are zero.

Example:

$$\begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 0 \\ 5 & 0 & 0 \end{bmatrix}$$

Storing all zeros wastes memory.

Sparse Matrix Representation

Only non-zero elements are stored.

(a) Triplet Representation

Stores:

• Row index
• Column index
• Value

Format:

| Row | Column | Value |

First row contains:

• Total rows
• Total columns
• Number of non-zero elements

Example:

Row	Col	Value
3	3	2
0	2	3
2	0	5

Advantages:

• Saves memory
• Faster processing

Linked List

A linked list is a dynamic linear data structure in which elements (nodes) are not stored in contiguous memory.

Each node contains:

1. Data
2. Address of next node (link)

Types of Linked List

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Array Implementation of Linked List

Linked list can be simulated using arrays.

Two Arrays Used:

• DATA[] → stores data
• NEXT[] → stores index of next node

Example:

Index	DATA	NEXT
1	10	3
3	20	5
5	30	-1

Advantages:

• No pointers needed
• Useful where pointers are not supported

Disadvantages:

• Fixed size
• Manual memory management

Pointer Implementation of Linked List

Uses dynamic memory allocation and pointers.

Structure Example (C):

struct node {
    int data;
    struct node *next;
};

Advantages:

• Dynamic size
• Efficient insertion and deletion

Disadvantages:

• Extra memory for pointers
• Slower access compared to arrays

Array vs Linked List

Basis	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed	Dynamic
Access	Direct	Sequential
Insertion	Costly	Easy

Exam-Focused Points

• Write formulae clearly
• Draw memory representation diagrams
• Explain sparse matrix with example
• Compare array and linked list

Array Implementation of Singly Linked List

In array implementation, linked list is simulated using arrays instead of pointers.

Arrays Used:

1. DATA[] – stores data
2. NEXT[] – stores index of next node
3. START – stores index of first node

Example:

Index	DATA	NEXT
1	10	4
4	20	6
6	30	-1

-1 indicates end of list.

Advantages:

• No pointer required
• Useful in languages without pointer support

Disadvantages:

• Fixed size
• Manual free list management

Pointer Implementation of Singly Linked List

Each node is created dynamically using pointers.

Structure (C):

struct node {
    int data;
    struct node *next;
};

Representation:

[DATA | NEXT] → [DATA | NEXT] → NULL

Advantages:

• Dynamic size
• Efficient insertion and deletion

Disadvantages:

• Extra memory for pointer
• Sequential access only

Doubly Linked List

A doubly linked list contains two pointers:

1. Previous pointer
2. Next pointer

Structure:

struct node {
    int data;
    struct node *prev;
    struct node *next;
};

Representation:

NULL ← [prev|data|next] ⇄ [prev|data|next] → NULL

Advantages:

• Traversal in both directions
• Easier deletion

Disadvantages:

• Extra memory required
• More complex implementation

Circular Linked List

In a circular linked list, the last node points back to the first node.

Types:

1. Circular Singly Linked List
2. Circular Doubly Linked List

Representation:

[DATA|NEXT] → [DATA|NEXT] → (back to first)

Advantages:

• No NULL pointer
• Useful in round-robin scheduling

Operations on Linked List

1. Traversal

Visiting all nodes sequentially.

Algorithm:

1. Start from head
2. Print data
3. Move to next node
4. Stop when NULL is reached

2. Insertion in Linked List

(a) Insertion at Beginning

1. Create new node
2. New node → next = head
3. Head = new node

(b) Insertion at End

1. Traverse to last node
2. Last → next = new node
3. New node → next = NULL

(c) Insertion at Specific Position

1. Traverse to position
2. Adjust links

Deletion in Linked List

(a) Deletion at Beginning

1. Head = head → next
2. Delete old head

(b) Deletion at End

1. Traverse to second last node
2. Set next = NULL

(c) Deletion of Specific Node

1. Locate node
2. Change previous link

Polynomial Representation Using Linked List

A polynomial is represented as nodes containing:

• Coefficient
• Exponent

Example Polynomial:

$$5x^3+3x^2+2x+1$$

Node Structure:

struct poly {
    int coeff;
    int exp;
    struct poly *next;
};

Representation:

[5,3] → [3,2] → [2,1] → [1,0] → NULL

Polynomial Operations

1. Polynomial Addition

Steps:

1. Compare exponents
2. Add coefficients if equal
3. Copy remaining terms

Example:

$$(5x^3+2x+1)+(3x^3+4x^2)$$

Result:

$$8x^3+4x^2+2x+1$$

2. Polynomial Subtraction

Similar to addition, but subtract coefficients.

Example:

$$(5x^3+4x^2)-(3x^3+x^2)$$

Result:

$$2x^3+3x^2$$

Polynomial Multiplication

Each term of first polynomial is multiplied with every term of second polynomial.

Steps:

1. Multiply coefficients
2. Add exponents
3. Combine like terms

Example:

$$(2x+3)(x+4)$$

Result:

$$2x^2+11x+12$$

Comparison of Linked Lists

Feature	Singly	Doubly	Circular
Pointers	One	Two	One/Two
Traversal	One-way	Two-way	Circular
Memory	Less	More	Moderate
Complexity	Simple	Complex	Medium

Exam-Focused Tips

• Draw node diagrams
• Write algorithms step-wise
• Explain polynomial operations with examples
• Use tables for comparison