On Linked Lists | Hacker News Reader

On Linked Lists

swapped.cc

20 pointslatitude11 comments

Don't forget the x-list: http://en.wikipedia.org/wiki/XOR_linked_list

Oh. I may need an addendum then.

A more elegant (IMHO) implementation of the q-list has the second pointer point not at the tail, but rather at either the last next pointer or at the head pointer. This makes your appending logic simpler by not having to deal with the special case of an empty list.

A similar trick can be used with hash tables where the buckets are s-lists. You still get O(1) deletion within a bucket if your hash table returns the address of the pointer that refers to the element, rather than the element itself; and you save one whole pointer per element by doing so.

Using the author's terminology: the last two, the h-list and the d-list, ought to have O(1) insertion anywhere too. Since he calls removal at any position O(1) he must already have a pointer to the desired item. Also, this implies that insertion anywhere is O(1) in all four list types.

Sure thing, I've considered adding that. But since it is not directly related to the stack/queue/etc split, I kept it out for the sake of simplicity.

I think its more confusing to say that insertion is O(1) when insertion in the general case is O(n). Hash tables should be another discussion.

It does not say that the insertion is O(1). It says that it's O(1) _at the head_.

My post was in response to the thread above -- the bottom line is that for all of the linked lists you mention insertion/deletion is O(n) in the general case and O(1) at the head. The way its currently written is confusing and wrong.

Yeah, I was confused by this. Why is deletion not still O(n)? The back pointer doesn't gain you anything, because you can just drag along a temporary "last next" pointer when you're scanning to find the element to delete, which you have to do either way, so the s-list is asymptotically no slower at deletion--- O(n) to find the element to delete, and O(1) to delete it.

Should also consider the cases with zero head pointers.

For singly linked lists, a pointer to any node gives you the downstream part of the list, but not the upstream. (Can't think of any non-contrived, simple examples.)

For doubly linked lists, each node is effectively a head/tail. The list might be circular or might not. (Lots of kernel data structures where list membership is not the primary index.)

This makes the categorization a little messier.

h-list is only advantageous for hash tables if the links are in-element. Generalized hash tables would probably use s-list. But I like the terminology.

Reply on news.ycombinator.com