linkedlist.java

These are the examples from the book Java Examples in a Nutshell, 2nd Edition, by David Flanagan.

/*
 * Copyright (c) 2000 David Flanagan.  All rights reserved.
 * This code is from the book Java Examples in a Nutshell, 2nd Edition.
 * It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
 * You may study, use, and modify it for any non-commercial purpose.
 * You may distribute it non-commercially as long as you retain this notice.
 * For a commercial use license, or to purchase the book (recommended),
 * visit http://www.davidflanagan.com/javaexamples2.
 */
package com.davidflanagan.examples.classes;

/**
 * This class implements a linked list that can contain any type of object
 * that implements the nested Linkable interface.  Note that the methods are
 * all synchronized, so that it can safely be used by multiple threads at
 * the same time.
 **/
public class LinkedList {
    /** 
     * This interface defines the methods required by any object that can be
     * linked into a linked list.
     **/
    public interface Linkable {
        public Linkable getNext();     // Returns the next element in the list
        public void setNext(Linkable node); // Sets the next element in the list
    }

    // This class has a default constructor: public LinkedList() {}

    /** This is the only field of the class.  It holds the head of the list */
    Linkable head;

    /** Return the first node in the list */
    public synchronized Linkable getHead() { return head; }

    /** Insert a node at the beginning of the list */
    public synchronized void insertAtHead(Linkable node) {
        node.setNext(head);
        head = node;
    }

    /** Insert a node at the end of the list */
    public synchronized void insertAtTail(Linkable node) {
        if (head == null) head = node;
        else {
            Linkable p, q;
            for(p = head; (q = p.getNext()) != null; p = q) /* no body */;
            p.setNext(node);
        }
    }

    /** Remove and return the node at the head of the list */
    public synchronized Linkable removeFromHead() {
        Linkable node = head;
        if (node != null) {
            head = node.getNext();
            node.setNext(null);
        }
        return node;
    }

    /** Remove and return the node at the end of the list */
    public synchronized Linkable removeFromTail() {
        if (head == null) return null;
        Linkable p = head, q = null, next = head.getNext();
        if (next == null) {
            head = null;
            return p;
        }
        while((next = p.getNext()) != null) { 
            q = p; 
            p = next;
        }
        q.setNext(null);
        return p;
    }

    /** 
     * Remove a node matching the specified node from the list.  
     * Use equals() instead of == to test for a matched node.
     **/
    public synchronized void remove(Linkable node) {
        if (head == null) return;
        if (node.equals(head)) { 
            head = head.getNext(); 
            return;
        }
        Linkable p = head, q = null;
        while((q = p.getNext()) != null) {
            if (node.equals(q)) {
                p.setNext(q.getNext());
                return;
            }
            p = q;
        }
    }
    
    /** This nested class defines a main() method that tests LinkedList */
    public static class Test {
        /**
	 * This is a test class that implements the Linkable interface
	 **/
        static class LinkableInteger implements Linkable {
            int i;          // The data contained in the node
            Linkable next;  // A reference to the next node in the list
            public LinkableInteger(int i) { this.i = i; }  // Constructor
            public Linkable getNext() { return next; }     // Part of Linkable
            public void setNext(Linkable node) { next = node; } // Linkable
            public String toString() { return i + ""; }    // For easy printing
            public boolean equals(Object o) {              // For comparison
                if (this == o) return true;
                if (!(o instanceof LinkableInteger)) return false;
                if (((LinkableInteger)o).i == this.i) return true;
                return false;
            }
        }

        /**
	 * The test program.  Insert some nodes, remove some nodes, then
	 * print out all elements in the list.  It should print out the
	 * numbers 4, 6, 3, 1, and 5
	 **/
        public static void main(String[] args) {
            LinkedList ll = new LinkedList();         // Create a list
            ll.insertAtHead(new LinkableInteger(1));  // Insert some stuff
            ll.insertAtHead(new LinkableInteger(2));
            ll.insertAtHead(new LinkableInteger(3));
            ll.insertAtHead(new LinkableInteger(4));
            ll.insertAtTail(new LinkableInteger(5));
            ll.insertAtTail(new LinkableInteger(6));
            System.out.println(ll.removeFromHead()); // Remove and print a node
            System.out.println(ll.removeFromTail()); // Remove and print again
            ll.remove(new LinkableInteger(2));       // Remove another one

            // Now print out the contents of the list.
            for(Linkable l = ll.getHead(); l != null; l = l.getNext())
                System.out.println(l);
        }
    }
}