Is there significant overhead for this particular inner non-static class?

Question

I am writing my own implementation of a doubly linked list for school assignment and I use an inner node class called Node inside the list class, which represents list nodes that are linked to each other (as is usually the case with linked lists).

class DoublyLinkedList<T>
{
    class Node
    {
        T obj;
    }
}

I wonder, for large lists with many nodes, since each Node object may refer to an instance of the parent list class, is it a significant overhead and suboptimal design? It surely is convenient to have as a non-static class - then the nodes may alter parent lists first and last references, which I have found to be great for incapsulation.

If I make Node static, it can no longer (without explicit member reference to the list) be used to manipulate the parent lists first and last and I have to approach it all from the other way around - the list will assign and manipulate nodes through its own methods, that is link them to each other, unlink and naturally adjust its first and last values.

For the sake of good design and learning, I would like to know what is The Smart Thing To Do (c) (if any)?

Answer 1

The overhead would be exactly one reference per node. Assuming that the node in addition to the payload also has a prior link and a back link, the overhead for an extra reference to the parent would amount to about 33% in additional memory use (1 reference on top of 3 existing ones). This is considerable overhead, especially for large node counts and small payloads. On the other hand, with larger payloads it would not matter much.

In general, though, I would not make an assumption about the payload size, and make the Node class static.

Answer 2

If the inner class is not static then an implicit reference to the parent class already exists and you can refer to it through DoublyLinkedList.this from inside Node class.

In any case I don't see why a Node class should be able to modify directly attributes of its parent class. Methods that alter the list (so first and last too) should be of DoubleLinkedList class and not directly of Node class. This exactly for encapsulation, a Node instance shouldn't know anything about where it is contained or how it is used from the outside.