Java Reference
In-Depth Information
Because arrays are stored in one large contiguous block of memory, we can quickly
locate any particular element of the array. Recall that this ability to quickly jump
around in the array is called random access. The weaknesses of the array approach
are that we can't easily insert values in or remove values from the middle without
shifting other values and we can't easily enlarge the size of the structure without con-
structing a brand-new array with a larger capacity.
The linked list structure has the opposite properties. It is not a random access struc-
ture, so it is not easy to jump around in the structure. It has the kind of sequential
access we associate with a cassette tape. If you are playing a tape and want to skip for-
ward 10 songs, you have to fast forward through the songs. You can't quickly skip to
the position where you want to be on the tape. Linked lists have this property as well.
But where arrays are weak, linked lists are strong. We can quickly insert values in
or delete values from the middle of a linked list without any shifting. It is also easy to
make the list larger or smaller.
Linked lists are composed of individual elements called
nodes
.
Node
A single element of a structure such as a linked list; each node contains one
data value.
A node is like a Lego building block. It looks unimpressive by itself, but once you
put a bunch of them together, it can form an interesting structure.
A basic list node looks like this:
data
18
next
It's an object with two fields: one for storing a single item of data and one for stor-
ing a reference to the next node in the list. To store a list of integer values we'd
declare the node class as follows:
public class ListNode {
public int data;
public ListNode next;
}
This class does not produce a nicely encapsulated object with private fields, but
the technique of using public fields is the usual approach to defining nodes. In the
next section we'll discuss why it is acceptable to avoid encapsulation in this case.
This is a recursive data structure. The
ListNode
class is defined in terms of itself
because it has a field of type
ListNode
. As a result, it is often possible to solve
linked list programming problems more effectively by writing recursive methods, as
described in Chapter 12.
Search WWH ::
Custom Search