Skip to main content
Logo image

Java, Java, Java Object-Oriented Problem Solving, 2024E

Ralph Morelli, Ralph Walde, Beryl Hoffman, David G. Cooper

Section 16.2 The Linked List Data Structure

As we said, a static data structure is one whose size is fixed during a program’s execution—a static structure’s memory is allocated at compile time. By contrast, a dynamic structure is one that can grow and shrink as needed. In this section, we will develop a dynamic list, which is a data structure whose elements are arranged in a linear sequence. There is a first element in the list, a second element, and so on. Lists are quite general and, as we will discuss later, lists have a broad range of applications. Depending on how elements are inserted and removed from a list, they can be used for a range of specialized purposes.
🔗

Subsection 16.2.1 Using References to Link Objects

As you know from earlier chapters, when you create an object using the new operator you get back a reference to the object that you then can assign to a reference variable. In the following example, b is a reference to a JButton:
🔗
JButton b = new JButton();
We have defined many classes that contained references to other objects:
🔗
public class Student {
     private String name;
}
In this example, name is a reference to a String object.
🔗
A linked list is a list in which a collection of nodes are linked together by references from one node to the next.
🔗
To make a linked list, we will define a class of self-referential objects. A self-referential object is an object that contains a reference to an object of the same class. The convention is to name this object Node:
🔗
public class Node {
     private String name;
     private Node next;
}
In addition to the reference to a String object, each Node object contains a reference to another Node object. The next variable is often called a link because it is used to link together two Node objects. For example, Figure 16.2.1 provides an illustration of a linked list of Node s.
🔗
Figure 16.2.1. A linked list of Nodes terminated by a null link.
🔗
By assigning references to the next variables in each Node, we can chain together arbitrarily long lists of objects. Therefore, we will want to add methods to our Node class that enable us to manipulate a Node’s next variable (Figure 16.2.2). By assigning it a reference to another Node, we can link two Node s together. By retrieving the link’s value, we can find the next Node in the list.
🔗
Figure 16.2.2. The Node class.
🔗
In addition to the link variable, each Node stores some data. In this example, the data is a single String. But there’s no real limit to the amount and type of data that can be stored in a linked list. Therefore, in addition to methods that manipulate a Node’s link, we will also want methods to manipulate its data. These points suggest the following basic design for a Node:
🔗
public class Node {
     private Object data;
     private Node next;
     public Node(Object obj);          // Constructor
     public void setData(Object obj);  // Data access
     public Object getData();
     public void setNext(Node link);   // Link access
     public Node getNext();
} // Node
Note that we have defined the Node’s data in the most general possible way: as a reference to an Object. Because the Object class is the root of Java’s entire class hierarchy, an Object can encompass any kind of data. By using Java’s wrapper classes, such as Integer and Double, a Node’s data can even include primitive data.
🔗
The important point is that regardless of its type of data, a Node will have data access methods and link access methods. The data access methods differ, depending on the type of data, but the link access methods will generally be the same.
🔗

Exercises Self-Study Exercises

1. New String Node.
Which of the following statements correctly creates a new Node whose data consist of the String“Hello.”
🔗
  • Node node = new Node(new String("Hello"));
  • That’s one way.
  • Node node = new Node("Hello");
  • That’s one way.
  • Node node = new Node(new String("hello"));
  • Spelling?
  • Node node = new Node("hello");
  • Spelling?
Hint.
The Node constructor has the following signature: public Node(Object obj).
🔗
🔗
🔗
2. New Integer Node.
The Integer wrapper class has a constructor with the following signature: Integer(int value). Which of the following statements correctly creates a new Node whose data is the value 100.
🔗
  • Node node = new Node(100);
  • An int is not an Object.
  • Node node = new Node(new Integer(100));
  • Correct, you need to use the Integer wrapper.
  • Node node = new Node("100");
  • We want an integer, not a string.
  • Node node = new int(100);
  • You need to use the Integer wrapper.
Hint.
The Node constructor has the following signature: public Node(Object obj).
🔗
🔗
🔗
🔗
🔗

Subsection 16.2.2 Example: The Dynamic Phone List

Let’s define a PhoneListNode class that can be used to implement a phone list (Figure 16.2.5). This definition will be a straightforward specialization of the generic Node list defined in the previous section. Each element of the phone list will consist of a person’s name and phone number. These will be the node’s data and can be stored in two String variables. To access these data, we will provide a constructor and a basic set of access methods. Thus, we have the definition shown in Listing 16.2.6.
🔗
Figure 16.2.5. Design of the PhoneListNode class.
🔗
Listing 16.2.6. The PhoneListNode class.
🔗
public class PhoneListNode {
     private String name;
     private String phone;
     private PhoneListNode next;
     public PhoneListNode(String s1, String s2) {
         name = s1;
         phone = s2;
         next = null;
     } // PhoneListNode()
     public void setData(String s1, String s2) {
         name = s1;
         phone = s2;
     } // setData()
     public String getName() {
         return name;
     } // getName()
     public String getData() {
         return name + " " + phone;
     } // getData()
     public String toString() {
         return name + " " + phone;
     } // toString()
     public void setNext(PhoneListNode nextPtr) {
         next = nextPtr;
     } // setNext()
     public PhoneListNode getNext() {
         return next;
     } // getNext()
} // PhoneListNode
The constructor and data access methods should be familiar to you. Note that the constructor sets the initial value of next to null, which means that it refers to no object.
🔗
Let’s discuss the details of the link access methods—the setNext() and getNext() methods—which are also simple to implement. Because this is a PhoneListNode, these methods take PhoneListNode as a parameter and return type, respectively. Given a reference to a PhoneListNode, the setNext() method assigns it to next. The getNext() method simply returns the value of its next link.
🔗
Let’s now see how we would use these methods to construct a list. The following statements create three nodes:
🔗
PhoneListNode node1 = new PhoneListNode("Roger M","090-997-2918");
PhoneListNode node2 = new PhoneListNode("Jane M","090-997-1987");
PhoneListNode node3 = new PhoneListNode("Stacy K","090-997-9188");
The next two statements chain the nodes together into the list shown in Figure 16.2.8:
🔗
node1.setNext(node2);
node2.setNext(node3);
Figure 16.2.8. The phonelist: a linked list of nodes, each of which contains a person’s name and phone number.
🔗
If we wanted to add a fourth node to the end of this list, we could use the following statements:
🔗
PhoneListNode node4 = new PhoneListNode("gary g","201-119-8765");
node3.setNext(node4);
Although this example illustrates the basic technique for inserting nodes at the end of the list, it depends too much on our knowledge of the list. In order to be truly useful we will have to develop a more general set of methods to create and manipulate a list of nodes. As we will see, a better design would be able to find the end of the list without knowing anything about the list’s data.
🔗

Exercises Self-Study Exercise

1. New PhoneListNode.
Suppose you know that nodeptr is a reference to the last element of a linked list of PhoneListNodes. Which of the following will correctly create a new PhoneListNode for “Bill C” with phone number “111-202-3331” and link it into the end of the list?
🔗
  • PhoneListNode newNode = new PhoneListNode("Bill C", "111-202-3331");
  • That creates a node but doesn’t link it.
  • nodeptr.setNext(newNode);
  • You first need to create newNode and populate it with the correct data.
  • PhoneListNode newNode = new PhoneListNode(Bill C, 111-202-3331);
nodeptr.setNext(newNode);
  • The constructor needs String arguments.
  • PhoneListNode newNode = new PhoneListNode("Bill C", "111-202-3331");
nodeptr.setNext(newNode);
  • Correct.
Hint.
See the most recent example above.
🔗
🔗
🔗
🔗
🔗

Subsection 16.2.3 Manipulating the Phone List

In addition to the Nodes that make a list, we must define a class containing methods to manipulate the list. This class will include the insert, access, and remove methods. It must also contain a reference to the list itself. This leads to the basic design shown in Figure 16.2.10. Because this is a list of PhoneListNode s, we need a PhoneListNode reference to point to the list, which is the purpose of the head variable.
🔗
Figure 16.2.10. The PhoneList class has a reference to the first node of the list (head) and methods to insert, remove, and look up information.
🔗
A preliminary coding of the PhoneList class is shown in Listing 16.2.12. As you can see there, when a new PhoneList instance is constructed, head is initialized to null, meaning the list is initially empty. Since we will frequently want to test whether the list is empty, we define the booleanisEmpty() method for that purpose. As you can see, its definition says that a list is empty when the reference to the head of this list is null.
🔗
Listing 16.2.12. A preliminary version of the PhoneList class.
🔗
public class PhoneList {
    private PhoneListNode head;
    public PhoneList() {
        head = null;         // Start with empty list
    }
    public boolean isEmpty() {  // Defines an empty list
        return head == null;
    }
    public void insert(PhoneListNode node) { }
    public String getPhone(String name) { }
    public String remove(String name) { }
    public void print() { }
} // PhoneList
🔗

Subsection 16.2.4 Inserting Nodes into a List

The insert() method will have the task of inserting new PhoneListNodes into the list. There are a number of ways to do this. The node could be inserted at the beginning or at the end of the list, or in alphabetical order, or possibly in other ways. As we’ll see, it is easiest to insert a new node at the head of the list. But for this example, let’s develop a method that inserts the node at the end of the list.
🔗
Figure 16.2.13. Two cases. (a) The list is empty before the insertion, which takes place at head. (b) The list is not empty, so the insertion takes place at the end of the list.
🔗
There are two cases we need to worry about for this algorithm. First, if the list is empty, we can insert the node by simply setting head to point to the node [Figure 16.2.13(a)]. Second, if the list is not empty, we must move through, or traverse, the links of the list until we find the last node and insert the new node after it [Figure 16.2.13(b)]. In this case, we want to set the next variable of the last node to point to the new node. This gives us the following algorithm:
🔗
public void insert(PhoneListNode newNode) {
  if (isEmpty())
    head = newNode;                   // Insert at head of list
  else {
    PhoneListNode current = head;     // Start traversal at head
    while (current.getNext() != null) // While not at the last node
      current = current.getNext();    //   go to next node
    current.setNext( newNode );       // Do the insertion
  } // else
} // insert()
Recall that when nodes are linked, their next variables are non-null. So when a node’s next variable is null, that indicates the end of the list—there’s no next node. Thus, our algorithm begins by checking if the list is empty. If so, we assign head the reference to newNode, the PhoneListNode that’s being inserted.
🔗
If the list is not empty, then we need to find the last node. In order to traverse the list, we will need a temporary variable, current, which will always point to the current node. It’s important to understand the while loop used here:
🔗
PhoneListNode current = head;       // Initializer
while (current.getNext() != null)   // Entry condition
     current = current.getNext();    // Updater
The loop variable, current, is initialized by setting it to point to the head of the list. The entry condition tests whether the next link, leading out of current, is null(Figure 16.2.14). That is, when the link coming out of a node is null, then that node is the last node in the list [Figure 16.2.14(c)]. Inside the while loop, the update expression simply assigns the next node to current. In that way, current will point to each successive node until the last node is found. It’s very important that the loop exits when current.getNext() is null—that is, when the next pointer of the current node is null. That way current is pointing to the last node and can be used to set its next variable to the node being inserted [Figure 16.2.14(d)]. Thus, after the loop is exited, current still points to the last node. At that point, the setNext() method is used to link newNode into the list as the new last node.
🔗
Figure 16.2.14. The temporary variable current is used to traverse the list to find its end.
🔗
🔗

Subsection 16.2.5 Printing the Nodes of a List

The print() method also uses a traversal strategy to print the data from each node of the list. Here again it is necessary to test whether the list is empty. If so, we must print an error message. (This would be a good place to throw a programmer-defined exception, such as an EmptyListException.) If the list is not empty, then we use a temporary variable to traverse the list, printing each node’s data along the way:
🔗
public void print() {
  if (isEmpty())
     System.out.println("Phone list is empty");
  PhoneListNode current = head;               // Start traversal at head
  while (current != null) {                   // While not end of list
    System.out.println( current.toString() ); //  print data
    current = current.getNext();              //  go to next node
  }
} // print()
Note the differences between this while loop and the one used in the insert() method. In this case, we exit the loop when current becomes null; there’s no action to be taken after the loop is exited. The printing takes place within the loop. Thus, in this case, the entry condition, (current != null), signifies that the task has been completed.
🔗
🔗

Subsection 16.2.6 Looking up a Node in a List

Because the record associated with a person can be located anywhere in the list, the traversal strategy must also be used to look up someone’s phone number in the PhoneList. Here again we start at the head of the list and traverse through the next links until we find the node containing the desired phone number. This method takes the name of the person as a parameter. There are three cases to worry about: (1) The list is empty; (2) the normal case where the person named is found in the list; and (3) the person named is not in the list. Because the method returns a String, we can return error messages in the first and third cases:
🔗
public String getPhone(String name) {
  if (isEmpty())                    // Case 1: Empty list
    return "Phone list is empty";
  else {
     PhoneListNode current = head;
     while ((current.getNext() != null) &&
                 (!current.getName().equals(name)))
        current = current.getNext();
     if (current.getName().equals(name))
        return current.getData(); // Case 2: Found name
     else                        // Case 3: No such person
        return ("Sorry.  No entry for " + name);
  } // else
} // getPhone()
Note the while loop in this case. As in the insert() method, when the loop exits, we need a reference to the current node so that we can print its phone number [current.getData()]. But here there are three ways to exit the loop: (1) We reach the end of the list without finding the named person; (2) we find the named person in the interior of the list; or (3) we find the named person in the last node of the list. In any case, it is necessary to test whether the name was found or not after the loop is exited. Then appropriate action can be taken.
🔗

Exercises Self-Study Exercise

1. Loop Exit Condition.
What if the exit condition for the while loop in getPhone() were stated as 
((current.getNext() != null) || (!current.getName().equals(name)))
🔗
  • It would cause the loop to be skipped entirely.
    🔗
  • No, it may cause the loop to exit beforee the correct name is found.
  • It may cause an infinite loop.
    🔗
  • No, it may cause the loop to exit beforee the correct name is found.
  • This condition should also work.
    🔗
  • No, it may cause the loop to exit beforee the correct name is found.
  • It will cause the loop to exit for any nonnull node.
    🔗
  • Correct. The exit condition is too general. It will cause the loop to exit as soon as a nonnull node is encountered, whether or not the node matches the one being sought.
Hint.
Apply the condition on the example given in the text.
🔗
🔗
🔗
🔗
🔗

Subsection 16.2.7 Removing a Node from a List

By far the most difficult task is that of removing a node from a list. In the PhoneList we use the person’s name to identify the node, and we return a String that can be used to report either success or failure. There are four cases to worry about in designing this algorithm: (1) The list is empty, (2) the first node is being removed, (3) some other node is being removed, and (4) the named person is not in the list. The same traversal strategy we used in getPhone() is used here, with the same basic while loop for cases 3 and 4.
🔗
As Listing 16.2.17 shows, the first two cases are easily handled. If the list is empty, we just return an error message.
🔗
Listing 16.2.17. The remove() method.
🔗
public String remove(String name) { // Remove an entry by name
  if (isEmpty())                         // Case 1: empty list
    return "Phone list is empty";

  PhoneListNode current = head;         // Initialize traverse
  PhoneListNode previous = null;

  if (current.getName().equals(name)) { // Case 2: remove first node
    head = current.getNext();
    return "Removed " + current.toString() ;
  }

                                        // Start traverse
  while ((current.getNext() != null) &&
                              (!current.getName().equals(name)))  {
    previous = current;
    current = current.getNext();
  }

  if (current.getName().equals(name)) { // Case 3: remove named node
    previous.setNext(current.getNext());
    return "Removed " + current.toString();
  } else
    return ("Sorry.  No entry for " + name); // Case 4: node not found
} // remove()
We use current as the traversal variable. If the named node is the first node, we simply need to set head to current.getNext(), which has the effect of making head point to the second node in the list [Figure 16.2.19(a)]. Once the node is cut out from the chain of links, there will be no further reference to it. In this case, Java will recapture the memory it uses when it does garbage collection.
🔗
Figure 16.2.19. Removing different nodes from a linked list.
🔗
In order to remove some other node besides the first, two traversal variables are needed: previous and current. They proceed together down the list, with previous always pointing to the node just before the current node. The reason, of course, is that to remove the current node, you need to adjust the link pointing to it contained in the previous node [Figure 16.2.19(b)]. That is, the new value of previous.next will be the current value of current.next. We use the getNext() and setNext() methods to effect this change:
🔗
previous.setNext(current.getNext());
🔗

Subsection 16.2.8 Testing the List

In developing list-processing programs, it is important to design good test data. As we have seen, both the insertion and removal operations involve several distinct cases. Proper testing of these methods ideally would test every possible case. The main() program in Listing 16.2.20 illustrates the kinds of tests that should be performed. This method could be incorporated directly into the PhoneList class, or it could be made part of a separate class.
🔗
Listing 16.2.20. A main() method containing a set of tests for the PhoneList class.
🔗
public static void main(String argv[]) {
                  // Create list and insert nodes
  PhoneList list = new PhoneList();
  list.insert( new PhoneListNode("Roger M", "997-0020"));
  list.insert( new PhoneListNode("Roger W", "997-0086"));
  list.insert( new PhoneListNode("Rich P", "997-0010"));
  list.insert( new PhoneListNode("Jane M", "997-2101"));
  list.insert( new PhoneListNode("Stacy K", "997-2517"));
                  // Test whether insertions worked
  System.out.println( "Phone Directory" );
  list.print();
                  // Test whether lookups work
  System.out.println("Looking up numbers by name");
  System.out.println(list.getPhone("Roger M"));
  System.out.println(list.getPhone("Rich P"));
  System.out.println(list.getPhone("Stacy K"));
  System.out.println(list.getPhone("Mary P"));
  System.out.println(list.remove("Rich P"));
  System.out.println("Phone Directory");
  list.print();
      // Test removals, printing list after each removal
  System.out.println(list.remove("Roger M"));
  System.out.println("Phone Directory");
  list.print();
  System.out.println(list.remove("Stacy K"));
  System.out.println("Phone Directory");
  list.print();
  System.out.println(list.remove("Jane M"));
  System.out.println("Phone Directory");
  list.print();
  System.out.println(list.remove("Jane M"));
  System.out.println("Phone Directory");
  list.print();
  System.out.println(list.remove("Roger W"));
  System.out.println("Phone Directory");
  list.print();
  System.out.println(list.remove("Roger W"));
  System.out.println("Phone Directory");
  list.print();
} // main()
Of course, there are often so many combinations of list operations that exhaustive testing might not be feasible. At the very least you should design test data that test each of the different conditions identified in your algorithms. For example, in testing removals from a list, you should test all four cases that we discussed. In testing insertions or lookups, you should test all three cases that we identified.
🔗

Exercises Self-Study Exercises

1. PhoneList Test.
The complete implementation of the PhoneList app is given here. Experiment with it to see how it works. Then add a new node to the list with your name and number. Print the list. Then remove your entry and print again.
🔗
🔗
2. PhoneList Test, Part 2.
Using the code on the previous exercise, design and implement a test of PhoneList that shows that new elements can be inserted into a list after all of its previous nodes have been removed.
🔗
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext