LinkedList


1   /**
2    * $RCSfile: LinkedList.java,v $
3    * $Revision: 1.3 $
4    * $Date: 2005/03/10 17:53:39 $
5    *
6    * Copyright (C) 2004 Jive Software. All rights reserved.
7    *
8    * This software is published under the terms of the GNU Public License (GPL),
9    * a copy of which is included in this distribution.
10   */
11  
12  package org.jivesoftware.util;
13  
14  
15  /**
16   * Simple LinkedList implementation. The main feature is that list nodes
17   * are public, which allows very fast delete operations when one has a
18   * reference to the node that is to be deleted.<p>
19   *
20   * @author Jive Software
21   */
22  public class LinkedList {
23  
24      /**
25       * The root of the list keeps a reference to both the first and last
26       * elements of the list.
27       */
28      private LinkedListNode head = new LinkedListNode("head", null, null);
29  
30      /**
31       * Creates a new linked list.
32       */
33      public LinkedList() {
34          head.next = head.previous = head;
35      }
36  
37      /**
38       * Returns the first linked list node in the list.
39       *
40       * @return the first element of the list.
41       */
42      public LinkedListNode getFirst() {
43          LinkedListNode node = head.next;
44          if (node == head) {
45              return null;
46          }
47          return node;
48      }
49  
50      /**
51       * Returns the last linked list node in the list.
52       *
53       * @return the last element of the list.
54       */
55      public LinkedListNode getLast() {
56          LinkedListNode node = head.previous;
57          if (node == head) {
58              return null;
59          }
60          return node;
61      }
62  
63      /**
64       * Adds a node to the beginning of the list.
65       *
66       * @param node the node to add to the beginning of the list.
67       */
68      public LinkedListNode addFirst(LinkedListNode node) {
69          node.next = head.next;
70          node.previous = head;
71          node.previous.next = node;
72          node.next.previous = node;
73          return node;
74      }
75  
76      /**
77       * Adds an object to the beginning of the list by automatically creating a
78       * a new node and adding it to the beginning of the list.
79       *
80       * @param object the object to add to the beginning of the list.
81       * @return the node created to wrap the object.
82       */
83      public LinkedListNode addFirst(Object   object) {
84          LinkedListNode node = new LinkedListNode(object, head.next, head);
85          node.previous.next = node;
86          node.next.previous = node;
87          return node;
88      }
89  
90      /**
91       * Adds an object to the end of the list by automatically creating a
92       * a new node and adding it to the end of the list.
93       *
94       * @param object the object to add to the end of the list.
95       * @return the node created to wrap the object.
96       */
97      public LinkedListNode addLast(Object   object) {
98          LinkedListNode node = new LinkedListNode(object, head, head.previous);
99          node.previous.next = node;
100         node.next.previous = node;
101         return node;
102     }
103 
104     /**
105      * Erases all elements in the list and re-initializes it.
106      */
107     public void clear() {
108         //Remove all references in the list.
109         LinkedListNode node = getLast();
110         while (node != null) {
111             node.remove();
112             node = getLast();
113         }
114 
115         //Re-initialize.
116         head.next = head.previous = head;
117     }
118 
119     /**
120      * Returns a String representation of the linked list with a comma
121      * delimited list of all the elements in the list.
122      *
123      * @return a String representation of the LinkedList.
124      */
125     public String   toString() {
126         LinkedListNode node = head.next;
127         StringBuilder   buf = new StringBuilder  ();
128         while (node != head) {
129             buf.append(node.toString()).append(", ");
130             node = node.next;
131         }
132         return buf.toString();
133     }
134 }
135
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags