LinkedList.java

/*
* Copyright (c) 2005, Graph Builder
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* * Neither the name of Graph Builder nor the names of its contributors may be
* used to endorse or promote products derived from this software without
* specific prior written permission.

* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

package com.graphbuilder.struc;

public class LinkedList {

	protected Node head = null;
	protected Node tail = null;
	protected int size = 0;

	public LinkedList() {}

	public static class Node {
		protected LinkedList list = null;
		protected Node next = null;
		protected Node prev = null;
		protected Object userObject = null;

		protected Node(LinkedList list, Object userObject) {
			this.list = list;
			this.userObject = userObject;
		}

		public LinkedList list() {
			return list;
		}

		public Node next() {
			return next;
		}

		public Node prev() {
			return prev;
		}

		public Object getUserObject() {
			return userObject;
		}

		public void setUserObject(Object userObject) {
			this.userObject = userObject;
		}

		public void insertBefore(Object o) {
			list.insertBefore(this, o);
		}

		public void insertAfter(Object o) {
			list.insertAfter(this, o);
		}

		public void remove() {
			list.removeNode(this);
		}
	}

	protected Node createNode(Object o) {
		return new Node(this, o);
	}

	protected void insertBefore(Node n, Object o) {
		Node p = createNode(o);

		if (size == 0) {
			head = p;
			tail = p;
		}
		else {
			if (n == head) {
				p.next = head;
				head.prev = p;
				head = p;
			}
			else {
				n.prev.next = p;
				p.prev = n.prev;
				n.prev = p;
				p.next = n;
			}
		}

		size++;
	}

	protected void insertAfter(Node n, Object o) {
		Node p = createNode(o);

		if (size == 0) {
			head = p;
			tail = p;
		}
		else {
			if (n == tail) {
				p.prev = tail;
				tail.next = p;
				tail = p;
			}
			else {
				n.next.prev = p;
				p.next = n.next;
				n.next = p;
				p.prev = n;
			}
		}

		size++;
	}

	protected Object removeNode(Node n) {
		if (size == 0)
			return null;

		Object o = n.userObject;

		if (n == head) {
			head = head.next;

			if (head == null)
				tail = null;
			else
				head.prev = null;
		}
		else if (n == tail) {
			tail = tail.prev;
			tail.next = null;
		}
		else {
			n.prev.next = n.next;
			n.next.prev = n.prev;
		}

		n.list = null;
		size--;
		return o;
	}

	public Node getHead() {
		return head;
	}

	public Node getTail() {
		return tail;
	}

	public void addToHead(Object o) {
		insertBefore(head, o);
	}

	public void addToTail(Object o) {
		insertAfter(tail, o);
	}

	public Object removeHead() {
		return removeNode(head);
	}

	public Object removeTail() {
		return removeNode(tail);
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public String toString() {
		StringBuffer sb = new StringBuffer(6 * size);
		sb.append("[");
		Node n = head;

		if (n != null) {
			sb.append(n.userObject);
			n = n.next;
		}

		while (n != null) {
			sb.append(", ");
			sb.append(n.userObject);
			n = n.next;
		}

		return sb.append("]").toString();
	}
}