Data: Raw facts, observations, or symbols without interpretation

Representation Technique: Numbers, characters, text, images, audio, video, binary values

Ex: 25, Student, 85

 Identifies individual values, tokens, and symbols

Information: Processed or organized data that has meaning in a particular context

Representation Technique: Tables, records, graphs, reports, databases, JSON/XML

Ex: Student scored 85 marks

Establishes relationships and context among data elements

Knowledge: Information combined with rules, experience, relationships, and interpretation

Representation Technique: Knowledge graphs, ontologies, rules, semantic networks, concept maps

Ex: 85 marks indicate good academic performance

 Identifies concepts, relationships, entities, and rules

Wisdom: Application of knowledge and experience to make appropriate decisions

Representation Technique: Decision models, recommendations, policies, expert systems

Ex: The student should be encouraged to participate in advanced courses

DATA

  ↓

( Processing + Context )

  ↓

INFORMATION

  ↓

(Interpretation + Relationships + Rules )

  ↓

KNOWLEDGE

  ↓

(Experience + Reasoning + Decision Making )

  ↓

WISDOM

Data Processing transforms raw facts into an organized or usable form.

Typical operations:

• Data collection

• Data entry

• Data validation

• Data cleaning

• Sorting

• Searching

• Classification

• Filtering

• Calculation

• Aggregation

• Storage

Example:

Raw Data: 45, 67, 89, 72, 55

        ↓ Data Processing

Sorted Data: 45, 55, 67, 72, 89     Average: 65.6

Information Processing: Information processing gives context and meaning to processed data.

Typical operations:

• Summarization

• Comparison

• Correlation

• Interpretation

• Categorization

• Visualization

• Report generation

• Pattern identification

Example:

Average Student Marks = 65.6 , Class Average = 58

        ↓ Information Processing

Student performance is above the class average.

Knowledge Processing: Knowledge processing uses information together with rules, relationships, concepts, and reasoning to derive new knowledge or make decisions.

Typical operations:

• Knowledge representation

• Semantic analysis

• Rule application

• Logical reasoning

• Inference

• Classification

• Prediction

• Recommendation

• Decision-making

• Knowledge discovery

Example:

Information: Student average = 65.6. and Class average = 58

        +

Knowledge Rule:

IF student performance > class average

THEN performance = "Above Average"

        ↓ Knowledge Processing

Inference: Student performance = Above Average

RAW DATA

   ↓

(DATA PROCESSING)

   ↓

PROCESSED DATA

   ↓

(INFORMATION PROCESSING)

   ↓

MEANINGFUL INFORMATION

   ↓

(KNOWLEDGE PROCESSING)

   ↓

KNOWLEDGE & INFERENCE

   ↓

(DECISION / RECOMMENDATION)

In Semantic Analysis: This distinction is particularly important in Natural Language Processing (NLP):

Data Processing→ text cleaning, tokenization, normalization, stemming

Information Processing→ extracting entities, keywords, relationships, and facts

Knowledge Processing→ understanding meaning, semantic relationships, reasoning, inference, and answering questions

For example:

"Ravi scored 85 marks in Data Structures."

• Data: Ravi, 85, Data Structures

• Information: Ravi scored 85 marks in Data Structures.

• Knowledge: Ravi has demonstrated strong performance in Data Structures, assuming an appropriate performance rule or benchmark.

• Inference: Ravi may be suitable for an advanced Data Structures activity.

A data type defines the kind of value that a variable can store, the amount of memory required to store it, the range of possible values, and the operations that can be performed on it

Primitive Data Types

Primitive data types are the basic built-in types a programming language provides.

char 

Character / small integer

1 byte

−128 to 127 or 0 to 255

'A'

Characters, symbols, text

_______________________________________________

int

Integer

4 bytes

−2,147,483,648 to 2,147,483,647

100

Counting, indexing, IDs

_______________________________________________

short

Small integer

2 bytes

−32,768 to 32,767

250

Memory-efficient integers

_______________________________________________

long

Large integer

4/8 bytes

Implementation-dependent

100000L

Large integer values

_______________________________________________

float

Decimal/real number

4 bytes

Approx. ±3.4 × 10³⁸

3.14f

Scientific calculations

_______________________________________________

double

High-precision decimal

8 bytes

Approx. ±1.7 × 10³⁰⁸

3.14159

High-precision calculations

_______________________________________________

Bool

Logical value

Implementation-dependent

0 or 1

1

True/false conditions

______________________________________________

void

No value

—

No value

void Functions with no return value

*Sizes and exact ranges can vary by C implementation. The ranges above are common for modern systems.

_______________________________________________

Type Modifiers in C

C provides modifiers that change the size or range of integer types:

• signed

• unsigned

• short

• long

Examples:

• unsigned int age;

• short int marks;

• long int population;

• unsigned char code;

For example, a typical unsigned int has a range: 0 to 4,294,967,295

 Non-Primitive Data Types

Non-primitive data types are built from primitive types and are generally used to represent collections or complex data structures.

Major Non-Primitive Types in C

Array -Collection of elements of the same data type

int marks[10];

Storing multiple values

_______________________________________________

Structure-Collection of different data types under one name

struct Student

Records/entities

_______________________________________________

Union-Different members share the same memory location

union Data

Memory-efficient representation

_______________________________________________

Pointer-Stores the address of another variable

int *p;

Dynamic memory, linked structures

_______________________________________________

String-Sequence of characters terminated by '\0'

char name[20];

Text processing

_______________________________________________

User-Defined Data Types

C also supports:

• struct

• union

• enum

• typedef

Example:

struct Student {

    int rollNo;

    char name[50];

    float marks;

};

Here, Student represents a complex data entity containing different kinds of values.

_______________________________________________

Data Types and Semantic Analysis

In semantic analysis, data types help determine whether values and operations are meaningful and valid.

For example:

int age = 20;

float marks = 85.5;

char grade = 'A';

The semantic analyzer determines:

• age → integer

• marks → floating-point value

• grade → character

• Whether assignments are type-compatible

• Whether operators are applicable

• Whether function arguments match parameter types

• Whether expressions produce valid results

Example:

int x;

float y;

x = y;   /*The semantic analysis phase checks the type compatibility between x and y.*/

Thus, data types provide the semantic meaning and constraints of values, making them fundamental to type checking, expression evaluation, symbol-table construction, and semantic analysis.

A data structure is an organization of data items in a particular manner, together with a set of valid operations applied to this organization.

A data structure is a specialized, systematic format for organizing, storing, and managing data in computer memory so that operations can be executed efficiently.

In literature: 

Data structure is formalized by Niklaus Wirth : Algorithms + Data Structures = Programs

 Thomas H. Cormen et al. (Introduction to Algorithms): A data structure serves as the concrete physical implementation of an Abstract Data Type (ADT)

It is described by the following three core components:

• Data Values: The set of primitive or complex values stored.

• Relationships: The logical arrangement (linear, hierarchical, or network) connecting data elements.

• Operations: The collection of algorithms permitted to manipulate and retrieve stored data.

Operations on Data Structures

• Access / Search-Locates a specific element or value within memory based on a key or index.

• Insertion-Adds a new element into a designated location within the structure.

• Deletion-Removes an existing element and reorganizes remaining memory references.

• Traversal-Accesses and processes every element in the structure sequentially or recursively exactly once.

• Sorting-Rearranges stored items into a specific order (e.g., numerical ascending or alphabetical).

• Merging-Combines elements from two separate structures into a single structure.

• Update-Replaces an existing element's value at a target reference or index.

Types of Data Structures

Primitive vs. Non-Primitive

• Primitive Data Structures: Basic building blocks provided directly by programming languages (e.g., Integer, Float, Character, Boolean, Pointer).

• Non-Primitive Data Structures: Complex structures built from primitive types to aggregate multiple values (e.g., Arrays, Linked Lists, Trees).

Linear vs. Non-Linear

• Linear Data Structures: Elements are linked sequentially in a single sequence, where each element connects directly to its predecessor and successor.

Array: A fixed-size, contiguous block of memory storing elements accessible via index.

Linked List: A sequence of nodes stored in non-contiguous memory connected via pointers (Singly, Doubly, or Circular).

Stack- A Last-In, First-Out (LIFO) structure where insertions (push) and deletions (pop) occur at one end.

Queue- A First-In, First-Out (FIFO) structure where items enter at the rear (enqueue) and exit at the front (dequeue).

• Non-Linear Data Structures: Elements are arranged hierarchically or as a complex network rather than sequentially.

Tree: A hierarchical node-based structure consisting of a root and child subtrees (e.g., Binary Search Tree, AVL Tree, B-Tree).

Graph: A non-linear network of vertices (nodes) linked by edges, representing arbitrary relationships.

Hash Table: An associative dictionary mapping key-value pairs using a hash function for $O(1)$ average lookup time.

Heap- A specialized tree maintaining min or max heap properties for priority queue operations.

Static vs. Dynamic

• Static: Fixed memory size determined at compile time (e.g., standard Arrays).

• Dynamic: Variable memory capacity that grows or shrinks dynamically at runtime via heap allocation (e.g., Dynamic Arrays, Linked Lists).

Stack

A Stack is a linear data structure in which elements are inserted and deleted from one end only, called the TOP. It follows the LIFO (Last In, First Out) principle.
Example: Stack of plates.

Possible Operations:

• Push: Insert an element onto the TOP of the stack.

• Pop: Remove an element from the TOP of the stack.

• Peek/Top: View the TOP element without removing it.

• isEmpty: Check whether the stack is empty.

• isFull: Check whether the stack is full in an array-based implementation.

• Size: Find the number of elements in the stack.

• Display/Traverse: View all elements of the stack.

• Search: Find a specified element in the stack.

• Clear: Remove all elements from the stack.

#define MAX 100

typedef struct {

    int data[MAX];

    int top;

} Stack;

void push(Stack *s, int value);

int pop(Stack *s);

int peek(const Stack *s);

int isEmpty(const Stack *s);

int isFull(const Stack *s);

void display(const Stack *s);

MultiStack

(n=2)

Two stacks can be implemented efficiently in one array by growing the two stacks from opposite ends of the array.

Two Stacks in a Single Array

Suppose the array has size MAX = 10.

• Stack 1 grows from left to right.

• Stack 2 grows from right to left.

• Both stacks share the unused space in the middle.

• Overflow occurs when top1 + 1 == top2.

Array: with 2 stacks

+----+----+----+----+----+----+----+----+----+----+

| S1 | S1 | S1 |    |    |    |    | S2 | S2 | S2 |

+----+----+----+----+----+----+----+----+----+----+

  ↑                         ↑

 top1                      top2

Initialization

#define MAX 10

int stack[MAX];

int top1 = -1;       // Stack 1

int top2 = MAX;      // Stack 2

PUSH Operation

______________________________

Push into Stack 1

void push1(int value)

{

    if (top1 + 1 == top2)

        printf("Stack Overflow");

    else

        stack[++top1] = value;

}

Push into Stack 2

void push2(int value)

{

    if (top1 + 1 == top2)

        printf("Stack Overflow");

    else

        stack[--top2] = value;

}

POP Operation

______________________________

Pop from Stack 1

int pop1()

{

    if (top1 == -1)

        return -1;

    return stack[top1--];

}

Pop from Stack 2

int pop2()

{

    if (top2 == MAX)

        return -1;

    return stack[top2++];

}

Example

If we perform:

push1(10)

push1(20)

push1(30)

push2(90)

push2(80)

push2(70)

The array becomes:

Index:  0    1    2    3    4    5    6    7    8    9

       +----+----+----+----+----+----+----+----+----+----+

       | 10 | 20 | 30 |    |    |    |    | 70 | 80 | 90 |

       +----+----+----+----+----+----+----+----+----+----+

                   ↑                   ↑

                  top1                top2

Main advantage: The unused space of one stack can be used by the other stack. This reduces wastage compared with allocating two separate fixed-size arrays.

Viva Questions

1. Why are two stacks implemented from opposite ends?

2. What is the initial value of top1?

3. What is the initial value of top2?

4. What is the condition for overflow?

5. How does push1() differ from push2()?

6. How does pop1() differ from pop2()?

7. What happens when the two stacks meet?

8. What is the advantage of implementing two stacks in one array?

9. What is the time complexity of push and pop operations?

10. Can the two stacks have different numbers of elements? Why?

Queue

A Queue is a linear data structure in which elements are inserted at the REAR and deleted from the FRONT. It follows the FIFO (First In, First Out) principle.
Example: People standing in a ticket queue.

Possible Operations:

• Enqueue: Insert an element at the REAR of the queue.

• Dequeue: Remove an element from the FRONT of the queue.

• Front/Peek: View the first element without removing it.

• Rear: View the last element in the queue.

• isEmpty: Check whether the queue is empty.

• isFull: Check whether the queue is full in an array-based implementation.

• Size: Find the number of elements in the queue.

• Display/Traverse: View all elements of the queue.

• Search: Find a specified element.

• Clear: Remove all elements from the queue.

#define MAX 100

typedef struct {

    int data[MAX];

    int front;

    int rear;

} Queue;

void enqueue(Queue *q, int value);

int dequeue(Queue *q);

int frontElement(const Queue *q);

int rearElement(const Queue *q);

int isEmptyQueue(const Queue *q);

int isFullQueue(const Queue *q);

void displayQueue(const Queue *q);

Queue Function Headers : A circular queue connects the last position back to the first position.

void initCircularQueue(Queue *q);

void enqueueCircular(Queue *q, int value);

int dequeueCircular(Queue *q);

int frontCircular(const Queue *q);

int rearCircular(const Queue *q);

int isEmptyCircular(const Queue *q);

int isFullCircular(const Queue *q);

void displayCircular(const Queue *q);

Fixed Front Design of Queue

In a Fixed Front Queue, the front of the queue is permanently anchored at index 0 (front = 0),

 while the rear pointer dynamically tracks the total element count (or the next available slot).

Because the front index never moves, removing an item requires shifting every remaining element left by one position to fill index 0.

Core Operations of fixed front queue design & Complexity

_________________________________________________________

Enqueue( &q, val)   O(1)  -Check overflow (rear == Capacity). Place val at arr[rear], then increment rear.

Dequeue(&q)       O(N)      - Check underflow (rear == 0). Save arr[0], shift all elements from index 1 to rear - 1 left by 1 slot, then decrement rear.

Peek(q)   O(1) - Return arr[0] directly without modifying rear.

IsEmpty(q)  O(1)  -Evaluate if rear == 0.

IsFull(q)    O(1)  -Evaluate if rear == Capacity.

C++ Implementation

#include <iostream>

#define CAPACITY 5

class FixedFrontQueue {

private:

    int arr[CAPACITY];

    int rear; // Tracks element count and next available insertion index

public:

    FixedFrontQueue() : rear(0) {}

    bool isFull()  { return rear == CAPACITY; }

    bool isEmpty() { return rear == 0; }

    void enqueue(int val) {

        if (isFull()) {

            std::cout << "Queue Overflow\n";

            return;

        }

        arr[rear++] = val; // Store at current rear, then increment

    }

    int dequeue() {

        if (isEmpty()) {

            std::cout << "Queue Underflow\n";

            return -1;

        }

        int frontValue = arr[0]; // Front is always fixed at index 0

        // Shift remaining elements left by 1 index

        for (int i = 1; i < rear; i++) {

            arr[i - 1] = arr[i];

        }

        rear--; 

        return frontValue;

    }

    int peek() {

        if (isEmpty()) return -1;

        return arr[0];

    }

};

Dry Run Execution

State 0 (Empty): arr = [ _ , _ , _ ], rear = 0

Enqueue(10), Enqueue(20), Enqueue(30):

arr = [ 10, 20, 30 ], rear = 3

Dequeue():

Output = 10 (at arr[0])

Shift elements: arr[0] = arr[1] (20), arr[1] = arr[2] (30)

Decrement rear to 2

Updated array: arr = [ 20, 30, _ ], rear = 2

Key Design Trade-Offs

1. No Wasted Capacity

 Unlike basic moving-front linear queues, this design prevents false overflows without needing modular index calculation. Memory is always tightly packed at the beginning of the array.

2. Performance Penalty

 Dequeuing requires $O(N) data movement due to continuous memory shifting. Standard circular queues achieve $O(1)$ dequeue performance by allowing front to advance instead, making circular queues preferred for high-volume applications.

Floating front design (Circular Queue)

#include <iostream>

class FloatingQueueWithNextPointers {

private:

    static const int N = 5; // Memory array size N (Max capacity = N - 1 = 4)

    int arr[N];

    int front;

    int rear;

    // Helper functions to pre-compute wrapped indices

    int getNextRear() const {

        return (rear + 1) % N;

    }

    int getNextFront() const {

        return (front + 1) % N;

    }

public:

    FloatingQueueWithNextPointers() : front(0), rear(0) {}

    bool isEmpty() const {

        return front == rear;

    }

    bool isFull() const {

        return getNextRear() == front; // Prevents rear from overrunning front

    }

    void enqueue(int val) {

        int nextrear = getNextRear();

        if (nextrear == front) { // Overflow check using explicit nextrear

            std::cout << "Queue Overflow\n";

            return;

        }

        arr[rear] = val;

        rear = nextrear; // Transition to pre-computed index

    }

    int dequeue() {

        if (isEmpty()) {

            std::cout << "Queue Underflow\n";

            return -1;

        }

        int val = arr[front];

        int nextfront = getNextFront();

        front = nextfront; // Transition to pre-computed index

        return val;

    }

    int peek() const {

        if (isEmpty()) return -1;

        return arr[front];

    }

};

Floating-Front Circular Queue — Reserved Slot

Let the circular array have N locations, with front and rear as floating indices.

Define:

NF=(front+1) mod NNF=(front+1)\bmod N NR=(rear+1) mod NNR=(rear+1)\bmod N

The slot immediately after rear is kept as the reserved/free slot. Therefore, the queue can contain at most N − 1 elements.

Condition

Next Front (NF)  NF = (front + 1) % N

Next Rear (NR) NR = (rear + 1) % N

Empty Queue  front == rear

Full Queue  NR == front

Reserved Slot Slot at NR is kept free before insertion

Capacity N − 1 elements

Enqueue 

Before inserting, calculate:

NR=(rear+1) mod N

If  (NR=front )

then the queue is FULL.

Otherwise:

rear = NR

Q[rear] = item

Thus, in this convention, the rear is advanced first, and the item is stored at the new rear position.

Dequeue

Calculate:

NF=(front+1) mod N

If (front=rear )

the queue is EMPTY.

Otherwise:

front = NF

item = Q[front]

So the front is also advanced first, and the item is then read.

Example: N = 6

Initially:

       0   1   2   3   4   5

       ┌───┬───┬───┬───┬───┬───┐

       │   │   │   │   │   │   │

       └───┴───┴───┴───┴───┴───┘

        ↑

      front

      rear

front = 0

rear  = 0

NF = (0 + 1) % 6 = 1

NR = (0 + 1) % 6 = 1

Initially front == rear, so the queue is empty.

After inserting 10:

NR = (0 + 1) % 6 = 1

rear = 1

Q[1] = 10

After inserting 20:

NR = (1 + 1) % 6 = 2

rear = 2

Q[2] = 20

The queue is conceptually:

       0       1       2       3       4       5

      ┌───────┬───────┬───────┬───────┬───────┬───────┐

      │       │  10   │  20   │       │       │       │

      └───────┴───────┴───────┴───────┴───────┴───────┘

        ↑                       ↑

      front                   rear

Here, front itself does not point to the first element. The first element is at:

NF=(front+1) mod N

This is the key idea behind the floating-front representation.

Most important distinction

There are two common circular-queue conventions:

Conventional front:

front → first element

rear  → next insertion position

Floating-front / reserved-slot convention:

front → position BEFORE first element

rear  → last element

Therefore:

NF=(front+1) mod N

gives the first element, while

NR=(rear+1) mod N

gives the reserved/free slot after the rear.

And the two key conditions are:

Empty  ⟺  front=rear\boxed{Empty \iff front=rear} Full  ⟺  NR=front\boxed{Full \iff NR=front}

This convention is particularly useful because empty and full states remain distinguishable without maintaining a separate count variable.

Priority Queue

A Priority Queue is a queue in which each element is associated with a priority, and elements are processed according to priority.

typedef struct {

    PriorityElement data[MAX];

    int size;

} PriorityQueue;

Function Headers

void initPriorityQueue(PriorityQueue *pq);

void insertPriority(PriorityQueue *pq, int value,  int priority);

int deletePriority(PriorityQueue *pq);

int peekPriority(const PriorityQueue *pq);

int isEmptyPriority(const PriorityQueue *pq);

int isFullPriority(const PriorityQueue *pq);

void displayPriority(const PriorityQueue *pq);

Deque : allows insertion and deletion from both ends.

void initDeque(Queue *dq);

void insertFront(Queue *dq, int value);

void insertRear(Queue *dq, int value);

int deleteFront(Queue *dq);

int deleteRear(Queue *dq);

int getFront(const Queue *dq);

int getRear(const Queue *dq);

int isEmptyDeque(const Queue *dq);

int isFullDeque(const Queue *dq);

void displayDeque(const Queue *dq);

Sparse Matrix

A Sparse Matrix is a matrix in which most elements are zero and only a small number of elements are non-zero. Special representations are used to save memory and processing time.

Example:

0  0  5

0  0  0

7  0  0

 can be represented as 

Row   Column   Value

 0      2        5

 2      0        7

A complete triplet representation generally also stores the matrix dimensions and number of non-zero elements.

#define MAX_TERMS 100

typedef struct {

    int row;

    int col;

    int value;

} Term;

typedef struct {

    int rows;

    int cols;

    int terms;

    Term data[MAX_TERMS];

} SparseMatrix;

Possible Operations:

• Create: Create and store a sparse matrix.

• Represent: Represent the matrix using triplet, tuple, or other compact forms.

• Insert: Add a non-zero element at a specified position.

• Delete: Remove a non-zero element or make an element zero.

• Update: Modify the value of an existing element.

• Access/Search: Find the value at a specified row and column.

• Display: Display the sparse matrix in normal or compact form.

• Transpose: Convert rows into columns and columns into rows.

• Fast Transpose: Perform an efficient transpose using compact representation.

• Addition: Add two sparse matrices.

• Subtraction: Subtract one sparse matrix from another.

• Multiplication: Multiply sparse matrices where dimensions are compatible.

• Count Non-Zero Elements: Determine the number of non-zero elements.

• Convert Representation: Convert between normal matrix and sparse/compact representation.

Operation

• Initialize void initSparse(SparseMatrix *s);

• Create void createSparse(SparseMatrix *s);

• Insert void insertSparse(SparseMatrix *s, int row, int col, int value);

• Delete void deleteSparse(SparseMatrix *s, int row, int col);

• Update void updateSparse(SparseMatrix *s, int row, int col, int value);

• Search int searchSparse(const SparseMatrix *s, int row, int col);

• Access int getSparse(const SparseMatrix *s, int row, int col);

• Display void displaySparse(const SparseMatrix *s);

• Transpose void transposeSparse(const SparseMatrix *s, SparseMatrix *t);

• Fast Transpose void fastTranspose(const SparseMatrix *s, SparseMatrix *t);

• Addition int addSparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Subtraction int subtractSparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Multiplication int multiplySparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Count Non-Zero int countNonZero(const SparseMatrix *s);

• Clear void clearSparse(SparseMatrix *s);

List

A List is a linear data structure in which elements are arranged in a sequential order. Lists may be implemented using arrays or linked nodes.

Example:

10 → 20 → 30 → 40

General List Operations:

• Create: Create a new list.

• Insert: Add an element at the beginning, end, or a specified position.

• Delete: Remove an element from the beginning, end, or a specified position.

• Traverse: Visit and process all elements.

• Search: Find a specified element.

• Access/Retrieve: Obtain an element at a specified position.

• Update/Replace: Modify an existing element.

• Size/Length: Find the number of elements.

• isEmpty: Check whether the list is empty.

• Sort: Arrange elements in ascending or descending order.

• Reverse: Reverse the order of elements.

• Merge: Combine two lists.

• Concatenate: Join one list after another.

• Clear: Remove all elements from the list.

• Copy: Create a duplicate of a list.

Array as List

An Array List stores list elements in contiguous memory locations.

Operations:

• Create

• Insert

• Delete

• Search

• Traverse

• Access by index

• Update

• Sort

• Reverse

• Merge

• Concatenate

• Find size

Unordered List

An Unordered List is a list in which elements are not arranged according to any specific order or sorting criterion. Elements can be stored in the order in which they are inserted.

Example:

30 → 10 → 40 → 20

Possible Operations:

• Insert at beginning

• Insert at end

• Insert at a specified position

• Delete an element

• Search for an element

• Traverse the list

• Access an element

• Update an element

• Find size

• Reverse the list

• Sort the list when required

• Merge or concatenate lists

• Clear the list

Ordered List

An Ordered List is a list in which elements are maintained in a specific order, usually ascending or descending according to their values or a defined key.

Example:

10 → 20 → 30 → 40

Possible Operations:

• Ordered Insert: Insert an element at its correct sorted position.

• Delete: Remove an element while maintaining the order.

• Search: Search for an element; efficient searching may be possible depending on implementation.

• Traverse: Visit elements in their sorted order.

• Access: Retrieve an element at a specified position.

• Update: Modify an element and restore the required order if necessary.

• Find Minimum: Retrieve the smallest element.

• Find Maximum: Retrieve the largest element.

• Find Size: Determine the number of elements.

• Merge: Combine two ordered lists while maintaining the order.

• Clear: Remove all elements.

Note: In an Ordered List, every insertion, deletion, or update should preserve the defined ordering criterion.

void initList(ArrayList *list);

int isEmptyList(const ArrayList *list);

int isFullList(const ArrayList *list);

int listSize(const ArrayList *list);

void insertBeginning(ArrayList *list, int value);

void insertEnd(ArrayList *list, int value);

void insertAtPosition(ArrayList *list, int position, int value);

int deleteBeginning(ArrayList *list);

int deleteEnd(ArrayList *list);

int deleteAtPosition(ArrayList *list, int position);

int searchList(const ArrayList *list, int key);

int getElement(const ArrayList *list, int position);

void updateElement(ArrayList *list, int position, int value);

void displayList(const ArrayList *list);

void reverseList(ArrayList *list);

void sortList(ArrayList *list);

void clearList(ArrayList *list);

An Unordered List contains elements that are not maintained according to any particular sorting order.

Example:

30 → 10 → 40 → 20

Operations

void insertUnordered(ArrayList *list, int value);

int deleteUnordered(ArrayList *list, int value);

int searchUnordered(const ArrayList *list, int key);

void updateUnordered(ArrayList *list, int position,int value);

void displayUnordered(const ArrayList *list);

void reverseUnordered(ArrayList *list);

void sortUnordered(ArrayList *list);

void mergeUnordered(const ArrayList *a, const ArrayList *b, ArrayList *result);

int listSize(const ArrayList *list);

void clearUnordered(ArrayList *list);

An Ordered List maintains its elements according to a specified order, generally ascending or descending.

Example: 10 → 20 → 30 → 40

Operations

void insertOrdered(ArrayList *list, int value);

int deleteOrdered(ArrayList *list, int value);

int searchOrdered(const ArrayList *list, int key);

void updateOrdered(ArrayList *list,int position, int value);

int findMinimum(const ArrayList *list);

int findMaximum(const ArrayList *list);

void displayOrdered(const ArrayList *list);

void mergeOrdered(const ArrayList *a, const ArrayList *b, ArrayList *result);

void clearOrdered(ArrayList *list);

Special Operation: Ordered Insertion

Unlike an unordered list: insertOrdered(&list, 25);

The function automatically determines the appropriate position so that the list remains ordered.