Java Reference
In-Depth Information
store the objects, then all objects following the new hire must be moved toward the
end.
Conversely, if an employee leaves the company, the object must be removed, and the
hole in the sequence needs to be closed up by moving all objects that come after it.
Moving a large number of values can involve a substantial amount of processing
time. We would like to structure the data in a way that minimizes this cost.
A linked list consists of a number of nodes, each of which has a reference to the
next node.
Rather than storing the values in an array, a linked list uses a sequence of nodes. Each
node stores a value and a reference to the next node in the sequence (see Figure 1 ).
When you insert a new node into a linked list, only the neighboring node references
need to be updated. The same is true when you remove a node. What's the catch?
Linked lists allow speedy insertion and removal, but element access can be slow.
Adding and removing elements in the middle of a linked list is efficient.
For example, suppose you want to locate the fifth element. You must first traverse the
first four. This is a problem if you need to access the elements in arbitrary order. The
term Ȓrandom accessȓ is used in computer science to describe an access pattern in
which elements are accessed in arbitrary (not necessarily random) order. In contrast,
sequential access visits the elements in sequence. For example, a binary search
requires random access, whereas a linear search requires sequential access.
Visiting the elements of a linked list in sequential order is efficient, but random
access is not.
Of course, if you mostly visit all elements in sequence (for example, to display or
print the elements), the inefficiency of random access is not a problem. You use
linked lists when you are concerned about the efficiency of inserting or removing
elements and you rarely need element access in random order.
666
Search WWH ::




Custom Search