✅ Operations on Linear Arrays: Traversing, Inserting, Deleting

---

✅ Introduction

A Linear Array is a collection of elements stored in contiguous memory locations.
To manage data inside an array, we perform some basic operations such as:

✅ 1. Traversing
✅ 2. Insertion
✅ 3. Deletion

---

✅ 1. Traversing in Linear Array

✅ Definition

Traversing means visiting each element of the array one by one to perform some operation like displaying, printing, or processing values.

✅ Example: Printing all array elements.

---

✅ Algorithm for Traversing

Algorithm: Traverse_Array(A, N)

1. Start
2. Set i = 0
3. Repeat steps until i < N
   • Print A[i]
   • i = i + 1
4. Stop

---

✅ Example

Array: A = {10, 20, 30, 40}
Traversal output: 10 20 30 40

---

✅ Time Complexity

✅ O(n) (because we visit all elements once)

---

✅ 2. Insertion in Linear Array

✅ Definition

Insertion means adding a new element into an array at a particular position.

📌 Insertion in array is possible only if there is free space (array not full).

---

✅ Types of Insertion

Insertion can be done at:

✅ (A) Insertion at Beginning

New element is inserted at index 0, and all elements shift right.

✅ Example:
Insert 5 in {10, 20, 30} → {5, 10, 20, 30}

---

✅ (B) Insertion at End

New element is added at the last position.

✅ Example:
Insert 40 in {10, 20, 30} → {10, 20, 30, 40}

---

✅ (C) Insertion at Any Position

Element is inserted at a specific position and remaining elements shift right.

✅ Example:
Insert 25 at position 3 in {10, 20, 30, 40}
Result → {10, 20, 25, 30, 40}

---

✅ Algorithm for Insertion at Given Position

Let:

• Array = A
• Size = N
• Element to insert = ITEM
• Position = POS (1-based)
• Index = POS - 1 (0-based)

✅ Algorithm: Insert_Array(A, N, ITEM, POS)

1. Start
2. If N == MAX, print Overflow and Stop
3. Set i = N - 1
4. While i >= POS - 1
   • A[i + 1] = A[i] (shift right)
   • i = i - 1
5. Set A[POS - 1] = ITEM
6. N = N + 1
7. Stop

---

✅ Time Complexity of Insertion

✅ Best case (Insert at end): O(1)
✅ Worst case (Insert at beginning): O(n) (shifting needed)

---

✅ 3. Deletion in Linear Array

✅ Definition

Deletion means removing an element from an array from a specified position.

After deletion, elements are shifted left to fill the empty space.

---

✅ Types of Deletion

Deletion can be done at:

✅ (A) Deletion from Beginning

First element is removed, and all elements shift left.

✅ Example:
Delete from {10, 20, 30} → {20, 30}

---

✅ (B) Deletion from End

Last element is removed.

✅ Example:
Delete from {10, 20, 30} → {10, 20}

---

✅ (C) Deletion from Any Position

Element is removed from a given position and shifting is done.

✅ Example:
Delete element at position 2 from {10, 20, 30, 40}
Result → {10, 30, 40}

---

✅ Algorithm for Deletion at Given Position

Let:

• Array = A
• Size = N
• Position = POS

✅ Algorithm: Delete_Array(A, N, POS)

1. Start
2. If N == 0, print Underflow and Stop
3. Store deleted element: ITEM = A[POS - 1]
4. Set i = POS - 1
5. While i < N - 1
   • A[i] = A[i + 1] (shift left)
   • i = i + 1
6. N = N - 1
7. Stop

---

✅ Time Complexity of Deletion

✅ Best case (Delete from end): O(1)
✅ Worst case (Delete from beginning): O(n) (shifting needed)

---

✅ Summary Table (Important for Exam)

Operation	Meaning	Shifting Needed?	Time Complexity
Traversing	Visit all elements	No	O(n)
Insertion	Add new element	Yes (mostly)	O(n)
Deletion	Remove an element	Yes (mostly)	O(n)

---

✅ Conclusion

Operations on linear arrays such as traversing, insertion and deletion are basic and important. Traversing takes O(n) time, while insertion and deletion may require shifting of elements, making them O(n) in worst cases. Arrays provide fast access but are costly for frequent insertions and deletions.

---