Adding nodes to or removing nodes from a linked chain requires a special case when the operation is at the beginning of the chain. To eliminate the special case, you can add a dummy node at the beginning of the chain. The dummy node is always present but does not contain a list entry. The chain, then, is never, and so the head reference is never null, even when the list is empty. Modify the class LList as presented in this chapter, by adding a dummy node to the chain.

/** A class that implements the ADT list by using a chain of linked nodes that has a head reference. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public class LList implements ListInterface { private Node firstNode; // Reference to first node of chain private int numberOfEntries;

public LList() { initializeDataFields(); } // end default constructor public void clear() { initializeDataFields(); } // end clear public void add(T newEntry) // OutOfMemoryError possible { Node newNode = new Node(newEntry);

if (isEmpty()) firstNode = newNode; else // Add to end of non-empty list { Node lastNode = getNodeAt(numberOfEntries); lastNode.setNextNode(newNode); // Make last node reference new node } // end if numberOfEntries++; } // end add

public void add(int newPosition, T newEntry) { if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) { Node newNode = new Node(newEntry); if (newPosition == 1) // Case 1 { newNode.setNextNode(firstNode); firstNode = newNode; } else // Case 2: list is not empty { // and newPosition > 1 Node nodeBefore = getNodeAt(newPosition - 1); Node nodeAfter = nodeBefore.getNextNode(); newNode.setNextNode(nodeAfter); nodeBefore.setNextNode(newNode); } // end if numberOfEntries++; } else throw new IndexOutOfBoundsException("Illegal position given to add operation."); } // end add

public T remove(int givenPosition) { T result = null; // Return value

if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty();

if (givenPosition == 1) // Case 1: Remove first entry { result = firstNode.getData(); // Save entry to be removed firstNode = firstNode.getNextNode(); // Remove entry } else // Case 2: Not first entry { Node nodeBefore = getNodeAt(givenPosition - 1); Node nodeToRemove = nodeBefore.getNextNode(); result = nodeToRemove.getData(); // Save entry to be removed Node nodeAfter = nodeToRemove.getNextNode(); nodeBefore.setNextNode(nodeAfter); // Remove entry } // end if

numberOfEntries--; // Update count return result; // Return removed entry } else throw new IndexOutOfBoundsException("Illegal position given to remove operation."); } // end remove

public T replace(int givenPosition, T newEntry) { if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty();

Node desiredNode = getNodeAt(givenPosition); T originalEntry = desiredNode.getData(); desiredNode.setData(newEntry); return originalEntry; } else throw new IndexOutOfBoundsException("Illegal position given to replace operation."); } // end replace

public T getEntry(int givenPosition) { if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) { assert !isEmpty(); return getNodeAt(givenPosition).getData(); } else throw new IndexOutOfBoundsException("Illegal position given to getEntry operation."); } // end getEntry

public T[] toArray() { // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] result = (T[])new Object[numberOfEntries]; int index = 0; Node currentNode = firstNode; while ((index < numberOfEntries) && (currentNode != null)) { result[index] = currentNode.getData(); currentNode = currentNode.getNextNode(); index++; } // end while return result; } // end toArray public boolean contains(T anEntry) { boolean found = false; Node currentNode = firstNode; while (!found && (currentNode != null)) { if (anEntry.equals(currentNode.getData())) found = true; else currentNode = currentNode.getNextNode(); } // end while return found; } // end contains

public int getLength() { return numberOfEntries; } // end getLength

public boolean isEmpty() { boolean result;

if (numberOfEntries == 0) // Or getLength() == 0 { assert firstNode == null; result = true; } else { assert firstNode != null; result = false; } // end if

return result; } // end isEmpty // Initializes the class's data fields to indicate an empty list. private void initializeDataFields() { firstNode = null; numberOfEntries = 0; } // end initializeDataFields // Returns a reference to the node at a given position. // Precondition: The chain is not empty; // 1 <= givenPosition <= numberOfEntries. private Node getNodeAt(int givenPosition) { assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= numberOfEntries); Node currentNode = firstNode; // Traverse the chain to locate the desired node // (skipped if givenPosition is 1) for (int counter = 1; counter < givenPosition; counter++) currentNode = currentNode.getNextNode(); assert currentNode != null; return currentNode; } // end getNodeAt

private class Node { private T data; // Entry in list private Node next; // Link to next node

private Node(T dataPortion) { data = dataPortion; next = null; } // end constructor

private Node(T dataPortion, Node nextNode) { data = dataPortion; next = nextNode; } // end constructor

private T getData() { return data; } // end getData

private void setData(T newData) { data = newData; } // end setData

private Node getNextNode() { return next; } // end getNextNode

private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode } // end Node } // end LList