Hacker News Reader

A regular linked list doesn't have random access to elements, typically a head node is inserted into a function that iterates the list.

View on HN

.. or you pass any node to a function that operates on the list. iterate up/down insert/delete etc.

point being you dont have to iterate from the start of the list.

In theory yes, but how many references do you need to claim random access.

its how I use them. theres the list + some other structure/object that points/references the node, usually multiple time and the node is contained in multiple lists - big data + performance optimization

So your function needs to be passed current and next (or prev, depending on which direction you want to iterate). XOR-lists have lots of issues. This isn't one of them.

and your back to storing 2 pointers again.

No you're not. Your function needs to accept two pointers. Your data structure doesn't need to store two pointers.

Unless you're storing external pointers to every node (in which case you'll actually break even with the traditional implementation in terms of size), you'll still have significant savings. Passing an extra pointer to a function is pretty trivial in terms of size.

Reply on news.ycombinator.com