Since this is a syllabus topic, I would keep the notes focused on the general operations of data structures, before moving into individual structures such as arrays, linked lists, stacks, queues, trees, and graphs.

Data Structure Operations: Insertion, Deletion, Traversal, etc.

1. Introduction

A data structure is a method of organizing and storing data in a computer so that the data can be accessed, processed, and modified efficiently.

Once data is organized into a data structure, several operations can be performed on it. These operations are called data structure operations.

The major operations are:

1. Insertion

2. Deletion

3. Traversal

4. Searching

5. Accessing

6. Updating

7. Sorting

8. Merging

The exact implementation and efficiency of these operations depend on the type of data structure.

---

2. Insertion

Insertion is the operation of adding a new data element to an existing data structure.

The new element may be inserted:

• At the beginning

• At the end

• At a specified position

• Before or after a particular element

• According to an ordering condition

Example

Consider:

10   20   30   40

If 25 is inserted between 20 and 30:

10   20   25   30   40

In an array, insertion at a position generally requires shifting some existing elements.

C Example

#include <stdio.h>

int main()
{
    int a[10] = {10, 20, 30, 40};
    int n = 4;
    int pos = 2;
    int value = 25;

    for (int i = n; i > pos; i--)
        a[i] = a[i - 1];

    a[pos] = value;
    n++;

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

10 20 25 30 40

Complexity

For an array:

Position	Complexity
Beginning	O(n)
Middle	O(n)
End	O(1)*

*Assuming sufficient space is already available.

---

3. Deletion

Deletion is the operation of removing an existing element from a data structure.

After deletion, the structure may need to be reorganized to maintain its proper representation.

Example

Before deletion:

10   20   30   40   50

Delete 30:

10   20   40   50

For an array, elements after the deleted element are shifted toward the left.

C Example

#include <stdio.h>

int main()
{
    int a[10] = {10, 20, 30, 40, 50};
    int n = 5;
    int pos = 2;

    for (int i = pos; i < n - 1; i++)
        a[i] = a[i + 1];

    n--;

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

10 20 40 50

Complexity

For an array:

• Beginning → O(n)

• Middle → O(n)

• End → O(1)

---

4. Traversal

Traversal is the process of visiting and processing each element of a data structure systematically.

Traversal is required when we want to:

• Display all elements

• Calculate a sum

• Count elements

• Find a particular property

• Process every element

Example

For:

10   20   30   40

Traversal visits:

10 → 20 → 30 → 40

C Example

#include <stdio.h>

int main()
{
    int a[] = {10, 20, 30, 40};
    int n = 4;

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

10 20 30 40

For n elements, traversal requires:

$$O(n)$$

because every element is visited.

---

5. Searching

Searching is the operation of finding a particular element in a data structure.

For example:

Array: 10  20  30  40  50
Search: 40

The result may indicate that 40 is present at index 3.

Two fundamental searching techniques are:

5.1 Linear Search

Elements are checked one after another.

10 → 20 → 30 → 40 ✓

Worst-case complexity:

$$O(n)$$

5.2 Binary Search

Binary search works on a sorted array and repeatedly divides the search space into two parts.

Worst-case complexity:

$$O(\log n)$$

---

6. Accessing

Accessing means obtaining or retrieving a particular data element from a data structure.

For an array:

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

printf("%d", a[3]);

Output:

40

An array provides direct access through its index.

For an array:

$$Access = O(1)$$

when the index is known.

This is one of the major advantages of arrays.

---

7. Updating

Updating means changing the value of an existing element.

Example

Before:

10   20   30   40

Update 30 to 35:

10   20   35   40

In C:

a[2] = 35;

If the index is already known, updating an array element takes:

$$O(1)$$

---

8. Sorting

Sorting is the process of arranging data elements according to a specified order.

Ascending Order

10   20   30   40   50

Descending Order

50   40   30   20   10

Common sorting algorithms include:

• Bubble Sort

• Selection Sort

• Insertion Sort

• Merge Sort

• Quick Sort

• Heap Sort

Sorting is often performed before applying algorithms such as binary search.

---

9. Merging

Merging is the process of combining two data structures, usually of compatible types, into a single structure.

For example:

A = 10  20  30

B = 40  50  60

Merged = 10  20  30  40  50  60

A particularly important case is merging two sorted arrays while preserving sorted order.

Merging is a fundamental operation in Merge Sort.

---

10. Splitting

Splitting means dividing a data structure into two or more smaller structures.

Example:

Original:
10   20   30   40   50   60

             ↓

Part 1: 10   20   30

Part 2: 40   50   60

Splitting is particularly important in divide-and-conquer algorithms.

For example, Merge Sort repeatedly divides an array into smaller parts and subsequently merges them.

---

11. Data Structure Operations in Different Structures

The same operation can behave differently depending on the data structure.

Data Structure	Major Operations
Array	Access, insertion, deletion, traversal, searching, updating
Linked List	Insertion, deletion, traversal, searching
Stack	Push, pop, peek
Queue	Enqueue, dequeue, front/rear
Tree	Insertion, deletion, searching, traversal
Graph	Insertion, deletion, traversal, searching
Hash Table	Insertion, deletion, searching

---

12. Operations on Linked List

A linked list consists of dynamically allocated nodes connected through pointers.

The major operations include:

Insertion

A new node is created and linked to the existing nodes.

Deletion

A node is disconnected from the list and its memory can be released.

Traversal

The list is traversed from the first node until NULL.

Example:

struct Node *temp = head;

while (temp != NULL)
{
    printf("%d ", temp->data);
    temp = temp->next;
}

Unlike an array, linked-list elements do not need to occupy contiguous memory locations.

---

13. Operations on Stack

A stack follows the LIFO (Last In, First Out) principle.

Its major operations are:

Push

Adds an element to the top.

Pop

Removes the top element.

Peek

Examines the top element without removing it.

For a suitable stack implementation, push and pop generally take:

$$O(1)$$

---

14. Operations on Queue

A queue follows the FIFO (First In, First Out) principle.

The major operations are:

• Enqueue – insert an element at the rear.

• Dequeue – remove an element from the front.

• Front – access the first element.

• Rear – access the last element.

For an appropriate queue implementation, enqueue and dequeue can generally be performed in:

$$O(1)$$

---

15. Operations on Trees

For a tree, common operations include:

• Insertion

• Deletion

• Searching

• Traversal

Tree traversal includes:

1. Preorder

2. Inorder

3. Postorder

4. Level-order

For a binary tree containing n nodes, a complete traversal generally takes:

$$O(n)$$

---

16. Operations on Graphs

Important graph operations include:

• Adding vertices

• Removing vertices

• Adding edges

• Removing edges

• Searching

• Traversal

The two fundamental graph traversal algorithms are:

• BFS – Breadth First Search

• DFS – Depth First Search

BFS generally uses a queue, while DFS can use a stack or recursion.

---

17. Complexity of Common Operations

The following table gives a general idea; actual complexity depends on the particular implementation and position of the operation.

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at beginning	O(n)	O(1)
Delete at beginning	O(n)	O(1)
Insert at end*	O(1)	O(1) with tail pointer
Traverse	O(n)	O(n)
Update by known array index	O(1)	O(n) if node must be located

*For an array with available capacity; a dynamically resizing array may occasionally require resizing.

---

18. Importance of Data Structure Operations

Understanding these operations helps a programmer answer an important design question:

Which data structure should be selected for a particular problem?

For example:

• If fast random access is required → Array is suitable.

• If frequent insertion/deletion is required → Linked List may be suitable.

• If LIFO processing is required → Stack.

• If FIFO processing is required → Queue.

• If hierarchical data is required → Tree.

• If relationships between objects must be represented → Graph.

Thus, data structure selection should be based on the operations that are performed most frequently.

---

19. Summary

Data structure operations are the fundamental mechanisms used to manipulate organized data.

The important operations are:

Insertion – adding a new element
Deletion – removing an element
Traversal – visiting elements systematically
Searching – locating an element
Accessing – retrieving an element
Updating – modifying an element
Sorting – arranging elements
Merging – combining structures
Splitting – dividing a structure

The efficiency of an operation depends strongly on the underlying data structure. Therefore, understanding the operations is essential for designing efficient algorithms and selecting appropriate data structures.

1. Explain the importance of selecting an appropriate data structure based on required operations.