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

tmp = new ListNode( x, current.next ); // Create new node
current.next = tmp; // a's next node is x

We now see that tmp is no longer necessary. Thus we have the one-liner

current.next = new ListNode( x, current.next );

The remove command can be executed in one link change. Figure 17.3
shows that to remove item x from the linked list, we set current to be the node
prior to x and then have current 's next link bypass x . This operation is
expressed by the statement

Removal can be
accomplished by
bypassing the
node. We need a
reference to the
node prior to the
one we want to
remove.

current.next = current.next.next;

The list . . . a , x , b , . . . now appears as . . . a , b , . . . .

The preceding discussion summarizes the basics of inserting and remov-
ing items at arbitrary places in a linked list. The fundamental property of a
linked list is that changes to it can be made by using only a constant number
of data movements, which is a great improvement over an array implementa-
tion. Maintaining contiguousness in an array means that whenever an item is
added or deleted, all items that follow it in the list must move.

Linked list opera-
tions use only a
constant number of
data movements.

17.1.1 header nodes

There is one problem with the basic description: It assumes that whenever an
item x is removed, some previous item is always present to allow a bypass.
Consequently, removal of the first item in the linked list becomes a special
case. Similarly, the insert routine does not allow us to insert an item to be the
new first element in the list. The reason is that insertions must follow some
existing item. So, although the basic algorithm works fine, some annoying
special cases must be dealt with.
Special cases are always problematic in algorithm design and frequently
lead to bugs in the code. Consequently, writing code that avoids special cases
is generally preferable. One way to do that is to introduce a header node.
A header node is an extra node in a linked list that holds no data but
serves to satisfy the requirement that every node containing an item have a

figure 17.3
Deletion from a
linked list

a x b

... ...

current