Given the following commands: LinkedList myList = new LinkedList(); myList.inser

Question

Given the following commands:

LinkedList myList = new LinkedList();

myList.insert(4);

myList.insert(6);

myList.insert(7);

1) Draw out what the linked list looks like after these inserts are performed

Now from this list, given the next set of commands:

myList.insert(10);

myList.delete(6);

myList.insert(-1);

2) Draw out what the linked list looks like after these inserts and delete are performed

Continue from this list with the next set of commands:

myList.update(4, 0);

myList.insert(2);

myList.delete(4);

3) Draw out what the linked list looks like after these commands are performed

4) Why is the linked list search performance O(n) even if the list data is sorted?

Explanation / Answer

Initially   [4, 6, 7]

After First Set Of Commands [4, 6, 7, 10, 6, -1]

After Second Set Of Commands   [6, 7, 10, 0, -1, 2]

So Final Set Is --->>>>> [6, 7, 10, 0, -1, 2]

Why is the linked list search performance O(n) even if the list data is sorted?

Answer: This is because we cant apply binary search on linkedlist because in a linked list we only know an element's successor not its predecessor.

Binary search algorithm is based on the logic of reducing your input size by half in every step until your search succeeds or input gets exhausted. Important point here is "the step to reduce input size should take constant time". In case of an array, it's always a simple comparison based on array indexes that takes O(1) time.

But in case of Linked list you don't have indexes to access items. To perform any operation on a list item, you first have to reach it by traversing all items before it. So to divide list by half you first have to reach middle of the list then perform a comparison. Getting to middle of list takes O(n/2)[you have to traverse half of the list items] and comparison takes O(1).
Total = O(n/2) + O(1) = O(n/2)

So the input reduction step does not take constant time. It depends on list size. hence violates the essential requirement of Binary search.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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