Linked List (Double Ended)

The following class implements an iterable linked list that maintains a reference to both the first and last nodes of the list.

If we restricted ourselves to using only the methods addFirst(Item item) and removeFirst to insert and remove elements, we would effectively be using a stack.

Similarly, If we restricted ourselves to using only the methods addLast(Item item) and removeFirst() to insert and remove elements, we would effectively would be using a queue.

For completeness, there is a removeLast() method, so that this class could also function as a deque -- but note that this method suffers from the inefficiency of having to traverse the list to get a reference to the parent of the last node. This could be fixed by implementing a doubly-linked list, where each node stores a link to both the next node and the previous node.

A contains(Item item) method is also included so that we can determine if a given item is present in the list.


import java.util.Iterator;

public class LinkedList implements Iterable {
    
    private class Node {
        Item item;
        Node next;
    }
   
    // instance variables
    private Node first;
    private Node last; 
    
    public boolean isEmpty() {
        return (first == null);
    }
    
    public void addFirst(Item item) {   
        Node node = new Node();
        node.item = item;
        
        if (this.isEmpty()) { // no items in list
            first = node;
            last = node;
        }
        else { // one or more items in list
            node.next = first;
            first = node;   
        }
    }
    
    public Item removeFirst() {     
        if (this.isEmpty()) { //no nodes in list
            return null; 
        }
        else if (first == last) { // one node in list
            Item item = first.item;
            first = null;
            last = null;
            return item;               
        }
        else { // more than one node in list
            Item item = first.item;      
            first = first.next;          
            return item;  
        }
    }
    
    public void addLast(Item item) {
        Node node = new Node();
        node.item = item;
        
        if (this.isEmpty()) { // no items in list
            first = node;
            last = node;
        }
        else { // one or more items in list
            last.next = node;
            last = node;
        }
    }
   
    public Item removeLast() {
        if (this.isEmpty()) {
            return null; //there is no last element
        }
        else if (first == last) { // one element in list
            Item item = first.item;
            first = null;
            last = null;
            return item;
        }
        else { // more than one item in list
            Node n = first; //and we already know that first and second is not null

            // we need a link to the node previous to the last node, so...
            while (n.next.next != null) {  
                n = n.next;
            }
            //n is now parent to last node...
            Item item = n.next.item;
            n.next = null;
            // the above would have been much easier in a doubly-linked list, 
            // where we have a link to the previous node!

            //don't forget to update "last" before we return the item removed...
            last = n;
            return item;
        }
    }
    
    public boolean contains(Item item) {  
        for (Node n = first; n != null; n = n.next) {
            if (n.item.equals(item)) return true;
        }
        return false;
    }

    private class TopToBottomIterator implements Iterator{
        Node node = first;

        public boolean hasNext() {
            return (node != null);
        }

        public Item next() {
            Item itemToReturn = node.item;
            node = node.next;
            return itemToReturn;
        }
    }
    
    public Iterator iterator() {
        return new TopToBottomIterator();
    }
    
    public String toString() {
        String outputStr = "";
        outputStr += "First: " + ((first != null) ? first.item : "-") + "\t";
        outputStr += "Last: " + ((last != null) ? last.item : "-") + "\t\t";
        outputStr += " List: ";
        for (Item i : this) {
            outputStr += i + " ";
        }
        return outputStr;
    }

    public static void main(String[] args) {
        String s;
        LinkedList list = new LinkedList();
        
        list.addFirst("a"); System.out.println(list);
        list.addFirst("b"); System.out.println(list);
        list.addFirst("c"); System.out.println(list);
        list.addFirst("d"); System.out.println(list);
        System.out.println("contains c? " + list.contains2("b"));
        s = list.removeFirst(); System.out.println(list);
        s = list.removeFirst(); System.out.println(list);
        s = list.removeFirst(); System.out.println(list);
        s = list.removeFirst(); System.out.println(list);
    }
}