3. Linked Lists. [30 marks total A linked list may have one of several forms. It

Question

3. Linked Lists. [30 marks total A linked list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is singly linked, only a nert pointer is present in each node; if doubly linked it has both a nert and a prev pointer present in each node. If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is at the head of the list, and the maximum element is at the tail. If the list is unsorted, the elements can appear in any order. Assume the pointer to the head of the list is NIL if the list is empty and points to the first node in the list otherwise. For each of the four types of lists, fill in the asymptotic worst-case run time for each dynamic set operation listed. Note that DELETE) needs to find the element x to delete; it could use SEarCH() for this purpose.

Explanation / Answer

1.Unsorted,singly linked list:

search(l,k):O(n)

Insert(L,x):O(n)

Delete(L,x):O(1)

Successor(L,x):O(n)

Predecessor(L,x):O(n)

Minimum(L,x):O(n)

Maximum(L,x):O(n)

2)Sorted,Singly Linked list:

search(l,k):O(n)   --       searching k element in linked list..because it is sorted we
                                   have to search until element in that sequence order

Insert(L,x):O(n)-----               Linked list sorted .so,we have to traverse whole linked list
           to place that particular 'x' in correct position

Delete(L,x):O(n)

Successor(L,x):O(1)

Predecessor(L,x):O(n)

Minimum(L,x):O(1)------Due to sorted list minimum element found at front only..
           no need of traverse whole thing

Maximum(L,x):O(1)

3)Unsorted,Doubly Linked-list:

search(l,k):O(n)

Insert(L,x):O(1)

Delete(L,x):O(n)

Successor(L,x):O(n)

Predecessor(L,x):O(n)

Minimum(L,x):O(n)

Maximum(L,x):O(n)

4)Sorted,Doubly Linked List:

search(l,k):O(n)

Insert(L,x):O(n)

Delete(L,x):O(1)

Successor(L,x):O(1)

Predecessor(L,x):O(1)

Minimum(L,x):O(1)

Maximum(L,x):O(1)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.