KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > shiftone > cache > util > LinkedList


1 package org.shiftone.cache.util;
2
3
4
5 /**
6  * This linked list is different from the java.util implementation in that it exposes access to
7  * the nodes themselves, allowing lower level manipulation. This ends up being rather critical
8  * when removing elements from a cache. Having a reference to the node allows it to be removed
9  * in constant time - rather than having to search for it first.
10  *
11  * @author <a HREF="mailto:jeff@shiftone.org">Jeff Drost</a>
12  * @version $Revision: 1.8 $
13  */
14 public class LinkedList
15 {
16
17     private static Log LOG = new Log(LinkedList.class);
18     private LinkedListNode header = null;
19     private int size = 0;
20
21     /**
22      * Constructor LinkedList
23      *
24      */
25     public LinkedList()
26     {
27
28         header = new LinkedListNode(null);
29         header.value = header; // this is how I designate the header node
30 header.prev = header;
31         header.next = header;
32     }
33
34
35     /**
36      * adding an object to the list, making it the new first node.
37      * for the purposes of treating this list as a queue or stack, <b>this</b>
38      * is the end of the list that should be used when adding.
39      */
40     public final LinkedListNode addFirst(Object JavaDoc obj)
41     {
42         return addBefore(header.next, obj);
43     }
44
45
46     /**
47      * adding an object to the list, making it the new last node.
48      */
49     public final LinkedListNode addLast(Object JavaDoc obj)
50     {
51         return addBefore(header, obj);
52     }
53
54
55     /**
56      * remove a node from the end of the list (list is being used like a <b>queue</b>).
57      */
58     public final Object JavaDoc dequeue()
59     {
60         return removeLast();
61     }
62
63
64     /**
65      * remove a node from the beginning of the list (list is being
66      * used like a <b>stack</b>)
67      */
68     public final Object JavaDoc pop()
69     {
70         return removeFirst();
71     }
72
73
74     /**
75      * peek the first element without removing it. This is a <b>stack</b> style peek
76      */
77     public final LinkedListNode peekFirst()
78     {
79
80         return (header.next == header)
81                ? null
82                : header.next;
83     }
84
85
86     /**
87      * peek the last element without removing it. This is a <b>queue</b> style peek
88      */
89     public final LinkedListNode peekLast()
90     {
91
92         return (header.prev == header)
93                ? null
94                : header.prev;
95     }
96
97
98     /**
99      * Method removeFirst
100      */
101     private final Object JavaDoc removeFirst()
102     {
103         return remove(header.next);
104     }
105
106
107     /**
108      * Method removeLast
109      */
110     private final Object JavaDoc removeLast()
111     {
112         return remove(header.prev);
113     }
114
115
116     /**
117      * promotes this node to the front of the the list.
118      */
119     public final void moveToFirst(LinkedListNode node)
120     {
121         remove(node);
122         addNodeBefore(header.next, node);
123     }
124
125
126     /**
127      * demotes this node to the end of the list.
128      */
129     public final void moveToLast(LinkedListNode node)
130     {
131         remove(node);
132         addNodeBefore(header, node);
133     }
134
135
136     /**
137      * Method addBefore (somewhat expensive - alloc)
138      */
139     public final LinkedListNode addBefore(LinkedListNode node, Object JavaDoc obj)
140     {
141
142         LinkedListNode newNode = new LinkedListNode(obj);
143
144         addNodeBefore(node, newNode);
145
146         return newNode;
147     }
148
149
150     /**
151      * Method addNodeBefore
152      */
153     public final void addNodeBefore(LinkedListNode nodeToAddBefore, LinkedListNode newPreviousNode)
154     {
155
156         newPreviousNode.prev = nodeToAddBefore.prev;
157         newPreviousNode.next = nodeToAddBefore;
158         newPreviousNode.prev.next = newPreviousNode;
159         newPreviousNode.next.prev = newPreviousNode;
160
161         size++;
162     }
163
164
165     /**
166      * Removes the node from the list and returns the value of the former node.
167      */
168     public final Object JavaDoc remove(LinkedListNode node)
169     {
170
171         if ((node == null) || (node == header))
172         {
173             return null;
174         }
175
176         node.prev.next = node.next;
177         node.next.prev = node.prev;
178         node.prev = null;
179         node.next = null;
180
181         size--;
182
183         return node.value;
184     }
185
186
187     /**
188      * Method size
189      */
190     public int size()
191     {
192         return size;
193     }
194
195
196     /**
197      * Method toString
198      */
199     public String JavaDoc toString()
200     {
201
202         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
203         LinkedListNode thisNode = header.next;
204
205         sb.append("[LIST size=" + size() + "]");
206
207         while (thisNode != header)
208         {
209             sb.append("<->");
210             sb.append(String.valueOf(thisNode.value));
211
212             thisNode = thisNode.next;
213         }
214
215         return sb.toString();
216     }
217
218
219     /**
220      * Method main
221      */
222     public static void main(String JavaDoc[] args)
223     {
224
225         LinkedList fifo = new LinkedList();
226
227         for (int i = 0; i < 5; i++)
228         {
229             fifo.addFirst("#" + i);
230         }
231
232         LinkedListNode a = fifo.addFirst("AAAAA");
233         LinkedListNode b = fifo.addFirst("BBBBB");
234
235         for (int i = 5; i < 10; i++)
236         {
237             fifo.addFirst("#" + i);
238         }
239
240         fifo.moveToFirst(a);
241         fifo.moveToLast(b);
242
243         /*
244         while (fifo.pop() != null)
245         {
246             /// LOG.debug(fifo);
247         }
248         */
249     }
250 }
251
Popular Tags