Running time of LinkedList and Sorted ArrayList functions Qu

Running time of LinkedList and Sorted ArrayList functions.

Questions (refers to both Linked list without a tail and Sorted Array List, so you need to have 4 answers.

1) Reversing the list (content of each node).

Linked List:

Sorted Array:

2) Removing a value at a given index.

Linked List:

Sorted Array:

Please give your answer like the answers below.

Example Question: Adding a value to the beginning of the linked list.
Example Answer: Running time: (1). You have a pointer to the head node in the list, so adding an element involves creating a new node (which is not dependent on the length of the list), setting the links in the new node, and changing the values of the head references. This takes somewhere around 10 steps to perform, and 10=(1).

Example Question: Adding a value to the beginning of the array list.
Example Answer: Running time: (n). You have to move everything over one cell to create a room for a new element. It will be done using a for loop that iterates through all elements. Since there are n elements in the list, it takes (n) to add a new element to the beginning of the array list.

Solution

1(a)

Reversing linked list

Running time = O(n)

To reverse the linked list, one must maintain three pointers say, currentnode, nextnode and previousnode.

Iterate through the list to reverse the string. Starting from the head node.

Follow the procedure:

head=previousnode;

while (currentnode! =null)

{

nextnode=currentnode. next;   

currentnode. next=previousnode;
previousnode=currentnode;
currentnode=nextnode;
}

Make the next of head node as null. This requires to traverse the complete list once. The list has n elements which means O (n) complexity.

1(b)

Reversing Sorted array

Running time O(n)

To reverse the sorted array, swapping of first and last element. One just need a temporary variable for swapping two elements. For the swap of first and last element, only the half array is traversed. Since there are n elements in the list, traversal of n/2 elements is done. Thus, it takes O (n/2) running time, that is, O (n).

2(a)

Removing a value at a given index in linked list.

Running time: O(1)

The index of the linked list is given. Deleting the node thus require only a slight change in pointers. The previous node of the target node will now point to the next node of the target node. This takes hardly two steps and 2 = O (1).

2(b)

Removing a value at a given index in sorted array.

Running time : O (1)

Deletion of head node is done in O(1) since it is the first node. Deleting any other node, one need to go to the node and shift all the element left. Somewhere it can be done in

O (1)