Question

6. List and explain the worst-case and average-case running times for each LinkedList method below:
(a) insert(iterator here, Object item)

(b) insertAtHead

(c) insertAtTail (aka push back)

(d) get(iterator here)

(e) get(index i)

(f) remove(iterator here)

(g) remove(index i)

(h) splice(iterator place here, iterator from here, iterator to here)

7. When should you use a Vector, and when should you use a Linked List?

Answer 1

Question#6

(A)

Average: n/2

Reason: The Position of the itreator can be at the middle of the size of the linklist.

Worst Time case: O(n)

Reason: When we are inserting at the last node of the link lost so we have to be traverse the whole Linklist.

(B)

Average: θ(1)

Reason: Whenever we are inserting at head so we have to attach the present head with a temp node so thats why the time complexity will be θ(1) .

Worst Time case: O(1)

Reason: Whenever we are inserting at head so we have to attach the present head with a temp node so thats why the time complexity will be O(1).

(C)

Average: O(n)

Reason: Whenever we are inserting at tail so we have to go through all the linklist in order to insert at tail as we have to traverse the linklist

Worst Time case: O(n)

Reason:Whenever we are inserting at tail so we have to go through all the linklist in order to insert at tail as we have to traverse the linklist

(D)

Average: n/2

Reason: The Position of the itreator can be at the middle of the size of the linklist.

Worst Time case: O(1)

Reason: As when we are getting the value through get function so might be the case that we have to get the last value so the worst time case will be O(1)

Question#7

Vectors are been useful in the cases when you are going for random read access and insertion and deletion on the back but in some cases the use of vector is not efficient like for insertions and deletions on the front or at any other position.

Where as the link list are very efficient for insertion and deletion of the items on the front or when you are been inserting at the back

PLEASE GIVE A THUMBS UP!!!! DONT GIVE A THUMBS DOWN IF YOU HAVE ANY QUERY SO COMMENT DOWN I WILL CLEAR IT FOR YOU