1.5.1 List Nodes1.5 Dynamic Data Structures1.5 Dynamic Data Structures1.5.2 List Type

1.5.1 List Nodes

A linked list consists of  nodes each of which holds

Figure 2 illustrates such a list of linked nodes.


Linked

Linked List
 


The following declaration introduces a corresponding Java class Node: 

  class Node
  {
    int value;
    Node next;
    Node(int value)
    {
      this.value = value;
    }
    Node(int value, Node next)
    {
      this(value);
      this.next = next;
    }
  }

This class has an object field value carrying the information value

A node value may be of any type.
(here of type int) and an object field next which represents the link to the next node. The first constructor initializes the value field to a given value; the link is automatically initialized to null. The second constructor initializes both the value and the link of the node. For sake of brevity, we do not introduce methods for returning or updating the
Don't do this in real programs.
content of the value field but will directly access the object field.

A list is just a (reference to a) node. Consequently, a  singleton list [1], i.e., a list with a single node holding the value 1 can be declared as

  Node one = new Node(1);

Here one is a reference to the list node (which itself contains a null reference). We can retrieve its value by the object field one.value.

The list [2,1] can be now created by creating a new node holding the value 2 and linking it with the list [1], i.e.,

  Node two = new Node(2, one);

We can retrieve the value of the first node as two.value and the content of the second node as two.next.value.

Why?

Consequently, the list [3,2,1] can be created as

  Node three = new Node(3, two);

We can retrieve the values of the list as three.value, three.next.value, and three.next.next.value.

What happens if we access three.next.next.next. value?
We then have the situation depicted in the following picture:

List with 3 Nodes

We see that list three consists of three linked nodes; however, we also see that different lists may have overlapping nodes, for instance, the second node of three is also the first node of two. Updating the content of this node as
  two.value = -2;

has the effect that the statement

  System.out.println(three.next.value);

gives output

  -2.

Dynamic data structures may have shared contents.
The possibility of having multiple references to a list node gives a lot of flexibility but it can be also a source of errors. When dealing with dynamic data structures, one has to take care that not unwanted side effects occur by updating a data structure that is also shared with other structures.
© Wolfgang Schreiner; February 3, 2005

1.5.1 List Nodes1.5 Dynamic Data Structures1.5 Dynamic Data Structures1.5.2 List Type