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

x [1] is the first node
x [n] is the last node
if 1 < k <= n, then x [ k ] is preceded by x [ k - 1]
if 1 <= k < n then x [ k ] is followed by x [ k + 1]

Thus, given a node, the “next” node is assumed to be in the next location, if any, in the array. The order of the
nodes is the order in which they appear in the array, starting from the first. Consider the problem of inserting a new
node between two existing nodes, x [ k ] and x [ k + 1].
This can be done only if x [ k + 1] and the nodes after it are moved to make room for the new node. Similarly, the
deletion of x [ k ] involves the movement of the nodes x [ k +1], x [ k + 2], and so on. Accessing any given node is easy;
all we have to do is provide the appropriate subscript.
In many situations, we use an array for representing a linear list. But we can also represent such a list by using an
organization in which each node in the list points explicitly to the next node. This new organization is referred to as a
linked list .
In a (singly) linked list, each node contains a pointer that points to the next node in the list. We can think of each
node as a cell with two components, like this:

next

data

The data item can actually be one or more fields (depending on what needs to be stored in a node), and next
“points to” the next node of the list. (You can use any names you want, instead of data and next .)
Since the next field of the last node does not point to anything, we must set it to a special value called the null
pointer . In Java, the null pointer value is denoted by null .
In addition to the cells of the list, we need an object variable ( top , say) that “points to” the first item in the list.
If the list is empty, the value of top is null .
Pictorially, we represent a linked list as shown in Figure 3-1 .

top

Figure 3-1. A linked list

The electrical earth symbol is used to represent the null pointer.

Traversing a linked list is like going on a treasure hunt. You are told where the first item is. This is what top does.
When you get to the first item, it directs you to where the second item is (this is the purpose of next ). When you get to
the second item, it tells you where the third item is (via next ), and so on. When you get to the last item, its null pointer
tells you that that is the end of the hunt (the end of the list).
How can we represent a linked list in a Java program? Since each node consists of at least two fields, we will need
to use a class to define the format of a node. The data component can consist of one or more fields (each of which
can itself be an object with many fields). The type of these fields will depend on what kind of data needs to be stored.
But what is the type of the next field? We know it's a pointer but a pointer to what? It's a pointer to an object that
is just like the one being defined! This is usually called a self-referencing structure. As an example, suppose the data at
each node is a positive integer. We can define the class from which nodes will be created as follows (using num instead
of data ):