001: package org.shiftone.cache.util;
002:
003: /**
004: * This linked list is different from the java.util implementation in that it exposes access to
005: * the nodes themselves, allowing lower level manipulation. This ends up being rather critical
006: * when removing elements from a cache. Having a reference to the node allows it to be removed
007: * in constant time - rather than having to search for it first.
008: *
009: * @author <a href="mailto:jeff@shiftone.org">Jeff Drost</a>
010: * @version $Revision: 1.8 $
011: */
012: public class LinkedList {
013:
014: private static Log LOG = new Log(LinkedList.class);
015: private LinkedListNode header = null;
016: private int size = 0;
017:
018: /**
019: * Constructor LinkedList
020: *
021: */
022: public LinkedList() {
023:
024: header = new LinkedListNode(null);
025: header.value = header; // this is how I designate the header node
026: header.prev = header;
027: header.next = header;
028: }
029:
030: /**
031: * adding an object to the list, making it the new first node.
032: * for the purposes of treating this list as a queue or stack, <b>this</b>
033: * is the end of the list that should be used when adding.
034: */
035: public final LinkedListNode addFirst(Object obj) {
036: return addBefore(header.next, obj);
037: }
038:
039: /**
040: * adding an object to the list, making it the new last node.
041: */
042: public final LinkedListNode addLast(Object obj) {
043: return addBefore(header, obj);
044: }
045:
046: /**
047: * remove a node from the end of the list (list is being used like a <b>queue</b>).
048: */
049: public final Object dequeue() {
050: return removeLast();
051: }
052:
053: /**
054: * remove a node from the beginning of the list (list is being
055: * used like a <b>stack</b>)
056: */
057: public final Object pop() {
058: return removeFirst();
059: }
060:
061: /**
062: * peek the first element without removing it. This is a <b>stack</b> style peek
063: */
064: public final LinkedListNode peekFirst() {
065:
066: return (header.next == header) ? null : header.next;
067: }
068:
069: /**
070: * peek the last element without removing it. This is a <b>queue</b> style peek
071: */
072: public final LinkedListNode peekLast() {
073:
074: return (header.prev == header) ? null : header.prev;
075: }
076:
077: /**
078: * Method removeFirst
079: */
080: private final Object removeFirst() {
081: return remove(header.next);
082: }
083:
084: /**
085: * Method removeLast
086: */
087: private final Object removeLast() {
088: return remove(header.prev);
089: }
090:
091: /**
092: * promotes this node to the front of the the list.
093: */
094: public final void moveToFirst(LinkedListNode node) {
095: remove(node);
096: addNodeBefore(header.next, node);
097: }
098:
099: /**
100: * demotes this node to the end of the list.
101: */
102: public final void moveToLast(LinkedListNode node) {
103: remove(node);
104: addNodeBefore(header, node);
105: }
106:
107: /**
108: * Method addBefore (somewhat expensive - alloc)
109: */
110: public final LinkedListNode addBefore(LinkedListNode node,
111: Object obj) {
112:
113: LinkedListNode newNode = new LinkedListNode(obj);
114:
115: addNodeBefore(node, newNode);
116:
117: return newNode;
118: }
119:
120: /**
121: * Method addNodeBefore
122: */
123: public final void addNodeBefore(LinkedListNode nodeToAddBefore,
124: LinkedListNode newPreviousNode) {
125:
126: newPreviousNode.prev = nodeToAddBefore.prev;
127: newPreviousNode.next = nodeToAddBefore;
128: newPreviousNode.prev.next = newPreviousNode;
129: newPreviousNode.next.prev = newPreviousNode;
130:
131: size++;
132: }
133:
134: /**
135: * Removes the node from the list and returns the value of the former node.
136: */
137: public final Object remove(LinkedListNode node) {
138:
139: if ((node == null) || (node == header)) {
140: return null;
141: }
142:
143: node.prev.next = node.next;
144: node.next.prev = node.prev;
145: node.prev = null;
146: node.next = null;
147:
148: size--;
149:
150: return node.value;
151: }
152:
153: /**
154: * Method size
155: */
156: public int size() {
157: return size;
158: }
159:
160: /**
161: * Method toString
162: */
163: public String toString() {
164:
165: StringBuffer sb = new StringBuffer();
166: LinkedListNode this Node = header.next;
167:
168: sb.append("[LIST size=" + size() + "]");
169:
170: while (this Node != header) {
171: sb.append("<->");
172: sb.append(String.valueOf(this Node.value));
173:
174: this Node = this Node.next;
175: }
176:
177: return sb.toString();
178: }
179:
180: /**
181: * Method main
182: */
183: public static void main(String[] args) {
184:
185: LinkedList fifo = new LinkedList();
186:
187: for (int i = 0; i < 5; i++) {
188: fifo.addFirst("#" + i);
189: }
190:
191: LinkedListNode a = fifo.addFirst("AAAAA");
192: LinkedListNode b = fifo.addFirst("BBBBB");
193:
194: for (int i = 5; i < 10; i++) {
195: fifo.addFirst("#" + i);
196: }
197:
198: fifo.moveToFirst(a);
199: fifo.moveToLast(b);
200:
201: /*
202: while (fifo.pop() != null)
203: {
204: /// LOG.debug(fifo);
205: }
206: */
207: }
208: }
|