81–86 of 86 posts
Earlier quoted context omitted.
.. 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.
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.
Earlier quoted context omitted.
.. 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.
Earlier quoted context omitted.
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.
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.
Believe it or not, we actually had a C exam question where we were asked to sketch out an implementation of this. http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2010p3q6.... With classic mildly amusing exam humour introduction!
Anyone actually using this is almost certainly committing a heinous premature optimization.
Why would you not just do the following? interface LinkedList class BasicLinkedList implements LinkedList class XORLinkedList implements LinkedList
Earlier quoted context omitted.
Why would you not just do the following? interface LinkedList class BasicLinkedList implements LinkedList class XORLinkedList implements LinkedList
LinkedList list = new XORLinkedList(Collections.fromArray(arrayList)); Element ele = list.get(4); //Ok, when we construct the list we can store the first and second pointers and traverse to the fourth Element next = ele.next(); //???
You need an Iterator type that has the address of the previous and current nodes, in addition to your existing node / Element type.
LinkedList list = new XORLinkedList(Collections.fromArray(arrayList));
Iterator it = list.get(4); //now you can access it.element for data from index 4
it.next(); // now access it.element for data from index 5