Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 75

3.3 Building a Linked List: Adding a New Item at the Tail
Consider the problem of building a linked list of positive integers in the order in which they are given. Say the
incoming numbers are as follows ( 0 terminates the data):

36 15 52 23 0

We want to build the following linked list:

top

36 15 52 23

One question that arises is, how many nodes will there be in the list? This, of course, depends on how many
numbers are supplied. One disadvantage of using an array for storing a linear list is that the size of the array must be
specified beforehand. If, when the program is run, it finds that it needs to store more items than this size allows, it may
have to be aborted.
With the linked list approach, whenever a new node must be added to the list, storage is allocated for the node,
and the appropriate pointers are set. Thus, we allocate just the right amount of storage for the list—no more, no less.
We do use extra storage for the pointers, but this is more than compensated for by more efficient use of storage
as well as easy insertions and deletions. Allocating storage “as needed” is usually referred to as dynamic storage
allocation . (On the other hand, array storage is referred to as static storage.)
In our solution to building the list as described earlier, we start with an empty list. Our program will reflect this
with the following statement:

top = null;

When we read a new number, we must do the following:

• Allocate storage for a node

• Put the number in the new node

•
Using our Node class from Section 3.1, let's write a constructor which, given an integer argument, sets num to the
integer and sets next to null .

Make the new node the last one in the list

public Node(int n) {
num = n;
next = null;
}

Consider the following statement:

Node p = new Node(36);

First, storage for a new node is allocated. Assuming an int occupies 4 bytes and a pointer occupies 4 bytes, the
size of Node is 8 bytes. So, 8 bytes are allocated starting at address 4000 , say. 36 is stored in the num field, and null is
stored in the next field, like this:

next

num
36

4000