Chapter XXXIII

Linked Lists I
Chapter XXXIII Topics
33.1 Introduction
33.2 Review of the LinkedList Class
33.3 Multiple Queue Implementations
33.4 Pre-OOP ListNode Class
33.5 OOP ListNode Class
33.6 Loops and Linked Lists
33.7 Considering Cases
33.8 An Ordered Linked List
33.9 Linked Lists and Memory
33.10 The GfxNode Class
33.11 Practice Exercises
33.12 Summary

Chapter XXXIII Linked Lists I 33.1

33.1 Introduction

The Linked list must be an important data structure. You are looking at a chapter
titled Linked List I, which will be immediately followed by Linked List II. Any
topic that gets two chapters exclusively devoted to itself must be a big deal. Yes,
linked lists are very powerful, very flexible and thus very important. Why the big
emphasis on linked lists? Let us investigate the array data structure and see any
potential weaknesses that must be addressed.

We can start with the static array. A Java static array allocates memory once and
the array is stuck with its selected memory block size. If the array is too small, it
is too bad, because you will run out of space to add any additional elements. If
the array is too big, you can add all the elements that you desire, but this is done
at a considerable penalty in using memory space. Look at a multiplex movie
theater and you will see sixteen theaters of varying sizes to fit the demand of a
particular movie. Imagine that it is a requirement that all theaters are the same
size, which is the case with a static array. If you select sixteen small theaters, you
will efficiently handle small crowds for unpopular movies and simultaneously
display sold out signs for new blockbuster movies. You may be concerned about
turning away customers, so you decide to build sixteen large theaters. Now you
can handle any crowd, but you are paying for the construction and air-
conditioning of huge theaters that are almost empty for many movies. It should
make sense that the multi-size theater is the best solution for a multiplex theater
situation.

This is a great solution, but the Java static array allows no such option. You
decide on the number of array elements and there are no changes allowed after
the array object is constructed. Good, bad or just right, you are stuck with your
size decision. I know that many of you clever students already know the solution.
Forget the Java static array and switch over to ArrayList, which is Java's own
solution to allow dynamic resizing during program execution.

This is an excellent idea and yes it is possible to create an ArrayList object and
then happily and merrily alters its size as demands increase or decrease. It seems
like a perfect solution. Why even ponder over any other possibilities? Frankly
you are not totally out off the woods with the use of ArrayList, which will make
sense if you understand the manner in which ArrayList handles its resizing
needs.

I will tell you a secret. The ArrayList object is not really doing much resizing.
Every object is a contiguous block in memory. If more space is needed, then a
new block is allocated, data is transferred from the old block to the new block and
the old block is returned to memory. In other words, there is a considerable
amount of processing that is happening in the background to make resizing

33.2 Exposure Java, 2008 Edition 07-26-08

possible. This process can be a healthy penalty in process time. If an object
exists that stores a large number of record elements, with each record already
taking up considerable memory, then the transfer of all these records becomes
process intensive. Given a large enough data structure, combined with frequent
resizing, and there could be problems. Is such a scenario realistic? Think about a
large growing company with many employees. Massive data is stored for each
employee to handle its payroll, health insurance, retirement plans, etc. needs.
Now this growing company is adding new employees daily and the data structure
to store this information is constantly resizing, if all the data is stored in an
ArrayList object.

ArrayList Warning

Java's ArrayList class allows dynamic resizing during program

execution. An ArrayList object may have some extra capacity
for additional new elements.

If the capacity is not sufficient to allow adding new elements, a

new block of memory is allocated, data is shifted from the old
block to the new block, and the old block is returned to available
memory for future use.

This process can take considerable execution penalty, if the

array has many elements, each storing large quantities of data.

It is precisely for the situations where execution processes become noticeable that
the linked list data structure takes front center and offers a solution. Forget the
requirement to store all the data in one contiguous block. This can be slow and
worse, it can even be impossible if too large a block is requested. Your program
needs to store and process lots of data and you care little how and where this data
is stored. The computer has chunks of memory all over the place. There is no
problem storing elements in many separate blocks if there is some way to connect
these blocks. You may guess where this is going? Blocks of information are
connected with links and the linked list data structure is born. In this chapter we
will start by reviewing the Java LinkedList class. The LinkedList class was
introduced with the other Collection classes along with a brief introduction to
linked lists. The power, flexibility and capabilities of a linked list were not
explored in the Collection chapter. This chapter and the next chapter will emerge
you in the virtues of the linked list data structure and truth be told, you may soon
find yourself overly emerged. You will learn that the Java LinkedList class is
nice, but it has limitations.

Chapter XXXIII Linked Lists I 33.3

After a review of the available features of the LinkedList class you will learn
how to implement your very own linked list data structure with far greater
capabilities than you will find with the provide LinkedList class.

33.2 Review of the LinkedList Class

The LinkedList class has access to various methods that start with the Collection
interface and continues with the List subinterface. These methods allow adding
new elements, checking for membership, removing elements and altering
elements. It is possible with the add method and the set method to specify a
specific index of an object for access. This makes perfect sense for an ArrayList
object, but a LinkedList object has access to the same methods and it makes for
a slightly peculiar LinkedList implementation. Normally, we do not think about
indexed access with a linked list data structure. Therefore this section will focus
on the methods that are unique to the LinkedList class. These methods allow
access to the first node or the last node of the data structure, which is a traditional
access of a linked list data structure. Program Java3301.java, in figure 33.1,
reviews the addFirst, addLast, getFirst and getLast methods.

Figure 33.1
// Java3301.java
// This program reviews the <LinkedList> class with methods <addFirst>, <addLast>, <getFirst> and <getLast>.

import java.util.LinkedList;

public class Java3301

{
public static void main(String args[])
{
System.out.println("JAVA3301.JAVA\n");
LinkedList family = new LinkedList();
family.addFirst("John");
family.addLast("Greg");
family.addLast("Maria");
family.addLast("Heidi");
System.out.println(family.getFirst());
System.out.println(family.getLast());
System.out.println();
System.out.println("family: " + family);
System.out.println();
}
}

33.4 Exposure Java, 2008 Edition 07-26-08

Figure 33.1 continued
Java3301.java Output
JAVA3301.JAVA

John
Heidi

[family: John, Greg, Maria, Heidi]

Do remember that courtesy of some toString redefinition, it is possible to display

the contents of any Collection class with print or println. Program
Java3301.java demonstrates access to the first and last nodes, but it does not
explain how to provide access to any other nodes. There are various approaches
and program Java3302.java, in figure 33.2, uses a simplistic approach with the
removeFirst method. If access is possible at either end than the removal of a
node provides access to the next node in line, which becomes an end node after
the removal of its predecessor.

Figure 33.2
// Java3302.java
// This program creates a linked list with four nodes and displays each node
// starting with the first node to the last node using the <getFirst> and <removeFirst> methods.

import java.util.LinkedList;

public class Java3302

{
public static void main(String args[])
{
System.out.println("JAVA3302.JAVA\n");
LinkedList family = new LinkedList();
family.addFirst("John");
family.addLast("Greg");
family.addLast("Maria");
family.addLast("Heidi");
for (int k = 1; k <= 4; k++)
{
System.out.println(family.getFirst());
family.removeFirst();
}
System.out.println();
}
}

Java3302.java Output

JAVA3302.JAVA

John
Greg
Maria
Heidi

Chapter XXXIII Linked Lists I 33.5

Node removal is not limited to the front of the linked list. It is also possible to
access the end of the linked list with the getLast and removeLast nodes.
Program Java3303.java, in figure 33.3, performs the same goals as the previous
program, but access now is provided at the end of the list, which results in a
reverse display of the names.

Figure 33.3
// Java3303.java
// This program creates a linked list with four nodes and displays each node
// starting with the last node to the first node using the <getLast> and
// <removeLast> methods.

import java.util.LinkedList;

public class Java3303

{
public static void main(String args[])
{
System.out.println("JAVA3303.JAVA\n");
LinkedList family = new LinkedList();
family.addFirst("John");
family.addLast("Greg");
family.addLast("Maria");
family.addLast("Heidi");
for (int k = 1; k <= 4; k++)
{
System.out.println(family.getLast());
family.removeLast( );
}
System.out.println();
}
}

Java3303.java Output

JAVA3303.JAVA

Heidi
Maria
Greg
John

LinkedList class method addFirst

data.addFirst(value);

Method addFirst inserts the new element value to the front of

the list.

33.6 Exposure Java, 2008 Edition 07-26-08

LinkedList class method addLast

data.addLast(value);

Method addLast inserts the new element value to the back of

the list.

LinkedList class method getFirst

String name = (String) data.getFirst();

Method getFirst returns the element at the front of the list.

LinkedList class method getLast

String name = (String) data.getLast();

Method getLast returns the element at the back of the list.

LinkedList class method removeFirst

String name = (String) data.removeFirst();

Method removeFirst returns, and removes, the element from

the front of the list.

LinkedList class method removeLast

Chapter XXXIII Linked Lists I 33.7

String name = (String) data.removeLast();

Method removeLast returns, and removes, the element from

the back of the list.

You have seen two approaches to display the elements of a linked list and frankly,
both methods are quite sad. Anytime you destroy a structure to see its contents,
you are looking at a poorly designed program segment. Imagine that you wish to
determine every student in your school by lining the students up and recording
their names as you kick them out off school, just to have access to the next person
in line. A little strange, is it not?

Well not to worry, because Java has these nifty Iterator and ListIterator classes.
The ListIterator class has the methods available in the Iterator class and then
adds some special methods to make linked list processing simpler. The next two
programs use the ListIterator class, but you could substitute the Iterator class
and get the same result. A later program will demonstrate some unique
ListIterator methods. Program Java3304.java, in figure 33.4, demonstrates the
use of the next method.

Everything presented in this section is a review. All these Iterator and

ListIterator methods were already introduced in chapter 31. The true focus of
this chapter will be on the implementations and use of linked list classes that are
not provided by the Java standard libraries. However, it makes sense to start by
looking what is already available in the Java bag of tricks before we start to create
our own tools.

Keep in mind that iterator is a noun created from the verb iterate, which means to
repeat. This makes iterator a repeater. Picture an iterator as an office aid who
has to deliver messages to different rooms. The iterator stands in front of the first
room and waits. A command is issued to the information stored in that room.
Now here is the key to this business. The iterator is not in charge of information
display. It just stands in front of the room that may require processing. The next
method processes the program statement for the immediate room and then moves
on to the next room. In truth next is a return method, which returns information
in the room.

Figure 33.4
// Java3304.java

33.8 Exposure Java, 2008 Edition 07-26-08

// This program demonstrates how to traverse a linked list using the <next>
// method of the <ListIterator> class.

import java.util.LinkedList;
import java.util.ListIterator;

public class Java3304

{
public static void main(String args[])
{
System.out.println("JAVA3304.JAVA\n");
LinkedList family = new LinkedList();

family.addFirst("John");
family.addLast("Greg");
family.addLast("Maria");
family.addLast("Heidi");

ListIterator iter = family.listIterator();

for (int k = 1; k <= 4; k++)
System.out.println(iter.next());
System.out.println();
}
}

Java3304.java Output

JAVA3304.JAVA

John
Greg
Maria
Heidi

Constructing a ListIterator Object

LinkedList family = new LinkedList();

ListIterator iter = family.listIterator();

The listIterator method of the LinkedList class instantiates an

iter object of the ListIterator class.

ListIterator Method next

Chapter XXXIII Linked Lists I 33.9

 System.out.print(iter.next() + " ");

Method next moves the iterator to the next element, and then
returns it.

Program Java3304.java takes the attitude that somehow the number of nodes in
the linked list is known. This is hardly logical. The whole point of using a linked
list is for the efficient convenience of constantly changing the size of the data
structure during program execution. This means that a fixed loop makes no sense
with a linked list. Program Java3305.java, in figure 33.5, uses the practical
hasNext method in a conditional loop. Iteration continues as long as hasNext is
true. This is really the only sensible way to work with linked lists.

Figure 33.5
// Java3305.java
// This program demonstrates how to traverse a linked list until the
// end is found, using the <hasNext> method.

import java.util.LinkedList;
import java.util.ListIterator;

public class Java3305

{
public static void main(String args[])
{
System.out.println("JAVA3305.JAVA\n");
LinkedList family = new LinkedList();

family.addFirst("John");
family.addLast("Greg");
family.addLast("Maria");
family.addLast("Heidi");

ListIterator iter = family.listIterator();

while (iter.hasNext())
System.out.println(iter.next());
System.out.println();
}
}

33.10 Exposure Java, 2008 Edition 07-26-08

Figure 33.5 continued
Java3305.java Output

JAVA3305.JAVA

John
Greg
Maria
Heidi

ListIterator Method hasNext

while (iter.hasNext())

Method hasNext returns true if an element remains in the

Collection object and returns false otherwise.

The remove method of the Iterator and ListIterator classes was not shown in
any review program. Method remove is detailed in a highlight window to make
the method review section complete.

ListIterator Method remove

iter.remove();

Method remove removes the current item pointed to by the

ListIterator.

Program Java3306.java, in figure 33.6, reviews the add and set methods. Be
careful with this program example, because you may get fooled. You already
know the add method. It is one of the Collection methods, which adds new
elements to a Collection object. Do not get confused because there is quite a
difference between list.add("Name"); and iter.add("Name");. The first add is
called by the list object and the second add method is called by the iter object.
Same method identifier, but they come from two totally different classes.

Chapter XXXIII Linked Lists I 33.11

Method add in the ListIterator class inserts a new element in front of the
element returned by the next call. Method set replaces the last element value
returned by method next with the provided argument.

Figure 33.6
// Java3306.java
// This program demonstrates how to use the <ListIterator> class to access
// elements in a <LinkedList> object. The <ListIterator> adds the <add>
// and <set> method to the three <Iterator> methods.

import java.util.*;

public class Java3306

{
public static void main(String args[])
{
System.out.println("\nJAVA3306.JAVA\n");
LinkedList list = new LinkedList();

for (int k = 1000; k <= 5000; k+= 1000)

list.add(new Integer(k));
System.out.println(list);
System.out.println();

ListIterator iter = list.listIterator();

while (iter.hasNext())
{
iter.next();
iter.set(new Integer(9999));
iter.add(new Integer(1111));
}
System.out.println(list);
System.out.println();
}
}

Java3306.java Output

JAVA3306.JAVA

[1000, 2000, 3000, 4000, 5000]

[9999, 1111, 9999, 1111, 9999, 1111, 9999, 1111, 9999, 1111]

ListIterator Method add

33.12 Exposure Java, 2008 Edition 07-26-08

 iter.add(new Integer(1111));

Method add inserts a new element between the current item

pointed to by the ListIterator and the next element.

ListIterator Method set

iter.set(new Integer(9999));

Method set replaces the current item pointed to by the

Listiterator with the provided argument.

33.3 Multiple Queue Implementations

Several chapters back you learned how to implement a queue data structure. The
choices at that stage were limited. We wanted to use some type of dynamic
structure that would grow and shrink with calls to enQueue and deQueue. The
choice was pretty much limited to ArrayList, since it was the only dynamic data
structure in our programming tool bag. The ArrayList class did an outstanding
job for us and we were very pleased with our queue implementation. Program
Java3307.java, in figure 33.7, reviews the queue implementation with the help of
an ArrayList object.

Figure 33.7
// Java3307.java
// This program reviews implementing a queue with the <ArrayList> class.

import java.util.ArrayList;

public class Java3307

{
public static void main (String args[])

Chapter XXXIII Linked Lists I 33.13

 {
System.out.println("JAVA3307.JAVA\n");
MyQueue students = new MyQueue();

students.enQueue("Luke Watts");
students.enQueue("Brian Sims");
students.enQueue("Mike Lewis");
students.enQueue("Jamie Singbush");
System.out.println("There are " + students.getSize() + " students stored on the queue");
System.out.println();

if (students.isEmpty())
System.out.println("The queue is empty");
else
System.out.println("Queue front contains " + students.peekFront());
System.out.println();

while (!students.isEmpty())
{
String student = (String) students.deQueue();
System.out.println(student);
}
System.out.println();

}
}

class MyQueue
{

private ArrayList data; // stores queue data

private final int front; // keeps index of the queue front

public MyQueue()
// Initializes an empty array object with references of private variable data objects.
{
data = new ArrayList();
front = 0;
}

public boolean isEmpty()

// Returns true if data is empty, false otherwise
{
return data.size() == 0;
}

public void enQueue (Object x)

// Adds variable x to the back of the queue
{
data.add(x);
}

public Object deQueue()

// Returns and removes the front element from the queue
{
return data.remove(front);
}

public Object peekFront()

// Returns the front element from the queue without removal
{
return data.get(front);
}

public int getSize()

// returns the number of queue elements
{
return data.size();

33.14 Exposure Java, 2008 Edition 07-26-08

 }
}

Figure 33.7 continued

Java3307.java Output

JAVA3307.JAVA

There are 4 students stored on the queue

Queue front contains Luke Watts

Luke Watts
Brian Sims
Mike Lewis
Jamie Singbush

You have no complaints with the ArrayList implementation. It works, so who

cares about other possible implementations. Well at least Mr. Schram cares and
he wants to make a point about the LinkedList class. The LinkedList class with
its special methods to access to first and last element in a list is an ideal tool to
implement a queue. Program Java3308.java, in figure 33.8, is the same queue
program, but now it is implemented with a MyQueue class that uses the
LinkedList class. Check it out. I hope you will find that the methods are clean
and straightforward and they seem to give a clearer picture about the purpose of
each method because of the program statements that are used.

Each one of the MyQueue methods uses a simple one-line statement. You want
to deQueue? This means you need access the front of the queue, well use
removeFirst. You want to enQueue? That means you need access the end of
the queue, then use addLast. Oh, and if you want only to take a look at the front
element with peekFront, then getFirst is your choice.

It may help to pull the ArrayList implementation of the queue and the
LinkedList implementation into JCreator with two separate vertical windows.
Compare them side-by-side and you may understand better what my point is.
Both implementations do work, but the LinkedList version is shorter, cleaner and
more readable. If such a solution is available, use it.

Figure 33.8
// Java3308.java

Chapter XXXIII Linked Lists I 33.15

// This program demonstrates implementing a queue with the <LinkedList> class.

import java.util.LinkedList;

public class Java3308

{
public static void main (String args[])
{
System.out.println("JAVA3308.JAVA\n");
MyQueue students = new MyQueue();

students.enQueue("Luke Watts");
students.enQueue("Brian Sims");
students.enQueue("Mike Lewis");
students.enQueue("Jamie Singbush");
System.out.println("There are " + students.getSize() + " students stored on the queue");
System.out.println();

if (students.isEmpty())
System.out.println("The queue is empty");
else
System.out.println("Queue front contains " + students.peekFront());
System.out.println();

while (!students.isEmpty())
{
String student = (String) students.deQueue();
System.out.println(student);
}
System.out.println();

}
}

class MyQueue
{

private LinkedList data; // stores queue data

public MyQueue()
// Initializes an empty array object with references of private variable data objects.
{
data = new LinkedList();
}

public boolean isEmpty()

// Returns true if data is empty, false otherwise
{
return data.size() == 0;
}

public void enQueue (Object x)

// Adds variable x to the back of the queue
{
data.addLast(x);
}

public Object deQueue()

// Returns and removes the front element from the queue
{
return data.removeFirst();
}

public Object peekFront()

// Returns the front element from the queue without removal
{
return data.getFirst();

33.16 Exposure Java, 2008 Edition 07-26-08

 }

public int getSize()

// returns the number of queue elements
{
return data.size();
}
}

Figure 33.8 continued

Java3308java Output

JAVA3308JAVA

There are 4 students stored on the queue

Queue front contains Luke Watts

Luke Watts
Brian Sims
Mike Lewis
Jamie Singbush

33.4 Pre-OOP ListNode Class

You will now make a major shift. Forget that you just learned a variety of
LinkedList tricks. Just imagine that there is a need for a linked list data structure
and you need to implement such a structure in some fashion without any special
classes. In other words, there are no shortcuts unless you create them first.

Right now we will not be concerned with complexities of inserting and deleting
nodes in the middle of a linked list. The simplest way to learn about handling
links is to concentrate on linking at one end of a linked list. The end result of
building a list at one end only is that the list behaves like a stack. However, the
motivation is to learn the easiest type of linked list implementation first, and this
just happens to be a stack.

The secret of implementing a linked list revolves around a rather peculiar looking
data structure. Each node in a linked list stores data as well as information about

Chapter XXXIII Linked Lists I 33.17

the next node. A good choice for this “link” is the use of a reference, which
stores the address of the next node in the list.

This brings up a curious problem. Each node in the linked list will then contain a
field, which is a reference to another node. But the pointer is inside the very
structure that it references. The solution is to use a self-referencing declaration
like the one shown in figure 33.9.

Figure 33.9

class ListNode
{
public Object value;
public ListNode next;
}

ListNode is a short, peculiar class with two fields. There are no constructors and
there are no methods in sight. Keep in mind that this is the pre-OOP approach.
The first field, value, stores the necessary data information. The second field,
next, is a reference and notice that this is a reference of the ListNode class.
Normally, it is not possible to make a reference to anything that is not yet
completely declared. This is allowed in the case of making a reference to some
memory location that will be allocated during program execution.

Self-Referenced Data Structure

A linked list data structure is made up of self-referential
objects. If the object is of ListNode type then one - or more -
fields references ListNode, like the example below.

class ListNode
{
public Object value;
public ListNode next;
}

This is the type of stuff that often causes major confusion. The only reason why
this self-referential stuff is included is for multiple reading purposes. After you
look at a variety of program examples that use this type of structure, you will see

33.18 Exposure Java, 2008 Edition 07-26-08

a pattern that will help to explain what is going on. A second or third time passed
over this page will be a whole lot more agreeable than it is the first time.

It is also important to realize that ListNode, value, and next are not special Java
keywords at all. Figure 33.10 shows the exact same functionality with the Tiger
class declaration.

Figure 33.10

class Tiger
{
public Object book;
public Tiger giraffe;
}

The first linked list program example will create a small linked list with only
three nodes. Strings are stored as data in the linked list besides the linking
information. Graphically, the linked list looks like figure 33.11

Figure 33.11
David Greg John

The diagonal line in the picture indicates the null pointer or address. It is used to
indicate the end of the list. null is a reference, but it does not reference any
actual memory address. Its only purpose in life is to help identify the end of a
list. The value of null is zero (0). Program Java3309.java, in figure 33.12
shows the syntax of this first program. Every program statement in this example
will be explained in detail following the program.

Figure 33.12
// Java3309.java
// This program demonstrates creating a linked list in an old-fashioned pre-oop
// style that uses a poorly designed <ListNode> class.

Chapter XXXIII Linked Lists I 33.19

// Note that the <ListNode> class contains only data and no methods at all.

public class Java3309

{

public static void main (String args[])

{
System.out.println("\nJAVA3309.JAVA\n");
ListNode p;
ListNode temp = null;

p = new ListNode();
p.value = "John";
p.next = temp;
temp = p;

p = new ListNode();
p.value = "Greg";
p.next = temp;
temp = p;

p = new ListNode();
p.value = "David";
p.next = temp;
temp = p;

while (p != null)
{
System.out.println(p.value);
p = p.next;
}
System.out.println();
}

class ListNode
{
public Object value;
public ListNode next;
}

Java3309.java Output

JAVA3309.JAVA

David
Greg
John

As you look at the explanation of program Java3309.java, keep in mind that it is

a pre-OOP design. Students who are now one with Object Orient Programming
will get some serious itch. Major design flaws are shown. Encapsulation is

33.20 Exposure Java, 2008 Edition 07-26-08

nowhere in sight. Public data fields are accessed directly without the benefit of a
proper accessing method. Yes, by today's OOP standards this is bad news but I
am showing this for several reasons. First, it does show each one of the steps
involved in creating a linked list nicely. Second, students and teachers who come
from the earlier C++ world will feel a comfort level. They will see that yes, this
looks familiar and just when you feel slightly warm and fuzzy I will pull the rug
from under you and do it the OOP way. The results are the same. The design is
better and the program is more reliable, but it will look radically different.

ListNode p; // # 01
ListNode temp = null; // # 02
Lines 01 and 02 declare two ListNode variables.

p = new ListNode(); // # 03
Line 03 constructs a ListNode object. Data fields do not have any useful values.

p.value = "John"; // # 04
p.next = temp; // # 05
temp = p; // # 06
Line 04 assigns the string "John" to the value data field.
Line 05 assigns temp's value, which is null, to the next data field.
Line 06 assigns p's value to temp. Both p and temp reference the same address.

p = new ListNode(); // # 07
p.value = "Greg"; // # 08
Line 07 uses p to construct another ListNode object.
Line 08 assigns the string "Greg" to the value data field.

p.next = temp; // # 09
temp = p; // # 10
Line 09 is very significant. temp references the first node created and p
references the second node. The next field of p links the two nodes.
After temp secures a link between the two nodes, temp moves to p.

p = new ListNode(); // # 11
p.value = "David"; // # 12
p.next = temp; // # 13
temp = p; // # 14

Chapter XXXIII Linked Lists I 33.21

Lines 11-14 repeat the process to construct and link a third node.
while (p != null) // # 15
{
System.out.println(p.value); // # 16
p = p.next; // # 17
}
Line 15 makes good use of null. The last node in the linked list has its next data
field set to null. When p reaches that last node, the conditional statement
becomes false and the looping stops.
Line 16 prints the data field value of the node that p references.
Line 17 moves the p reference to the next node.

Next Reference Rule

The next data field is one-directional. This linking reference

value is only capable of linking to one other node.

In other words, if Node A links to node B, the two nodes

are linked but it is not possible to traverse from node B
back to node A with the link A B.

33.5 OOP ListNode Class

When you looked at earlier programs that used the LinkedList class, you had
little control over the manner in which the list elements linked together. The last
program, with the pre-OOP ListNode class linked three nodes together in a LIFO
sequence or a stack. It could also have been linked as a FIFO or queue and the
linking could be done such that new nodes are inserted to maintain a certain
desired order. There is a reason for starting with a stack. The LIFO sequence,
which means a single end access, simplifies the processing for any linked
structure. A linked list data structure is not concerned with the arrangements of
its nodes. As long as each node has the ability to access the next node and you
have a means to identify the beginning and end of the list, you are functional.

33.22 Exposure Java, 2008 Edition 07-26-08

You can do some amazing linked list application with the ListNode class, shown
in the previous program, but it was presented for various reasons, mostly for
comparison and historical purposes. It is not meant to set an example of proper
programming design. The wide variety of linked structures will not be shown
with the pre-OOP ListNode class, but it will be shown with the new, improved
and ever so proper ListNode class, shown in figure 33.13. This class comes
complete with a constructor and various accessing methods. This ListNode class
will be used for the rest of program examples in this chapter. How is this new
ListNode class improved? Let's check.

OOP ListNode Improvements

The constructor creates a new node and initializes the attribute

fields. Both the value field and the next field are initialized.
This process used to be three steps. Now it is only one
statement.

The attribute fields are private, and cannot be accessed globally

anymore.

Special get methods are declared to properly get the values of

any ListNode object.

Special set methods are declared to properly alter the values of

any ListNode object.

Figure 33.13
// Proper OOP ListNode class declaration.

class ListNode
{

Chapter XXXIII Linked Lists I 33.23

 public ListNode (Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public Object getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (Object theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private Object value;
private ListNode next;
}

It is easier to understand the nature of the new ListNode class, when it is used in
a program example. Program Java3310.java, in figure 33.14, uses the new class
and links four nodes in a stack sequence, and then displays the stored names.

Figure 33.14
// Java3310.java
// This program demonstrates how to create a linked list of four nodes with
// a well-designed <ListNode> class. This linked list behaves like a stack.

public class Java3310

{

public static void main (String args[])

{
System.out.println("\nJAVA3310.JAVA\n");

ListNode p = null;
ListNode temp = null;

System.out.println("Constructing a node with Isolde");

p = new ListNode("Isolde",temp);
temp = p;

System.out.println("Constructing a node with Maria");

p = new ListNode("Maria",temp);
temp = p;

System.out.println("Constructing a node with Heidi");

p = new ListNode("Heidi",temp);
temp = p;

System.out.println("Constructing a node with Diana\n");

p = new ListNode("Diana",temp);
temp = p;

while (p != null)
{
System.out.println(p.getValue());
p = p.getNext();
}

33.24 Exposure Java, 2008 Edition 07-26-08

 System.out.println();
}

class ListNode
{
public ListNode (Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public Object getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (Object theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private Object value;
private ListNode next;
}

Figure 33.14 continued

Java3310.java Output

JAVA3310.JAVA

Constructing a node with Isolde

Constructing a node with Maria
Constructing a node with Heidi
Constructing a node with Diana

Diana
Heidi
Maria
Isolde

How does the new class manage to perform the same linked processes as its
predecessor? Compare the program statements of the last two programs. You will
see that the same exact steps that were shown in the previous program are present
here. The key difference is that several statements of the pre-OOP style are now
consolidated in a single program statement.

ListNode p = null; // # 1
ListNode temp = null; // # 2
Lines 01 and 02 declare two ListNode variables.
So far this is identical to the previous program

Chapter XXXIII Linked Lists I 33.25

 System.out.println("Constructing a node with Isolde"); // # 3
p = new ListNode("Isolde",temp); // # 4
temp = p; // # 5
Line 3 is an output statement to indicate the node under construction.
Line 4 constructs a new node, places the string "Isolde" in the value field and
links the node to temp, which for now is null.
Line 5 makes temp and p both reference the same new node.

System.out.println("Constructing a node with Maria"); // # 6

p = new ListNode("Maria",temp); // # 7
temp = p; // # 8
Line 6 is an output statement to indicate the node under construction.
Line 7 constructs a new node, places the string "Maria" in the value field and
links the node to temp, which links the current node to the previous node.
Line 8 makes temp and p both reference the same new node.

Is it much tougher to create a linked list that is sequenced as a FIFO queue? It is

not much harder, but it is slightly more involved. Program Java3311.java, in
figure 33.15, takes our new ListNode class and uses the class to link nodes
together in a queue sequence.

You should observe that more variables are used and also more program
statements. A stack builds new nodes at the same location where the stack
removes elements. A queue builds new nodes at one end and removes nodes at
another end. This type of structure will require an additional reference that keeps
track of the front of the list for node removal.

Figure 33.15
// Java3311.java
// This program demonstrates how to create a linked list of four nodes with
// a well-designed <ListNode> class. This linked list behaves like a queue.

public class Java3311

{

public static void main (String args[])

{
System.out.println("\nJAVA3311.JAVA\n");

ListNode p = null;
ListNode front = null;
ListNode temp = null;

System.out.println("Constructing a node with Isolde");

p = new ListNode("Isolde",null);
front = p;
temp = p;

33.26 Exposure Java, 2008 Edition 07-26-08

 System.out.println("Constructing a node with Maria");
p = new ListNode("Maria",null);
temp.setNext(p);
temp = p;

System.out.println("Constructing a node with Heidi");

p = new ListNode("Heidi",null);
temp.setNext(p);
temp = p;

System.out.println("Constructing a node with Diana\n");

p = new ListNode("Diana",null);
temp.setNext(p);
temp = p;

p = front;
while (p != null)
{
System.out.println(p.getValue());
p = p.getNext();
}
System.out.println();
}

class ListNode
{
public ListNode (Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public Object getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (Object theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private Object value;
private ListNode next;
}

Figure 33.15 continued

Java3311.java Output
JAVA3311.JAVA

Constructing a node with Isolde

Constructing a node with Maria
Constructing a node with Heidi
Constructing a node with Diana

Isolde
Maria
Heidi
Diana

It is really important to understand why two nodes link as a stack and why the
same nodes also manage to link as a queue. Two sets of statements will be shown
in figure 33.16, to help clarify the difference.

Chapter XXXIII Linked Lists I 33.27

Figure 33.16
Stack Linking Queue Linking

p = new ListNode("Isolde",temp); p = new ListNode("Isolde",null);

// Creates a new node with "Isolde" data. // Creates a new node with "Isolde" data.
// Links new node to temp, which is null. // Links new node to null.
temp = p; front = p;
// Assigns temp to the new node. temp = p;
// Assigns both front and temp to
// the new node.

p = new ListNode("Maria",temp); p = new ListNode("Maria",null);

// Creates a new node with "Maria" data. // Creates a new node with "Maria" data.
// Links new node to temp, which is the first // Links new node to null.
node. temp.setNext(p);
temp = p; // Links previous node to the new node.
// Moves temp to the new node. temp = p;
// Moves temp to the new node.

Figure shows the creation of a linked list with three nodes. Two linked lists are
shown and each one has a sequence of three characters, [ X, Y, Z] stored in the
data field. Notice the difference in the linking arrows.

Figure 33.17

X Y Z [top] (stack)

(queue) [front] X Y Z

33.6 Loops and Linked Lists

The number of statements required to construct, and link a node in a linked list, is
not very excessive. If the sequence needs to be a queue there will be some extra

33.28 Exposure Java, 2008 Edition 07-26-08

statements, but still the number of program statements seems reasonable.
Reasonable, perhaps because the program examples involved uses only three or
four nodes. Linked list programs will rapidly become tedious if the list contains
1000 or more nodes and three statements are needed per node. Surely, you have
noticed a pattern, such that each new node uses the same kind of statements. The
main difference is that each node stores some different value.

In the case of a stack there are only two statements required. The first statement
constructs a node, enters information for the data field and assigns a value to the
linking field so that it connects to the previous node. Any extra nodes will follow
this same pattern. Program Java3312.java, in figure 33.18, uses a fixed loop to
enter a set of integers in a linked list. Note that two ListNode variables are
declared prior to the loop structure.

Figure 33.18
// Java3312.java
// This program demonstrates how to create a linked list of integers.
// The linked list is created like a stack.

public class Java3312

{

public static void main (String args[])

{
System.out.println("\nJAVA3312.JAVA\n");

ListNode p = null;
ListNode temp = null;

for (int k = 100; k < 110; k++)

{
System.out.println("Constructing a node with " + k);
p = new ListNode(new Integer(k),temp);
temp = p;
}
System.out.println();

while (p != null)
{
System.out.print(p.getValue() + " ");
p = p.getNext();
}
System.out.println("\n\n");
}

class ListNode
{
public ListNode (Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public Object getValue () { return value; }

public ListNode getNext () { return next; }

Chapter XXXIII Linked Lists I 33.29

 public void setValue (Object theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private Object value;
private ListNode next;
}

Figure 33.18 continued

Java3312.java Output

JAVA3312.JAVA

Constructing a node with 100

Constructing a node with 101
Constructing a node with 102
Constructing a node with 103
Constructing a node with 104
Constructing a node with 105
Constructing a node with 106
Constructing a node with 107
Constructing a node with 108
Constructing a node with 109

109 108 107 106 105 104 103 102 101 100

You must be careful if you write a program to create a linked list as a queue with
the logic of the previous program. The front reference of a queue should not be
moved inside the loop structure. Your structure will have a serious access
problem if the front reference moves from node to node. front should be
anchored to the first node that is created and not move unless the first node is
removed.

The solution to this dilemma is not too difficult. Start by creating the very first
node prior to any loop structure. Create the node, assign its data value and
reference null for the next field. Makes sure that the front reference accesses
this first node. Once the node is constructed, you are ready to start a loop
structure to complete the building of the linked list. Program Java3313.java, in
figure 33.19, creates a linked list in a queue sequence.

Figure 33.19
// Java3313.java
// This program demonstrates how to create a linked list of integers.
// The linked list is created like a queue.

public class Java3313

{

33.30 Exposure Java, 2008 Edition 07-26-08

 public static void main (String args[])
{
System.out.println("\nJAVA3313.JAVA\n");

ListNode p = null;
ListNode temp = null;
ListNode front = null;

System.out.println("Constructing a node with 100");

front = new ListNode(new Integer(100),null);
temp = front;

for (int k = 101; k < 110; k++)

{
System.out.println("Constructing a node with " + k);
p = new ListNode(new Integer(k),null);
temp.setNext(p);
temp = p;
}
System.out.println();

p = front;
while (p != null)
{
System.out.print(p.getValue() + " ");
p = p.getNext();
}
System.out.println("\n\n");
}

class ListNode
{
public ListNode (Object initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public Object getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (Object theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private Object value;
private ListNode next;
}

Figure 33.19 continued

Java3313.java Output

JAVA3313.JAVA

Constructing a node with 100

Constructing a node with 101
Constructing a node with 102

Chapter XXXIII Linked Lists I 33.31

Constructing a node with 103
Constructing a node with 104
Constructing a node with 105
Constructing a node with 106
Constructing a node with 107
Constructing a node with 108
Constructing a node with 109

100 101 102 103 104 105 106 107 108 109

33.7 Considering Cases

All linked list examples up to this point have worked with stacks and queues.
Access to a stack and a queue is always at the end of a linked list and this type of
access simplifies a program. What happens if a node needs to be deleted in a
linked list? I mean a node, with a specified data field, that may be anywhere in
the linked list, or possibly not even exist. How is such a node deleted?

Linked lists can get you into very subtle trouble. Just when you start feeling
comfortable you may encounter some weird outputs for certain situations. The
nature of linked lists involves the consideration of all the possible cases that
might be encountered during some linked list process. This is a major big deal
and has a heavy impact on program reliability.

AP Examination Alert

Students with a firm understanding of many computer science

concepts often lose points on their free response section of the
exam, because they do not consider all the possible cases.

I will start with a deletion program that appears correct, but fails because of some
subtle mistake. Program Java3314.java, in figure 33.20, demonstrates the
process that is necessary to delete nodes from a linked list. The program does a
good job testing the accuracy of the deleteNode method.

33.32 Exposure Java, 2008 Edition 07-26-08

Four delete statements are used to test the program. The parameter of the
deleteNode method specifies the data field value of the node to be deleted. The
program tries to delete the first node in the list, the last node in the list and a node
in the middle of the list. Additionally, the program also tries to delete a node
with a non-existing value. See how well the program performs its assigned job.

Figure 33.20
// Java3314.java
// This program demonstrates how to delete a node from a linked list.
// The <deleteNode> method of the <List> class does not work in all cases.
// For operating convenience the <ListNode> class uses the <int> type
// for its data <value> field.

public class Java3314

{
public static void main (String args[])
{
System.out.println("\nJAVA3314.JAVA\n");
List list = new List(10);
list.displayList();
list.deleteNode(5); // delete from the middle
list.displayList();
list.deleteNode(1); // delete from the front
list.displayList();
list.deleteNode(10); // delete from the end
list.displayList();
list.deleteNode(25); // delete non-existing node
System.out.println();
}
}

class ListNode
{
public ListNode (int initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public int getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (int theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private int value;
private ListNode next;
}

class List
{
ListNode front;
int size;

public List(int n)
{
size = n;
ListNode temp, p;
front = new ListNode(1,null);
temp = front;
for (int k = 2; k <= size; k++)
{
p = new ListNode(k,null);

Chapter XXXIII Linked Lists I 33.33

 temp.setNext(p);
temp = p;
}
}

public void displayList()

{
System.out.println("\nDISPLAY OF LINKED LIST ELEMENTS\n");
ListNode p = front;
while (p != null)
{
System.out.print(p.getValue() + " ");
p = p.getNext();
}
System.out.println();
}

public void deleteNode(int key)

{
ListNode temp1 = front;
ListNode temp2 = null;
boolean exists = false;
while (temp1 != null && !exists)
{
exists = temp1.getValue() == key;
if (!exists)
{
temp2 = temp1;
temp1 = temp1.getNext();
}
}
if (exists)
{
temp2.setNext(temp1.getNext());
}
else
{
System.out.println("List node value does not exist");
}
}
}

Java3314.java Output

JAVA3314.JAVA

DISPLAY OF LINKED LIST ELEMENTS

1 2 3 4 5 6 7 8 9 10

DISPLAY OF LINKED LIST ELEMENTS

1 2 3 4 6 7 8 9 10
Exception in thread "main" java.lang.NullPointerException
at List.deleteNode(Java3313.java:94)
at Java3313.main(Java3313.java:18)

The program does have correct syntax. It must compile because there is output.
You see a display of the linked list before the first deletion and a display that
proves that the middle number 5 is deleted. After that, a bunch of runtime error
message start with the infamous NullPointerException error. Usually, that error
indicates that an attempt is made to dereference the null value. A reference to a

33.34 Exposure Java, 2008 Edition 07-26-08

node allows access to a field within the node, such as value and next with the
access methods of the ListNode class. If a reference has the null value and an
attempt is made to access its value or next field, you will get errors. You see that
this program was not careful to check every possibility.

Program Java3315.java, in figure 33.21, needs to be studied very slowly and

very carefully. Check the deleteNode method and see how each possibility is
checked. For starters the whole program and its execution are shown. Following
the whole program, the focus is on the deleteNode method and details will be
given how every case is considered.

Figure 33.21
// Java3315.java
// This program correctly implements the <deleteNode> method by considering all the possible delete cases.

public class Java3315

{
public static void main (String args[])
{
System.out.println("\nJAVA3315.JAVA\n");
List list = new List(10);
list.displayList();
list.deleteNode(5); // delete from the middle
list.displayList();
list.deleteNode(1); // delete from the front
list.displayList();
list.deleteNode(10); // delete from the end
list.displayList();
list.deleteNode(25); // delete non-existing value
System.out.println();
}
}

class ListNode
{
public ListNode (int initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}
public int getValue () { return value; }
public ListNode getNext () { return next; }
public void setValue (int theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private int value;
private ListNode next;
}

class List
{
ListNode front;
int size;

public List(int n)
{
size = n;
ListNode temp, p;
front = new ListNode(1,null);
temp = front;
for (int k = 2; k <= size; k++)
{
p = new ListNode(k,null);

Chapter XXXIII Linked Lists I 33.35

 temp.setNext(p);
temp = p;
}
}

public void displayList()

{
System.out.println("\nDISPLAY OF LINKED LIST ELEMENTS\n");
ListNode p = front;
while (p != null)
{
System.out.print(p.getValue() + " ");
p = p.getNext();
}
System.out.println();
}

public void deleteNode(int key)

{
boolean exists = false;
if (front == null)
{
exists = false;
}
else
{
if (front.getValue() == key)
{
front = front.getNext();
exists = true;
}
else
{
ListNode temp1 = front;
ListNode temp2 = null;
while (temp1 != null && !exists)
{
exists = temp1.getValue() == key;
if (!exists)
{
temp2 = temp1;
temp1 = temp1.getNext();
}
}
if (exists)
{
temp2.setNext(temp1.getNext());
}
else
{
System.out.println("List node value does not exist");
}
}
}
}

Figure 33.21 continued

Java3315.java Output

JAVA3315.JAVA

DISPLAY OF LINKED LIST ELEMENTS

1 2 3 4 5 6 7 8 9 10

33.36 Exposure Java, 2008 Edition 07-26-08

DISPLAY OF LINKED LIST ELEMENTS

1 2 3 4 6 7 8 9 10

DISPLAY OF LINKED LIST ELEMENTS

2 3 4 6 7 8 9 10

DISPLAY OF LINKED LIST ELEMENTS

2 3 4 6 7 8 9
List node value does not exist

The deleteNode method looks long and convoluted. Let us slowly start at the
beginning and build the method with each one of the cases that should be
considered. A good start is the consideration when a node needs to be deleted
from an empty list.

CASE 1: Is the list empty?

This simple, short question is forgotten so frequently. A method should not make
the assumption that a linked list exists. If front references null, then any process
on front will create a dereferencing null error. Figure 33.22 shows the first step
of the deleteNode method. Note that a local exists boolean variable is used. This
variable adds readability to the code in the method and will be used later in the
method.

Figure 33.22
public void deleteNode(int key)
{
boolean exists = false;
if (front == null)
{
exists = false;
}
}

CASE 2: Does the first node contain the key?

You have passed the first test. The list does exist. Now you must continue and
carefully check conditions in such a way that you avoid the evil dereferencing
null error. The next logical test is to see if the very first node contains the key.
Keep the following in mind. A node that is deleted in the middle of the list
requires that the preceding node is linked to the succeeding node. If the very first

Chapter XXXIII Linked Lists I 33.37

node is deleted there is no re-link process required. The only process that
happens is that the second node becomes the front. This section is added in
figure 33.23.

CASE 3: What if the list has only one node?

Now I know that some of you are clever and say, but what if the list has only one
node, then only one node needs to be deleted? You will see that it is the same
process as deleting the first node in a list. If a list has one node then the next
field of the only node is null. If we change first to the value of the next node, it
will be the second node if it exists and null otherwise. This is correct because
deleting a one-node situation should result in an empty list.

Figure 33.23
public void deleteNode(int key)
{
boolean exists = false;
if (front == null)
{
exists = false;
}
else
{
if (front.getValue() == key)
{
front = front.getNext();
exists = true;
}

CASE 4: Does some middle node contain the key?

We are making good progress. We have established if the list is empty, and if it
is not, we checked to see if the first node must be deleted. We have also learned
that deleting the first node in a one-node list requires an identical process as
deleting a node from a multi-node list. Now we must consider the case of a node
in the middle of a list. This situation requires some type of loop to iterate to
every node in the list. We also need to have a reference to the preceding node
and succeeding node. Figure 33.24 shows the code for the loop. temp2 is used
to trail temp1.

Figure 33.24
public void deleteNode(int key)
{
boolean exists = false;
if (front == null)
{
exists = false;
}

33.38 Exposure Java, 2008 Edition 07-26-08

 else
{
if (front.getValue() == key)
{
front = front.getNext();
exists = true;
}
else
{
ListNode temp1 = front;
ListNode temp2 = null;
while (temp1 != null && !exists)
{
exists = temp1.getValue() == key;
if (!exists)
{
temp2 = temp1;
temp1 = temp1.getNext();
}
}

You might be confused how this code works to delete a middle node. Figure
33.25 shows an example of a list with characters stored in data field. The object
is to delete the node storing character K. A loop starts with temp1 leading the
search and temp2 follows one node behind temp1.

Figure 33.25

[temp2] [temp1]

A G K M T

[temp2] [temp1]

A G K M T

A G M T
CASE 5: You need to delete the last node.

Deleting the last node may seem like a separate case, just like the deletion of a
single-node linked list. You will find that it is not a special situation and is
handled in precisely the same manner as deleting a node from the middle of a list.
temp1 stops at the last node and temp2 at the second-to-last node. temp2 links

Chapter XXXIII Linked Lists I 33.39

to the value of the next field in the node to be deleted, which for the last node is
null.

CASE 6: There is no node with the required key.

We are almost home free. References are placed at the desirable nodes and some
code is needed to perform the relinking process that was shown in figure 33.25.
A few more statements must be added and then the job is finished. Note in figure
33.26 that we must be careful to check if the node exists. It is quite possible that
the entire loop finished without finding the requested node. If such is the case, a
message is generated that the node could not be found, otherwise one statement
links two nodes around the deleted node and Java automatically returns the
memory space for future use.

Figure 33.26
if (exists)
{
temp2.setNext(temp1.getNext());
}
else
{
System.out.println("List node value does not exist");
}

Possible Cases to Consider to Delete a Node

1. The list is empty.

2. Delete the first node. (same as one-node list)
3. Delete a middle node. (same as last node)
4. The requested node does not exist in the list.

33.40 Exposure Java, 2008 Edition 07-26-08

33.8 An Ordered Linked List

In the previous section you learned to consider all possible cases when processing
linked lists. In truth the section strictly concentrated on all the possible cases that
may occur when a node needs to be deleted from a linked list. This chapter
started with so many examples that created lists as a stack or a queue that you
may wonder why there is the need to delete a node from somewhere in the middle
of a list. Now stacks and queues certainly have their place in computer science
and they are data structures with few complexities. The simplicity of stacks and
queues make them ideal examples. However, does it not seem more natural to
create a linked list that is ordered in some manner? The list can be ordered
alphabetically by name, numerically by account number, by age, by social
security number or any other order that is desired.

So how do you create an ordered linked list? This involves quite a bit more
processing than creating stacks and queues. A stack inserts a new node at the top
and a queue insert a new node at the end of the list. That is clean and simple, but
an ordered list requires that the desired insert location is known and such
knowledge requires considering various cases.

Program Java3316.java, in figure 33.27, demonstrates how to create an ordered

linked list. The key work horse in this program is the insertNode method of the
List class. The step-by-step detail used in the last section with deleteNode will
not be repeated for this program. With your new knowledge of checking cases,
trace through the insertNode method and see if you understand the logic. The
program starts with a static array of numbers, which are visibly not ordered. The
numbers are intentionally not random. With a special selection of numbers it is
possible to test the different cases to see if the program works correctly.

Figure 33.27
// Java3316.java
// This program demonstrates how to create an ordered list using the
// <ListNode> class with an <insert> method and considering all cases.

public class Java3316

{

public static void main (String args[])

{
System.out.println("\nJAVA3315.JAVA\n");
int[] intArray = {150,100,130,120,160,110,140};
List list = new List(intArray);
list.displayLinkedList();
System.out.println();
}
}

class ListNode
{

Chapter XXXIII Linked Lists I 33.41

 public ListNode (int initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public int getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (int theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private int value;
private ListNode next;
}

class List
{
ListNode front;
int size;

public List(int[] lst)

{
front = null;
for (int k = 0; k < lst.length; k++)
insertNode(lst[k]);
}

void insertNode(int newValue)

{
ListNode p = null;
ListNode t1 = null;
ListNode t2 = null;

p = new ListNode(newValue,null);

if (front == null)
{
front = p;
}
else
{
if (p.getValue() < front.getValue())
{
p.setNext(front);
front = p;
}
else
{
t1 = front;
while (t1 != null && p.getValue() > t1.getValue())
{
t2 = t1;
t1 = t1.getNext();
}
t2.setNext(p);
p.setNext(t1);
}
}
}

public void displayLinkedList()

{

33.42 Exposure Java, 2008 Edition 07-26-08

 System.out.println("\nDISPLAY OF LINKED LIST ELEMENTS\n");
ListNode p = front;
while (p != null)
{
System.out.print(p.getValue() + " ");
p = p.getNext();
}
System.out.println();
}
}

Figure 33.27 continued

Java3316.java Output

JAVA3316.JAVA

DISPLAY OF LINKED LIST ELEMENTS

100 110 120 130 140 150 160

Did you see the possible cases considered by the insertNode method? They are
similar, but not precisely the same as the cases considered for the deleteNode
class. One major difference is that it is always possible to insert a new node. It is
not always possible to delete a node, because the requested node must exist. With
that idea in mind see if you found the cases that are listed below

Possible Insertion Cases

1. Insert into a completely empty list.

2. Insert in front of an existing list.
3. Insert in the middle of a list. (same as at the end)

Chapter XXXIII Linked Lists I 33.43

33.9 Linked Lists and Memory

Consider the linked list diagram in figure 33.28. It is a terrific list with five
nodes. Each node has one field for character data and a second field to store the
reference linking to the next node in the list. front references the first node in the
linked list, which is ordered alphabetically.

Figure 33.28

[front] A G K M T

Now all this linked list stuff and diagrams with nodes and arrows is terrific, but
hopefully you do not expect to look inside the computer and find a bunch of
arrows that link different memory locations together. You have worked with
references before. A reference stores a memory address. So let’s get a little more
technical and represent the linked list in a manner that resembles computer reality
more closely.

The diagram, shown in figure 33.29, represents memory. Memory is identified

by a base-16 memory address like @7b00. The @ indicates address in this
illustration. The grid that is shown has four bytes per cell. For the purpose of
this illustration let us assume that the character data field and the linking
reference occupy four bytes of memory. The memory needs of a node fluctuate.
The importance here is to visualize a memory grid of addresses drawn such that
every cell can hold the information of one node in the linked list. Now also keep
in mind that there is one reference, the front pointer, which needs to be stored
somewhere. A reference may store a memory address, but this memory address
in turn needs to be stored somewhere.

The diagram represents a top view of a segment of the computer’s memory. In

particular note that some memory locations contain addresses of other memory
locations. This is precisely what happens in a linked list is. It represents the next
field of the linked list.

The linked list diagram, with its arrows, is drawn again above the memory
segment diagram. This allows a clear comparison between the two types of
linked list representations.

Figure 33.29

33.44 Exposure Java, 2008 Edition 07-26-08

[F] A G K M T

@7b00 @7b04 @7b08 @7b0c @7b10 @7b14 @7b18 @7b1c

@7b44 M
@7b94
@7b30 @7b34 @7b38 @7b3c @7b40 @7b44 @7b48 @7b4c

G A
@7b68 @7b30
@7b60 @7b64 @7b68 @7b6c @7b70 @7b74 @7b78 @7b7c

K
@7b1c

@7b90 @7b94 @7b98 @7b9c @7ba0 @7ba4 @7ba8 @7bac

T
@0000

Let us step through this diagram and see if you can visualize the linked list that is
represented here. It is possible that many of you have little trouble with the
visualization because you look at the diagram at the top of the page.

Step-1 front occupies @7b08

and stores the address of the first node, @7b44.

Step-2 The memory cell at @7b44 stores character A.

It also stores the address of the next node, @7b30.

Step-3 The memory cell at @7b30 stores character G.

It also stores the address of the next node, @7b68.

Step-4 The memory cell at @7b68 stores character K.

It also stores the address of the next node, @7b1c.

Step-5 The memory cell at @7b1c stores character M.

It also stores the address of the next node, @7b94.

Step-6 The memory cell at @7b94 stores character T.

It also stores the address of the next node, @0000.
This is NULL address and indicates the end of the linked list.

33.10 The GfxNode Class

Chapter XXXIII Linked Lists I 33.45

Drawing pictures with nodes linking to other nodes, using arrows, is not just
some cute exercise. It is a necessity to help see the actual linking process.
Linking will only become more complex. Right now all the linked lists presented
use a single, one-directional link. In the next chapter you will learn about
doubly-linked lists that have multiple links in both directions. Later on you will
also create tree structures with multiple links. The arrow diagrams help to keep
sanity in this linking business.

This chapter will finish with a tool that will help to visualize the linking process.
I have created a GfxNode class that can draw the linked list diagrams. The
constructor creates a node and there are methods to draw linking arrows.
Program Java3317.java, in figure 33.30, demonstrates the use of this class. You
need to be aware that it does demonstrate how to use the GfxNode class, but it
draws a linked list incorrectly. This is done intentionally, because a lab exercise
at the conclusion of this chapter is devoted to the very process of drawing a
linked list correctly. I did not want to supply the answer to a lab exercise in a
convenient program example.

Program Java3317.java, includes the necessary overhead required to create a

graphics application program. The focus of the program for you is the drawList
method. After the program example follows an explanation of how to use the
GfxNode class.

Figure 33.30
// Java3317.java
// This program demonstrates the use of the GfxNode class.
// The actual drawing does not represent any correct approach to
// creating a linked list.

import java.awt.*;
import java.awt.event.*;

public class Java3317

{
public static void main(String args[])
{
GfxApp gfx = new GfxApp();
gfx.setSize(1000,750);
gfx.addWindowListener(new WindowAdapter() {public void
windowClosing(WindowEvent e) {System.exit(0);}});
gfx.show();
}
}

class GfxApp extends Frame

{

private int td = 200; // time delay to slow down graphics display

33.46 Exposure Java, 2008 Edition 07-26-08

 public void paint (Graphics g)
{
g.setFont(new Font("ARIAL",Font.BOLD,28));
g.drawString("Java3317 GfxNode Demo",300,50);
drawList(g);
}

public void drawList(Graphics g)

{
GfxNode node1 = new GfxNode(g,200,200,'P',0,td);
node1.enterData(g,'A',0);
node1.drawNull(g,0);
node1.drawPointer(g,'T',2,0);

GfxNode node2 = new GfxNode(g,250,200,'P',0,td);

node2.enterData(g,'B',0);
node2.drawNull(g,0);
node2.drawPointer(g,'T',2,0);

GfxNode node3 = new GfxNode(g,300,200,'P',0,td);

node3.enterData(g,'C',0);
node3.drawNull(g,0);
node3.drawPointer(g,'T',2,0);

GfxNode node4 = new GfxNode(g,350,200,'P',0,td);

node4.enterData(g,'D',0);
node4.drawNull(g,0);
node4.drawPointer(g,'T',2,0);

GfxNode node5 = new GfxNode(g,400,200,'P',0,td);

node5.enterData(g,'E',0);
node5.drawNull(g,0);
node5.drawPointer(g,'T',2,0);

GfxNode node6 = new GfxNode(g,450,200,'P',0,td);

node6.enterData(g,'F',0);
node6.drawNull(g,0);
node6.drawPointer(g,'T',2,0);

node1.drawNull(g,9);
node1.drawLink(g,node2,0);
node2.drawNull(g,9);
node2.drawLink(g,node3,0);
node3.drawNull(g,9);
node3.drawLink(g,node4,0);
node4.drawNull(g,9);
node4.drawLink(g,node5,0);
node5.drawNull(g,9);
node5.drawLink(g,node6,0);

Chapter XXXIII Linked Lists I 33.47

In the true spirit of information hiding you will find that it is not necessary to see or
understand the actual code of the GfxNode class. The code will not be shown here,
but what is shown below is the information that is necessary to use the class. This
includes the method heading with their parameters and a brief comment that explains
the purpose of each parameter.

The best way to understand this class is by starting with a single node. Observe where
the node is placed on the screen and then change the parameters and see how the node
appearance changes. The only time that you are concerned with the location of a node
is during the construction stage. After a node is constructed, it knows it location and
arrows, as well as data, will automatically be drawn in the correct location.

GfxNode Public Methods Headers and Comments

// GfxNode constructor instantiates an object and
// stores its Top-Left coordinate (tlx,tly) information, as
// well as the length and width of the node object. A node object
// with two fields is drawn at the specified coordinate.

public GfxNode(Graphics g, int tlx, int tly, char ltr, int clr, int dt)

// Method getColor a private helper method to make it easier to use colors

33.48 Exposure Java, 2008 Edition 07-26-08

// in a graphics program.

private Color getColor(int clr)

{
Color temp = Color.white;
switch (clr)
{
case 0: temp = Color.black; break;
case 1: temp = Color.red; break;
case 2: temp = Color.green; break;
case 3: temp = Color.blue; break;
case 4: temp = Color.orange; break;
case 5: temp = Color.cyan; break;
case 6: temp = Color.magenta; break;
case 7: temp = Color.yellow; break;
case 8: temp = Color.pink; break;
case 9: temp = Color.white; break;
}
return temp;
}

// Method getX returns the top-left X-coordinate of a linked list node.

public int getx()

// Method getY returns the top-left Y-coordinate of a linked list node.

public int gety()

// Method drawPointer draws a vertical pointer down to an existing node.

// The first pointer to a node uses OffSet value 1 and the second
// pointer to the same node uses OffSet value 2. The result is that
// the second pointer is moved farther to the right.

public void drawPointer(Graphics g, char ltr, int offSet, int clr)

// Method enterData draws a letter in the Data field of the GfxNode.

void enterData(Graphics g, char ltr, int clr)

// Method drawLink draws a link from the current sourceNode to the

// endNode in the specified color (clr).

public void drawLink(Graphics g, GfxNode endNode, int clr)

// Method drawNull draws a diagonal g.drawLine in the Next

// field of a list node, to indicate a NULL value.

public void drawNull(Graphics g, int clr)

// Method drawLetter upper-case Letter characters. The characters

// are drawn in a 9x9 pixel box.
// The (x,y) parameters indicate the coordinate of the top-left corner
// of the box. Only capital letters and numbers are drawn.

public void drawLetter(Graphics g, char ltr, int x, int y)

// Method delay allows viewing the sequence in which the linked lists are drawn/

private void delay(double n)

Chapter XXXIII Linked Lists I 33.49

33.11 Practice Exercises

This chapter finishes with a set of exercises that uses a pictorial display of a linked
list in the same manner as the pictures created by the GfxNode class. Each time
you will be shown the same diagram of some initial linked list. This is followed by
a set of program statements and you select the appearance of the linked list after the
executions of the program statements are completed. The initial diagram is the
same for each exercise, but it is still displayed on each page to help visualize the
problem better. Assume that any variables used in the exercises have been declared
correctly and can be used in a logical manner. Furthermore, some of the variables
are not shown in the answer responses to avoid clutter. Everything that is necessary
to solve the problem is displayed.

Exercises 1-10 refer to the following ListNode class.

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

Each exercise is shown on a separate page and the ListNode class will be
displayed on each page to assist in solving the problem. After some initial
practice, you will probably remember the logic of the ListNode class and its
methods without needing that help. Until such time this will make the exercises
simpler to solve.

33.50 Exposure Java, 2008 Edition 07-26-08

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

01. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
p1.setValue(p2.getValue());

(A) A B C D

(B) A B C E

(C) E B C D

(D) E E E E

Chapter XXXIII Linked Lists I 33.51

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

02. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getNext() != null)
p1 = p1.getNext();
p1.setValue(p2.getValue());

(A) A B C D

(B) A E C D

(C) A B C E

(D) A B E D

33.52 Exposure Java, 2008 Edition 07-26-08

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

03. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getNext().getNext() != null)
p1 = p1.getNext();
p1.setValue(p2.getValue());

(A) A B C D

(B) A E C D

(C) A B C E

(D) A B E D

Chapter XXXIII Linked Lists I 33.53

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

04. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getNext().getNext().getNext() != null)
p1 = p1.getNext();
p2.setValue(p1.getValue());

(A) A B C D

(B) A E C D

(C) A B C E

(D) A B E D

33.54 Exposure Java, 2008 Edition 07-26-08

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

05. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

while (p1.getNext() != null)

{
p2 = p1;
p1 = p1.getNext();
p1.setValue(p2.getValue());
}

(A) A B C D

(B) D C B A

(C) D D D D

(D) A A A A

Chapter XXXIII Linked Lists I 33.55

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

06. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode(' ', null);

p2.setValue(p1.getNext().getNext().getValue());
while (p1.getNext() != null)
{
p1 = p1.getNext();
p1.setValue(p2.getValue());
}

(A) A B C D

(B) A C C C

(C) A B C C

(D) C C C D

33.56 Exposure Java, 2008 Edition 07-26-08

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

07. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getNext() != null)
p1 = p1.getNext();
p1.setNext(p2);

(A) A B C D E

(B) A B C E D

(C) A B C E

(D) A B D C

Chapter XXXIII Linked Lists I 33.57

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

08. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getNext().getNext() != null)
{
p2 = p1;
p1 = p1.getNext();
p2.setValue(p1.getValue());
}

(A) A B C D E

(B) B C D E A

(C) B C C D

(D) B C D E

33.58 Exposure Java, 2008 Edition 07-26-08

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

09. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p2 = new ListNode('E',null);
while (p1.getValue() != 'C')
{
p3 = p1;
p1 = p1.getNext();
}
p3.setNext(p2);
p2.setNext(p1);

(A) A B C E D

(B) A B E C D

(C) A E B C D

(D) A B C D E

Chapter XXXIII Linked Lists I 33.59

class ListNode
{
public ListNode (char initValue, ListNode initNext)
{
value = initValue;
next = initNext;
}

public char getValue () { return value; }

public ListNode getNext () { return next; }
public void setValue (char theNewValue) { value = theNewValue; }
public void setNext (ListNode theNewNext) { next = theNewNext; }
private char value;
private ListNode next;
}

ListNode p1, p2, p3;

10. Suppose that p1 represents the following list.

[p1]

A B C D

How is the linked list represented after the program segment below executes?

p3 = new ListNode(' ',null);

while (p1.getNext() != null)
{
p2 = p1;
p1 = p1.getNext();
p3.setValue(p1.getValue());
p1.setValue(p2.getValue());
p2.setValue(p3.getValue());
}

(A) A B C D

(B) A B C E

(C) B C D A

(D) D C B A

33.60 Exposure Java, 2008 Edition 07-26-08

 Exercise Answers
1–C 6–B
2–C 7–A
3–D 8–C
4–B 9–B
5–D 10 – C

If you did these types of exercises for the first time, they probably were pretty
tricky. Many students attempt to find an answer to linked list problems without
drawing any pictures. That is a mistake. Linked list problems rapidly become
confusing and you will quickly forget the changes in the reference values and the
data values.

Handling the practice exercises you just finished is important for two reasons.
First, this type of exercise may very well be representative of some of the
multiple choice questions on the AB examination. Second, as you write solutions
for any linked list lab assignment or free response answer on the AP examination,
you need to be able to trace accurately through your solution. This is even more
significant for the free response questions than the lab assignments. With the lab
assignment you have a computer, which displays the incorrect result of some
illogical solution. It is possible that you cannot trace linked list statement very
well, but your computer will display the actual values in each of the nodes and
give you help in debugging the problem. Free response questions are another
story. You have no computer, which provides feedback. You have very little
time and you need a method to determine accuracy.

Tracing Linked List Program Code

Anytime you design linked list code initially or check

finished linked list code, you need to draw diagrams.

Even with the limited time on an AP Examination, you

should still take the time to draw pictures. The visual image
of the linked list gives you confidence that your solution is
correct or it will quickly point out any faulty logic.

33.12 Summary
Chapter XXXIII Linked Lists I 33.61
ArrayList Warning

Java's ArrayList class allows dynamic resizing during program

execution. An ArrayList object may have some extra capacity
for additional new elements.

If the capacity is not sufficient to allow adding new elements, a

new block of memory is allocated, data is shifted from the old
block to the new block, and the old block is returned to available
memory for future use.

This process can be a considerable execution penalty, if the

array has many elements, each storing large quantities of data.

LinkedList class method addFirst

data.addFirst(value);

Method addFirst inserts the new element value to the front of

the list.

LinkedList class method addLast

data.addLast(value);

Method addLast inserts the new element value to the back of

the list.

LinkedList class method getFirst

33.62 Exposure Java, 2008 Edition 07-26-08

String name = (String) data.getFirst();

Method getFirst returns the element at the front of the list.

LinkedList class method getLast

String name = (String) data.getLast();

Method getLast returns the element at the back of the list.

LinkedList class method removeFirst

String name = (String) data.removeFirst();

Method removeFirst returns, and removes, the element from

the front of the list.

LinkedList class method removeLast

String name = (String) data.removeLast();

Method removeLast returns, and removes, the element from

the back of the list.

Constructing a ListIterator Object

Chapter XXXIII Linked Lists I 33.63

LinkedList family = new LinkedList();
ListIterator iter = family.listIterator();

The listIterator method of the LinkedList class instantiates an

iter object of the ListIterator class.

ListIterator Method next

System.out.print(iter.next() + " ");

Method next moves the iterator to the next element, and then
returns it.

ListIterator Method hasNext

while (iter.hasNext())

Method hasNext returns true if an element remains in the

Collection object and returns false otherwise.

ListIterator Method remove

iter.remove();

Method remove removes the element returned by the next

method.

ListIterator Method add

33.64 Exposure Java, 2008 Edition 07-26-08

 iter.add(new Integer(1111));

Method add inserts a new element before the next element.

ListIterator Method set

iter.set(new Integer(9999));

Method set replaces the last element value returned by method

next with the provided argument.

Self-Referenced Data Structure

A linked list data structure is made up of self-referential
objects. If the object is of ListNode type then one - or more -
fields references ListNode, like the example below.

class ListNode
{
public Object value;
public ListNode next;
}

Next Reference Rule

Chapter XXXIII Linked Lists I 33.65

The next data field is one-directional. This linking reference
value is only capable of linking to one other node.

In other words, if Node A links to node B, the two nodes

are linked but it is not possible to traverse from node B
back to node A with the link A B.

OOP ListNode Improvements

The constructor creates a new node and initializes the attribute

fields. Both the value field and the next field are initialized.
This process used to be three steps. Now it is only one
statement.

The attribute fields are private, and cannot be accessed globally

anymore.

Special get methods are declared to properly get the values of

any ListNode object.

Special set methods are declared to properly alter the values of

any ListNode object.

AP Examination Alert

33.66 Exposure Java, 2008 Edition 07-26-08

Students with a firm understanding of many computer science
concepts often lose points on their free response section of the
exam, because they do not consider all the possible cases.

Possible Cases to Consider to Delete a Node

1. The list is empty.

2. Delete the first node. (same as one-node list)
3. Delete a middle node. (same as last node)
4. The requested node does not exist in the list.

Possible Insertion Cases

1. Insert into a completely empty list.

2. Insert in front of an existing list.
3. Insert in the middle of a list. (same as at the end)

Tracing Linked List Program Code

Anytime you design linked list code initially or check

finished linked list code, you need to draw diagrams.

Even with the limited time on an AP Examination, you

should still take the time to draw pictures. The visual image
of the linked list gives you confidence that your solution is
correct or it will quickly point out any faulty logic.

Chapter XXXIII Linked Lists I 33.67

33.68 Exposure Java, 2008 Edition 07-26-08