• A linked list is a List object in which the following property is satisfied:

Each element is contained in an object, called an Entry object, which also includes a reference, called a link, to the Entry object that contains the next element in the list.

• For the Entry object that holds the last element, there is no "next" element.
   
• Some linked lists also satisfy the following property:

Each Entry object includes a link to the Entry object that contains the previous element in the list.

• A linked list that satisfies this property is called a doubly linked list.
• Otherwise, it is called a singly linked list.

• The SinglyLinkedList class has very little functionality, and is not part of the Java Collections Framework.
   
• The elements in a SinglyLinkedList object are not stored contiguously, so with each element we must provide information on how to get to the next element in the collection.

• First, we create a class to hold:
  • A reference to an element.
  • And a "next" reference.
• In this Entry class
  • There are no specified methods.
  • Of course, there is a default constructor.
  • Two fields.
  • With the E type parameter.

protected class Entry<E> 
{
	protected E element;
	protected Entry<E> next;
} // class Entry

We use an arrow to indicate that the next field at the base of the arrow contains a reference to the Entry object pointed to by the tip of the arrow.

• In the last Entry object, the next field has the value null, which indicates that there is no subsequent Entry object.

• The Entry class will be embedded in the SinglyLinkedList class.
  • A class that is embedded in another class is called a nested class.
  • This embedding allows the SinglyLinkedList to access the two fields in an Entry object directly.
  • The Entry class has protected visibility for the sake of future subclasses of SinglyLinkedList.

public class SinglyLinkedList\<E> extends AbstractCollection<E> implements List<E>

• The SinglyLinkedList class will implement the Collection interface in the Java Collections Framework.
• As with the other Collection classes, the SinglyLinkedList class is parameterized, with E as the type parameter.

1. Default Constructor

/**
* Initializes this SinglyLinkedList object to be empty, with elements to be of type E.
*
*/
public SinglyLinkedList();

Note: Saying that a SinglyLinkedList object is empty means that the collection has not elements in it.

 2. The isEmpty Method

/**
* Determines if this SinglyLinkedList object has no elements.
*
* @return true - if this SinglyLinkedList object has no elements; otherwise, false.
*
*/
public boolean isEmpty();

If we start with

SinglyLinkedList<Double> myLinked = new SinglyLinkedList<Double>();
System.out.println(myLinked.isEmpty());

• The output will be true because the object referenced by myLinked has no elements.

3. The addToFront method

/** 
* Adds a specizialed element to the front of this SinglyLinkedList.
*
* @param element - the element to be inserted (at the front).
*
*/
public void addToFront(E element);

• Elements are inserted only at the front of a SinglyLinkedList object.
  • This allows for a simpler implementation.

For example, suppose the SinglyLinkedList object referenced by myLinked consists of "yes" --> "no" --> "maybe" in that order.

• And the message is:

myLinked.addToFront("simple");

Then the SinglyLinkedList object referenced by myLinked will consist of "simple" --> "yes" --> "no" --> "maybe" in that order.

• The method identifier addToFront is used instead of add because the add(E element) in the List interface specifies that element must be inserted at the end of the list, and that is somewhat more difficult than inserting at the front.

4. The size method

/**
* Determines the number of elements in this SinglyLinkedList object.
* The worstTime(n) is O(n).
*
* @return the number of elements.
*
*/
public int size();

Suppose the SinglyLinkedList object referenced by myLinked consists of the elements "simple" --> "yes" --> "no" --> "maybe" in that order.

• If the message is

System.out.println(myLinked.size());

Then the output will be 4.

5. The contains method

/**
* Determines if this SinglyLinkedList object contains a specified element.
* The worstTime(n) is O(n).
*
* @param obj - the specified element being sought.
*
* @return true - if this SinglyLinkedList object contains obj; otherwise, false.
* 
*/
public boolean contains(Object obj);

• The user is responsible for ensuring that the equals method is explicitly defined for the class that includes obj and the elements in the SinglyLinkedList.
  • Otherwise, the Object's class version of equals will be applied.

public boolean equals(Object obj) {
	return(this == obj);
}

• This method tests whether the reference to the calling object contains the same address as the reference obj.
• Because equality-of-reference is tested instead of equality of elements, false will be returned if the calling-object reference and obj are references to distinct but identical objects!

• The missing thing is a reference to the first Entry object.
• This missing "link" will be a field in the SinglyLinkedList class and in fatc the only field.

protected Entry<E> head;

Suppose a SinglyLinkedList object is constructed as follows:

SinglyLinkedList<Integer> scoreList = new SinglyLinkedList<Integer>();

• To make scoreList a reference to an empty SinglyLinkedList object, all the default constructor has to do is to initialize the head field to null.
• Since a reference field is automatically initialized to null, we need not define the default constructor, but we will do so for the sake of being explicit.

public SinglyLinkedList() {
	head = null;
} // default constructor.

public boolean isEmpty() {
	return head == null;
} // method is empty.

1. Step 1:
   • We start by constructing a new Entry object.
2. Step 2:
   • And assigning (a reference to) the new element to that Entry object's element field.
3. Step 3:
   • The reference we assign to the next field should be a reference to what had been the first Entry before this call to addToFront.
   • In other words, we should assign head to reference the new Entry object.

public void addToFront(E element) {
	Entry<E> newEntry = new Entry<E>();
	newEntry.element = element;
	newEntry.next = head;
	head = newEntry;
} // method addToFront

1. Step 1:
   • We initialize a local int variable, count to 0.
   • We initialize a local Entry reference, current to head.
2. Step 2:
   • We then loop until current is null.
   • And increment count and current during each loop iteration.
   • Incrementing current means changing current so that current will reference the next Entry after the one current is now referencing.
   • That is, we set:

current = current.next;

Here is the definition of the size method:

public int size() {
	int count = 0;
	for(Entry<E> current = head; current != null; current = current.next) {
		count++;
	}
	return count;
} // method size

• The loop goes through the entire SinglyLinkedList object, so worstTime(n) is linear in n --> O(n).
  • As is averageTime(n).

• Note that if we add a size field to the SinglyLinkedList class, the definition of the size() method becomes one-linear, namely:

return size;

• BUT then the definition of the addToFront method would have to be modified to maintain the value of the size field.

The loop structure is similar to the one in the definition of the size method, except that we need to compare element to current.element.

• For the sake of compatibility with the LinkedList class in the Java Collections Framework, we allow null elements in a SinglyLinkedList object.
  • So we need a separate loop for the case where element is null.
  • We needed a special case for obj == null because the message obj.equals(current.element) will throw a NullPointerException.

public boolean contains(Object obj) {
	if(obj == null) 
	{
		for(Entry<E> current = head; current != null; current = current.next) 
			if(obj == current.element) return true;		
	} // if obj == null
	else
	{
		for(Entry<E> current = head; current != null; current = current.next)
			if(obj.equals(current.element)) 
				return true;
	}
	return false; 
} // method contains

One important point of the SinglyLinkedList class is that a linked structure for storing a collection of elements is different from an array or ArrayList objects in two key aspects:

1. The size of the collection need not be known in advance.
   • We simply add elements at will.
   • So we do not have to worry, as we would with an array, about allocating too much space or too little space.
   • But it should be noted that in each Entry object, the next field consumes extra space: it contains program information rather than problem information.
2. Random access is not available.
   • To access some element, we would have to start by accessing the head element, and then accessing the next element after the head element, and so on.

We have not yet established a way for a user to loop through the elements in a SinglyLinkedList object.

• The solution is to develop an Iterator class for SinglyLinkedList objects, that is, a class that implements the Iterator interface, and of which each instance will iterate over a SinglyLinkedList object.
   
• The SinglyLinkedListIterator class will be a protected class embedded within the SinglyLinkedList class.
  • We want our Iterator object to be positioned at an Entry so we can easily get the next element and determine if there are any more elements beyond where the Iterator object is positioned.
• For now, the SinglyLinkedListIterator class will have only one field.

protected Entry<E> next;

We will fully implement only three methods:

• A default constructor.
• next().
• hasNext().
• The remove() method will simply throw an exception.

protected class SinglyLinkedListIterator implements Iterator<E> {
	protected Entry<E> next;

	/**
	* Initializes this SinglyLinkedListIterator object
	*
	*/
	protected SinglyLinkedList() {
		...
	}

	/**
	* Determines if this Iterator object is positioned at an element in this SinglyLinkedListIterator object.
	*
	* @return true - if this Iterator object is this positioned at an element; otherwise false.
	*
	*/ 
	public boolean hasNext() {
		...
	}

	/**
	* Returns the element this Iterator object was (before this call) positioned at, and advances this Iterator object.
	*
	* @return - the element this Iterator object positioned at.
	*
	* @throws NullPointerException - if this Iterator object was not positioned at an element before this call.
	*/
	public E next() {
		...
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}
} // class SinglyLinkedListIterator

Note that the SinglyLinkedList has E as its type parameter because SinglyLinkedListIterator implements Iterator<E>.

• An interface does not have any constructors because an interface cannot be instantiated, so the Iterator interface had no constructors.
  • But we will need a constructor for the SinglyLinkedListIterator class.
  • Otherwise, the compiler would generate a default constructor and the Java Virtual Machine would simply, but worthlessly initialize the next field to null.
  • Where do we want to start iterating? At the head of SinglyLinkedList.

protected SinglyLinkedList() {
	next = head;
} // default constructor.

• The method can access the head because the SinglyLinkedListIterator class is embedded in the SinglyLinkedList class, where head is a field.

• The hasNext() method should return true as long as the next field (in the SinglyLinkedListIterator class, not in the Entry class) is referencing an Entry object.

public boolean hasNext() {
	return next != null;
} // method hasNext

Suppose we have a SinglyLinkedList of two String elements and the default constructor for the SinglyLinkedList has just been called.

• The first element to be returned --> "Karen" --> next.element.
• The next field --> should be advanced to point to the next Entry object.
  • That is, the SinglyLinkedListIterator's next field should get the reference stored in the next field of the Entry object that the SinglyLinkedListIterator's next field currently pointing to.

We cannot anything after a return, so we save next.element before advancing next, and then we return (a reference to) the saved element.

public E next() {
	E theElement = next.element;
	next = next.next;
	return theElement;
} // method next.

Iterating through a SinglyLinkedList object.

First, we have to associate a SinglyLinkedListIterator object with a SinglyLinkedList object.

• The iterator method creates the necessary connection.

/**
* Returns a SinglyLinkedListIterator object to iterate over this SinglyLinkedList object.
*
*/
public Iterator<E> iterator() {
	return new SinglyLinkedList<E>();
} // method iterator

Iterator<Boolean> itr = myLinked.iterator();

• The variable itr is a polymorphic reference: it can be assigned a reference to an object in any class (for example, SinglyLinkedListIterator) that implements the Iterator<Boolean> interface.
   

The actual iteration is straightforward.

• For example, to print out each element:

while(itr.hasNext()) 
	System.out.println(itr.next());

• Or, even simpler, with the enhanced for statement:

for(Boolean b: mylist) 
	System.out.println(b);

Test Program

import java.util.*;

public class SinglyLinkedExample {
	public static void main(String[] args) {
		new SinglyLinkedListExample().run();
	}

	public void run() {
		final double SENTINEL = - 1.0;

		final String INPUT_PROMT = "\nPlease enter a GPA (or " + SENTINEL + " to quit) ".
		final String AVERAGE_MESSAGE = "\n\nThe average GPA is ";
		final String NO_VALID_INPUT = "\n\nError: there were no valid grade-point-averages in the input."

		SinglyLinkedList<Double> gpaList = new SinglyLinkedList<Double>();
		
		Scanner sc = new Scanner(System.in);
		double oneGPA, sum = 0.0;
		while(true) {
			try 
			{
				System.out.print(INPUT_PROMPT);
				oneGPA = sc.nextDouble();
				if(oneGPA == SENTINEL) 
					break;
				gpaList.addToFront(oneGPA);
			}
			catch(Exception e) 
			{
				System.out.println(e);
				sc.nextLine();
			} // catch
		}
			for(Double gpa: gpaList)
				sum += gpa;
			if(gpaList.size() > 0) 
				System.out.println(AVERAGE_MESSAGE + (sum/gpaList.size()));
			else
				System.out.println(NO_VALID_INPUT);
		}
	}
}

Suppose we want to insert "placid" in front of "serene" in the doubly-linked list.

• First: --> we need to get a reference to the Entry object that holds "serene".
  • That will take linear-in-n time, on average, where n is the size of the linked list.
• After that --> the insertion entails constructing a new Entry object, storing "placid" as its element, and adjusting four links.
  • The previous and next links for "placid".
  • The next link for the predecessor of serene.
  • The previous link for serene.
• In other words, once we have a reference to an Entry object, we can insert a new element in front of that Entry object in constant time,

Suppose we want to remove "mellow" from the partially shown linked list in this figure.