Linked lists - Data Structures and Problem Solving Using Java - page 646

Finally, remove is shown at lines 36-48. After the obligatory error checks,
we use the LinkedList remove method to remove the lastVisited node. The
explicit reference to the outer class is required because the iterator remove
hides the list remove . After making lastVisited null , to disallow a second
remove , we check whether the last operation was a next or previous . In the latter
case, we adjust current , as shown on line 46, to its state prior to the previous /
remove combination.
All in all, there is a large amount of code, but it simply embellishes the
basics presented in the original implementation of the nonstandard LinkedList
class in Section 17.2.
summary
In this chapter we described why and how linked lists are implemented, illus-
trating the interactions among the list, iterator, and node classes. We exam-
ined variations of the linked list including doubly linked lists. The doubly
linked list allows bidirectional traversal of the list. We also showed how a
sorted linked list class can easily be derived from the basic linked list class.
Finally, we provided an implementation of most of the Collections API
LinkedList class.
key concepts
circularly linked list A linked list in which the last cell's next link references
first . This action is useful when wraparound matters. (633)
doubly linked list A linked list that allows bidirectional traversal by storing
two links per node. (630)
header node An extra node in a linked list that holds no data but serves to sat-
isfy the requirement that every node have a previous node. A header node
allows us to avoid special cases such as the insertion of a new first ele-
ment and the removal of the first element. (621)
iterator class A class that maintains a current position in a container, such as a
list. An iterator class is usually in the same package as, or an inner class
of, a list class. (623)
sorted linked list A list in which items are in sorted order. A sorted linked list
class can be derived from a list class. (633)