3 ms·
Why would you not just do the following? interface LinkedList class BasicLinkedList implements LinkedList class XORLinkedList implements LinkedList
by glimcat 14y ago
Why would you not just do the following?
interface LinkedList
class BasicLinkedList implements LinkedList
class XORLinkedList implements LinkedList
- kevingadd 14y agoHm, I'm super concerned about performance! I know, I'll turn every function call into a virtual function call!
- ComputerGuru 14y agoDon't be silly, the principle is sound. #ifdef _DEBUG typedef BasicLinkedList LinkedList #else typedef XorLinkedList LinkedList #endif
- aggftw 14y agoExcept this is not about performance, but memory.
- hythloday 14y agoYou'd implement it either with a policy-based class[0] or a CRTP compile-time virtual dispatch[1]. There's zero need to involve vtables in this. [0] http://en.wikipedia.org/wiki/Policy-based_design [1] http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern#Static_polymorphism
- mason55 14y agoLinkedList<Element> 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(); //???
- xsmasher 14y agoI don't understand your comment - are you saying "ele" doesn't have enough info to find the next node? You need an Iterator type that has the address of the previous and current nodes, in addition to your existing node / Element type. LinkedList<Element> list = new XORLinkedList(Collections.fromArray(arrayList)); Iterator<Element> 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
- xsmasher 14y agoXORLinkedList is most assuredly harder to debug then BasicLinkedList. Don't do it unless you hafta. In fact don't implement your own linked list at all, unless you have a specialized scenario that needs it (as proven by profiling).