001: /**
002: * $RCSfile: LinkedList.java,v $
003: * $Revision: 1.3 $
004: * $Date: 2006/01/07 00:21:06 $
005: *
006: * Copyright (C) 2000 CoolServlets.com. All rights reserved.
007: *
008: * ===================================================================
009: * The Apache Software License, Version 1.1
010: *
011: * Redistribution and use in source and binary forms, with or without
012: * modification, are permitted provided that the following conditions
013: * are met:
014: *
015: * 1. Redistributions of source code must retain the above copyright
016: * notice, this list of conditions and the following disclaimer.
017: *
018: * 2. Redistributions in binary form must reproduce the above copyright
019: * notice, this list of conditions and the following disclaimer in
020: * the documentation and/or other materials provided with the
021: * distribution.
022: *
023: * 3. The end-user documentation included with the redistribution,
024: * if any, must include the following acknowledgment:
025: * "This product includes software developed by
026: * CoolServlets.com (http://www.Yasna.com)."
027: * Alternately, this acknowledgment may appear in the software itself,
028: * if and wherever such third-party acknowledgments normally appear.
029: *
030: * 4. The names "Jive" and "CoolServlets.com" must not be used to
031: * endorse or promote products derived from this software without
032: * prior written permission. For written permission, please
033: * contact webmaster@Yasna.com.
034: *
035: * 5. Products derived from this software may not be called "Jive",
036: * nor may "Jive" appear in their name, without prior written
037: * permission of CoolServlets.com.
038: *
039: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
040: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
041: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
042: * DISCLAIMED. IN NO EVENT SHALL COOLSERVLETS.COM OR
043: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
044: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
045: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
046: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
047: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
048: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
049: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
050: * SUCH DAMAGE.
051: * ====================================================================
052: *
053: * This software consists of voluntary contributions made by many
054: * individuals on behalf of CoolServlets.com. For more information
055: * on CoolServlets.com, please see <http://www.Yasna.com>.
056: */package com.Yasna.util;
057:
058: import java.util.*;
059:
060: /**
061: * Simple LinkedList implementation. The main feature is that list nodes
062: * are public, which allows very fast delete operations (when one has a
063: * reference to the node that is to be deleted).<p>
064: *
065: * The linked list implementation was specifically written for the CoolServlets
066: * cache system. While it can be used as a general purpose linked list, for
067: * most applications, it is more suitable to use the linked list that is part
068: * of the Java Collections package.
069: */
070: public class LinkedList {
071:
072: /**
073: * The root of the list keeps a reference to both the first and last
074: * elements of the list.
075: */
076: private LinkedListNode head = new LinkedListNode("head", null, null);
077:
078: /**
079: * Creates a new linked list.
080: */
081: public LinkedList() {
082: head.next = head.previous = head;
083: }
084:
085: /**
086: * Returns the first linked list node in the list.
087: *
088: * @return the first element of the list.
089: */
090: public LinkedListNode getFirst() {
091: LinkedListNode node = head.next;
092: if (node == head) {
093: return null;
094: }
095: return node;
096: }
097:
098: /**
099: * Returns the last linked list node in the list.
100: *
101: * @return the last element of the list.
102: */
103: public LinkedListNode getLast() {
104: LinkedListNode node = head.previous;
105: if (node == head) {
106: return null;
107: }
108: return node;
109: }
110:
111: /**
112: * Adds a node to the beginning of the list.
113: *
114: * @param node the node to add to the beginning of the list.
115: */
116: public LinkedListNode addFirst(LinkedListNode node) {
117: node.next = head.next;
118: node.previous = head;
119: node.previous.next = node;
120: node.next.previous = node;
121: return node;
122: }
123:
124: /**
125: * Adds an object to the beginning of the list by automatically creating a
126: * a new node and adding it to the beginning of the list.
127: *
128: * @param object the object to add to the beginning of the list.
129: * @return the node created to wrap the object.
130: */
131: public LinkedListNode addFirst(Object object) {
132: LinkedListNode node = new LinkedListNode(object, head.next,
133: head);
134: node.previous.next = node;
135: node.next.previous = node;
136: return node;
137: }
138:
139: /**
140: * Adds an object to the end of the list by automatically creating a
141: * a new node and adding it to the end of the list.
142: *
143: * @param object the object to add to the end of the list.
144: * @return the node created to wrap the object.
145: */
146: public LinkedListNode addLast(Object object) {
147: LinkedListNode node = new LinkedListNode(object, head,
148: head.previous);
149: node.previous.next = node;
150: node.next.previous = node;
151: return node;
152: }
153:
154: /**
155: * Erases all elements in the list and re-initializes it.
156: */
157: public void clear() {
158: //Remove all references in the list.
159: LinkedListNode node = getLast();
160: while (node != null) {
161: node.remove();
162: node = getLast();
163: }
164:
165: //Re-initialize.
166: head.next = head.previous = head;
167: }
168:
169: /**
170: * Returns a String representation of the linked list with a comma
171: * delimited list of all the elements in the list.
172: *
173: * @return a String representation of the LinkedList.
174: */
175: public String toString() {
176: LinkedListNode node = head.next;
177: StringBuffer buf = new StringBuffer();
178: while (node != head) {
179: buf.append(node.toString()).append(", ");
180: node = node.next;
181: }
182: return buf.toString();
183: }
184: }
|