0

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?

beastlyCoder
  • 2,349
  • 4
  • 25
  • 52
luw
  • 207
  • 3
  • 14
  • 2
    I think you need to read what reference is and how it is represented in memory – mangusta Jun 26 '20 at 03:20
  • 1
    A reference takes up the same fixed amount of space whether it references some actual object or no object at all (i.e., is `null`). Unless, of course, you count the space taken by the referenced object itself as part of the space taken by a non-null reference (which, personally, _I_ don't...) – Kevin Anderson Jun 26 '20 at 03:31
  • In java, the nodes in a linked list will be fixed in size. In some other languages, the nodes can have different sizes, such as a node structure in C with a [flexible array member](https://en.wikipedia.org/wiki/Flexible_array_member) , – rcgldr Jun 27 '20 at 07:14

1 Answers1

2

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.

pingOfDoom
  • 408
  • 1
  • 4
  • 21