Describe how a new integer could be inserted into a sequence of sorted integers (so that the resulting sequence is also sorted) in each of the following cases: i. The sequence is stored in an array. ii. The sequence is stored in a linked list.

Inserting an Integer into a Sorted Sequence

Case i: The Sequence is Stored in an Array

Inserting a new integer into a sorted sequence that is stored in an array involves the following steps:

1. Find the Insertion Point:

   • Start from the beginning of the array and compare the new integer with each element until you find the first element that is greater than the integer to be inserted.
   • Let's denote the index of this element as insertionIndex.

2. Shift Elements:

   • If the array has enough space to accommodate the new integer, shift all elements from insertionIndex to the end of the array one position to the right to make space for the new integer.
   • This step is necessary because arrays have a fixed size and inserting an element without shifting would overwrite an existing element.

3. Insert the New Integer:

   • Place the new integer into the insertionIndex.

4. Handle Array Size:

   • If the array is full, you may need to create a new array with a larger size and copy all elements including the new integer into it.

Here's a step-by-step example:

Suppose we have an array A with the sorted sequence [1, 3, 5, 7] and we want to insert the integer 4.

1. Find the Insertion Point:

   • Compare 4 with each element: 4 is greater than 1 and 3, but less than 5.
   • insertionIndex = 2 (since arrays are zero-indexed).

2. Shift Elements:

   • Shift elements at and after index 2: [1, 3, (5), 5, 7].

3. Insert the New Integer:

   • Insert 4 at index 2: [1, 3, 4, 5, 7].

4. Handle Array Size:

   • If the array was initially [1, 3, 5, 7, _] (with an empty space), no resizing is needed.
   • If the array was [1, 3, 5, 7] (no empty space), create a new array [1, 3, 4, 5, 7, _].

Case ii: The Sequence is Stored in a Linked List

Inserting a new integer into a sorted sequence that is stored in a linked list involves the following steps:

1. Find the Insertion Point:

   • Traverse the linked list from the head and compare the new integer with the value of each node until you find the first node that has a value greater than the integer to be inserted.
   • Let's denote this node as insertionNode and its predecessor as previousNode.

2. Create a New Node:

   • Allocate memory for a new node and set its value to the new integer.

3. Insert the New Node:

   • Adjust the pointers such that previousNode points to the new node and the new node points to insertionNode.

Here's a step-by-step example:

Suppose we have a linked list with the sorted sequence 1 -> 3 -> 5 -> 7 and we want to insert the integer 4.

1. Find the Insertion Point:

   • Traverse the list: 4 is greater than 1 and 3, but less than 5.
   • previousNode is the node containing 3, and insertionNode is the node containing 5.

2. Create a New Node:

   • Create a new node newNode with the value 4.

3. Insert the New Node:

   • Adjust pointers: previousNode.next points to newNode, and newNode.next points to insertionNode.
   • The linked list now looks like: 1 -> 3 -> 4 -> 5 -> 7.

Comparison Table

Aspect	Array-Based Insertion	Linked List-Based Insertion
Find Insertion Point	O(n) time complexity	O(n) time complexity
Space for New Element	May require resizing	Only requires new node
Shift Elements	O(n) time complexity	Not required
Insert New Element	O(1) time complexity	O(1) time complexity
Overall Time Complexity	O(n) (due to shifting)	O(n) (due to traversal)
Space Complexity	O(1) or O(n) if resize needed	O(1)

In summary, inserting an integer into a sorted sequence stored in an array requires finding the insertion point, potentially shifting elements, and handling array size, which can lead to O(n) time complexity. In contrast, inserting into a sorted linked list also requires finding the insertion point, but the insertion itself is more straightforward with no need to shift elements, also resulting in O(n) time complexity. However, linked lists offer easier dynamic memory management compared to arrays.