CODEWITHSUNDEEP
algorithmdoubly-linked-list
JillAndMe
JillAndMe

Reputation: 4551

Does doubly-linked-list can be O(log n) if I search in the middle?

enter image description here

If i search in the middle of the list and it is sorted in ascending order like

10 20 30 40 50

then imagine i search "20" and then pick 30(in the middle)

10 20 30 40 50

and then i can move left in the doubly-linked-list so move left(pick 20)

10 20 30 40 50

Does it can be O(log n) because the searching time be halved?

Upvotes: 0

Views: 1155

Answers (2)

paxdiablo
paxdiablo

Reputation: 882078

The thing that makes binary search (which is what you're discussing) possible is the ability to get to any element in the collection in constant time, O(1).

This means that arrays are one possibility since you can convert the base and index into a memory location in O(1). For example, if the array is based at byte location 314159 and each element is seven bytes in size, element 42 can be found at 314159 + 42 * 7 = 314453.

A linked list, even a doubly linked one, cannot do this since, in order to find an element, you have to traverse from either the head or the tail until you get there (and, in fact, you don't know you've gotten there unless you traverse them all or have the count handy).

So, for a linked list, it's very much an O(n) method for finding a given element.

Upvotes: 1

Xenon
Xenon

Reputation: 304

It’s possible only in linear O(n) time. Here is the whole explanation. https://stackoverflow.com/a/19554432/3457707 The main thing is you don’t have direct access to every element, so access time is not constant as in the array. So each time you have to iterate through elements, you cannot skip them as in the array.

Upvotes: 0

Related Questions