linkedlist.java

一些JAVA的小程序

//
//	LinkedList class
//		written by Tim Budd
//		for Java/OOP book (as yet unnamed)
//

import java.util.*;

public class LinkedList {
	private Link firstLink;
	private Link lastLink;
	private int  count = 0;

	public LinkedList () 
		{ firstLink = lastLink = new Link(null, null, null); }

	private class Link {
		public Object value;
		public Link next;
		public Link prev;

		public Link (Object v, Link n, Link p) 
			{ value = v; next = n; prev = p; }

		public void insert (Object newValue) {
			Link newNode = new Link (newValue, this, prev);
			count++;
			if (prev == null)
				firstLink = newNode;
			else
				prev.next = newNode;
			prev = newNode;
		}

		public Object remove () {
			if (next == null) 
				return null; // cannot remove last element
			count--;
			next.prev = prev;
			if (prev == null)
				firstLink = next;
			else
				prev.next = next;
			return value;
		}
	}

	private class ListEnumeration implements Enumeration {
		public Link link = null;

		public boolean hasMoreElements () { 
			if (link == null)
				link = firstLink;
			else
				link = link.next;
			return link.next != null; }

		public Object nextElement () { return link.value; }
	}

	public boolean isEmpty () { return firstLink == lastLink; }

	public int size () { return count; }

	public void addFront (Object newValue) { firstLink.insert(newValue); }

	public void addBack (Object newValue) { lastLink.insert(newValue); }

	public void addElement (Enumeration e, Object newValue) {
		ListEnumeration le = (ListEnumeration) e;
		le.link.insert (newValue);
	}

	public Object removeFront () { return firstLink.remove(); }

	public Object removeBack () { return lastLink.prev.remove(); }

	public Object removeElement (Enumeration e) {
		ListEnumeration le = (ListEnumeration) e;
		return le.link.remove ();
	}

	public Enumeration elements () { return new ListEnumeration(); }
}