001: /**
002: * $RCSfile$
003: * $Revision: 1113 $
004: * $Date: 2005-03-10 09:53:39 -0800 (Thu, 10 Mar 2005) $
005: *
006: * Copyright (C) 2004 Jive Software. All rights reserved.
007: *
008: * This software is published under the terms of the GNU Public License (GPL),
009: * a copy of which is included in this distribution.
010: */package org.jivesoftware.util;
011:
012: /**
013: * Simple LinkedList implementation. The main feature is that list nodes
014: * are public, which allows very fast delete operations when one has a
015: * reference to the node that is to be deleted.<p>
016: *
017: * @author Jive Software
018: */
019: public class LinkedList {
020:
021: /**
022: * The root of the list keeps a reference to both the first and last
023: * elements of the list.
024: */
025: private LinkedListNode head = new LinkedListNode("head", null, null);
026:
027: /**
028: * Creates a new linked list.
029: */
030: public LinkedList() {
031: head.next = head.previous = head;
032: }
033:
034: /**
035: * Returns the first linked list node in the list.
036: *
037: * @return the first element of the list.
038: */
039: public LinkedListNode getFirst() {
040: LinkedListNode node = head.next;
041: if (node == head) {
042: return null;
043: }
044: return node;
045: }
046:
047: /**
048: * Returns the last linked list node in the list.
049: *
050: * @return the last element of the list.
051: */
052: public LinkedListNode getLast() {
053: LinkedListNode node = head.previous;
054: if (node == head) {
055: return null;
056: }
057: return node;
058: }
059:
060: /**
061: * Adds a node to the beginning of the list.
062: *
063: * @param node the node to add to the beginning of the list.
064: */
065: public LinkedListNode addFirst(LinkedListNode node) {
066: node.next = head.next;
067: node.previous = head;
068: node.previous.next = node;
069: node.next.previous = node;
070: return node;
071: }
072:
073: /**
074: * Adds an object to the beginning of the list by automatically creating a
075: * a new node and adding it to the beginning of the list.
076: *
077: * @param object the object to add to the beginning of the list.
078: * @return the node created to wrap the object.
079: */
080: public LinkedListNode addFirst(Object object) {
081: LinkedListNode node = new LinkedListNode(object, head.next,
082: head);
083: node.previous.next = node;
084: node.next.previous = node;
085: return node;
086: }
087:
088: /**
089: * Adds an object to the end of the list by automatically creating a
090: * a new node and adding it to the end of the list.
091: *
092: * @param object the object to add to the end of the list.
093: * @return the node created to wrap the object.
094: */
095: public LinkedListNode addLast(Object object) {
096: LinkedListNode node = new LinkedListNode(object, head,
097: head.previous);
098: node.previous.next = node;
099: node.next.previous = node;
100: return node;
101: }
102:
103: /**
104: * Erases all elements in the list and re-initializes it.
105: */
106: public void clear() {
107: //Remove all references in the list.
108: LinkedListNode node = getLast();
109: while (node != null) {
110: node.remove();
111: node = getLast();
112: }
113:
114: //Re-initialize.
115: head.next = head.previous = head;
116: }
117:
118: /**
119: * Returns a String representation of the linked list with a comma
120: * delimited list of all the elements in the list.
121: *
122: * @return a String representation of the LinkedList.
123: */
124: public String toString() {
125: LinkedListNode node = head.next;
126: StringBuilder buf = new StringBuilder();
127: while (node != head) {
128: buf.append(node.toString()).append(", ");
129: node = node.next;
130: }
131: return buf.toString();
132: }
133: }
|