Search code examples
javaobjectlinked-listnodes

Does each node in linked list occupy same amount of space?

I know that each node in a linkedlist is composed of val and next nodes. My intuition is that the head will occupy more space than tail. Since the head has reference to its next node which also has the reference to its next node and so on, while tail's next is null. Or do all the nodes in the list occupy the same amount of space?

Solution

  • Every node in a linkedlist will occupy the same amount of memory. If we define a Node in a linkedlist as follows:

    class Node{
   int val;
   Node next;
}

    Recognize that, apart from the data, each node only contains a reference to the node that comes after it. Even the head node only contains a reference to node that comes after it in sequence. You can traverse the entire list by iterating over the next nodes by starting at the head however each node contains a fixed amount of data (The data it houses and the reference to its neighbor). If the size of the datatype stored in each node is fixed then each node will be the same size.