View Full Version : O(1) insertion into an arbitrary position in a double-linked list

Sir Penguin
10-11-2004, 06:53:23
Is this possible while keeping the list node structure transparent to the user? I want to be able to have a function like this:

void insert(list* lst, sometype position, void* element);

It should run in constant time, and element should be the actual element, not a wrapper around the element (like a node). Position should be able to represent any position in the list.

I don't think it's possible, because you'd need to be able to inspect the whole list to find the position. But my old data structures course notes say that all list operations are O(1) time. I can only assume they want the function to take a pointer to the node you want to insert before, which seems kind of stupid, not to mention non-orthogonal.

Any takers?


10-11-2004, 10:21:36
Originally posted by Sir Penguin

But my old data structures course notes say that all list operations are O(1) time.

Typo? Left out "best case" before "O(1)"? Or perhaps they meant operations like adding and removing from beginning/end of list (ie. not an arbitrary position)?

10-11-2004, 15:53:26
LoD is right: best case is O(1), worst case is O(n), average is O(n/2) ;)

Sir Penguin
10-11-2004, 21:22:02
I thought the same when I took the course 2 years ago, but it's still in the notes. I guess I could have asked. :)
In the implementation of the List ADT by means of a doubly linked list:
The space used by a list with n elements is O (n )
The space used by each position of the list is O (1)
All the operations of the List ADT run in O (1) time
Operation element() of the
Position ADT runs in O (1) time
I can see how you'd keep it down to O(1) after doing the O(n) search for the position, by saving the position outside the list and passing it as a parameter. Then the space requirements double, and you're left with nonencapsulated crap. Oh well. I guess the universe isn't perfect.


10-11-2004, 23:45:43
If you want O(1) ALL the time, use either a really big simple hashtable, or a simple hashtable and very little data ;).

Sir Penguin
11-11-2004, 00:28:44
Or an array. :)

I'm writing a bunch of data structures in C so that I have them available when I need them (and so I know the ADTs). I just don't want to miss out on some trick that makes things really efficient.


Sir Penguin
11-11-2004, 00:29:25
Yeah, yeah, shut up about insertion and deletion. Nobody does that.


11-11-2004, 00:33:38
You'll never need it, you say?

19-11-2004, 18:00:19
He was being sarcastic...

19-11-2004, 18:07:15
Shush. I was giving him the code monkey signal for "famous last words". You obviously have been missing the monthly meetings in the Temple, Ash.