Is it odd if Nodes in a LinkedList held references to the List object?

Question

Its like, I want to call .moveToBefore(Node) on a Node object and have the node relocate to before the node passed in.

The problem arises if the node passed in is the head node. The List object will still reffer to the old head where as the old head will actually follow the new head further down the chain.

I guess this could be solved easily if the nodes held a reference to the List object. So want to know if there are any disadvantages if the node objects in a Linked List implementation held a reference to its parent "List" object.

Answer 1

The potential problem with the Node class knowing about and using the List class directly is that you create a circular dependency between Node and List.

Circular dependencies can be acceptable if they're carefully contained to ensure you don't accidentally end up making all your classes circularly dependent on each other. This particular example is probably very easy to contain and unlikely to "infect" the rest of your classes, so I wouldn't rule it out as a potentially valid design. But it could still cause problems when maintaining the List itself, since in principle it means you can never change anything on List without checking that you aren't breaking Node in the process. For instance, what if you want to implement the splice operation for your List class? If your Nodes all contain references to the List they're in, then you have to update all of these references, which means slightly more complicated code, and the splice would end up taking O(n) instead of O(1) time. And, if you weren't consciously aware of the circular dependency, you might not have even realized you had to update those references (just imagine the kinds of bugs that would lead to).

For that reason, I would default to List.moveBefore(node1, node2) unless I had some compelling reason to put that method on the Node class instead. But if you do have such a reason, it's okay as long as you keep in mind that you can no longer make any changes to List or Node without checking both class' implementations for things that might break.

Answer 2

The obvious disadvantage would be that a node cannot belong to more than one list. The fact that nodes can belong to more than one list is typically critical in the implementation of persistent data structures through structural sharing.

So, by making the node know about the list, you pretty much preclude making the list persistent, at least using the currently known techniques for doing so. Whether or not that is a restriction you can live with, depends on your requirements.

Answer 3

To me the biggest problem is:

1. Increasing the size of a list node by an extra pointer (or references) for SLL, 3 for DLL. This might not affect performance that much if you're just sporadically allocating list nodes all over the memory space, since at that point it wouldn't matter much unless the node was just around 64 bytes, e.g., aligned to 64 byte boundaries, and the extra pointer made it over 64 bytes, in which case we would double up our cache misses. If you're using a careful allocation strategy, the smaller the list node, the better for sequential traversal, and one extra pointer might be a huge relative size increase just from the list POV.
2. The biggest real-world benefit of linked lists even in performance-critical areas is often that ability to move nodes from one list to another, split lists into two lists and merge them in constant time, etc. You complexify this part in exchange for simplifying something that isn't that complex.
3. Circular references were mentioned, and that might be a problem in some languages. If it's like C or C++, it would be a backpointer to the list which wouldn't affect collection in any way, the nodes would still be destroyed when requested.

What I recommend is to stop trying to put your linked list implementation into a node. Make a node raw data, a private implementation detail of a list that doesn't bother to provide much logic at all. Your life will generally become a lot easier if you stop trying to split functionality concerns too much between linked structures and their nodes: tree vs. tree node, linked list vs. list node, e.g. Put all the logic into the data structure where you have all the information you need to do everything (both head pointer and node). moveToFront should be a linked list method rather than list node method. With that, there's no more need for a backpointer.

class DataStructure
{
public:
    ...

private:
    struct Node
    {
        // Don't put functionality here except maybe a ctor/dtor at 
        // most if you can avoid it. The distribution of concerns should 
        // this node have functionality will often make things more 
        // complex rather than simpler, and also have you reaching for 
        // backpointers quickly, potentially wanting to waste memory
        // and increase the amount of state to maintain superfluously
        // (more state usually means more potential for bugs) just
        // because we want to put functions into this Node class.
    };
    ...
    Node* head_or_root;
};

Another minor thing worth noting is that there's not really much smarter work that moveToFront can do besides erase and push to front, so it might not be worth having the extra function at all except as a convenience sort of thing.

That is, unless this is unavoidable, where the clients would only have a node that they access from a previously cached, persistent space, e.g., and no access to the linked list. If they do have access to the linked list, then the easiest way is just avoid putting logic into your nodes outright, and make them private, raw data C-style struct type of things.

Even then, you will often make your life easier in this case to simply require clients to store a reference to both node and linked list, instead of always storing a backpointer in a node (which may not be needed by most operations, making us waste memory often in places that don't benefit from this).

Another thing is that since Node models implementation details of a linked list, if you can avoid exposing Node references directly and instead provide some indirect handle to it, like Iterator, it'll reduce the risk of problems.