// This example is from _Java Examples in a Nutshell_. (http://www.oreilly.com) // Copyright (c) 1997 by David Flanagan // This example is provided WITHOUT ANY WARRANTY either expressed or implied. // You may study, use, modify, and distribute it for non-commercial purposes. // For any commercial use, see http://www.davidflanagan.com/javaexamples /** * 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); 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 the LinkedList class **/ public static class Test { /** * This is a test class that implements the Linkable interface **/ static class LinkableString implements Linkable { String i; // The data contained in the node Linkable next; // A reference to the next node in the list public LinkableString(String i) { this.i = i; } // Constructor method public Linkable getNext() { return next; } // Part of Linkable public void setNext(Linkable node) { next = node; } // Part of Linkable public String toString() { return i + ""; } // For easy printing public boolean equals(Object o) { // For comparison if (this == o) return true; if (!(o instanceof LinkableString)) return false; if (((LinkableString)o).i.equals(this.i)) return true; return false; } } /** * 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 method public Linkable getNext() { return next; } // Part of Linkable public void setNext(Linkable node) { next = node; } // Part of 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)); // Insert some more stuff ll.insertAtTail(new LinkableInteger(6)); System.out.println(ll.removeFromHead()); // Remove and print a node System.out.println(ll.removeFromTail()); // Remove and print another 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); } } /** * This is a test class that implements the Linkable interface **/ static class LinkableString implements Linkable { String i; // The data contained in the node Linkable next; // A reference to the next node in the list public LinkableString(String i) { this.i = i; } // Constructor method public Linkable getNext() { return next; } // Part of Linkable public void setNext(Linkable node) { next = node; } // Part of Linkable public String toString() { return i + ""; } // For easy printing public boolean equals(Object o) { // For comparison if (this == o) return true; if (!(o instanceof LinkableString)) return false; if (((LinkableString)o).i.equals(this.i)) return true; return false; } } /** * 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 method public Linkable getNext() { return next; } // Part of Linkable public void setNext(Linkable node) { next = node; } // Part of 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; } } public static void main(String[] args) { /** The test program. Insert some nodes, remove some nodes, then * print out all elements in the list. It should print out the * numbers 314 714 33 3 1 5 826 and 534 ... int then String **/ 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(33)); ll.insertAtHead(new LinkableInteger(714)); ll.insertAtTail(new LinkableInteger(5)); // Insert some more stuff ll.insertAtTail(new LinkableInteger(826)); // Insert some more stuff ll.insertAtTail(new LinkableInteger(6)); ll.remove(new LinkableInteger(6)); // Remove another one ll.remove(new LinkableInteger(2)); // Remove another one ll.insertAtTail(new LinkableInteger(534)); // Insert some more stuff ll.insertAtHead(new LinkableInteger(314)); // Now print out the contents of the list. for(Linkable l = ll.getHead(); l != null; l = l.getNext()) System.out.println(l); System.out.println(" ... and then there were strings ..."); LinkedList lls = new LinkedList(); // Create a list lls.insertAtHead(new LinkableString("1")); // Insert some stuff lls.insertAtHead(new LinkableString("2")); lls.insertAtHead(new LinkableString("3")); lls.insertAtHead(new LinkableString("33")); lls.insertAtHead(new LinkableString("714")); lls.insertAtTail(new LinkableString("5")); // Insert some more stuff lls.insertAtTail(new LinkableString("826")); // Insert some more stuff lls.insertAtTail(new LinkableString("6")); lls.remove(new LinkableString("6")); // Remove another one lls.remove(new LinkableString("2")); // Remove another one lls.insertAtTail(new LinkableString("534")); // Insert some more stuff lls.insertAtHead(new LinkableString("314")); // Now print out the contents of the list. for(Linkable ls = lls.getHead(); ls != null; ls = ls.getNext()) System.out.println(ls); } }