KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > batik > util > DoublyLinkedList


1 /*
2
3    Copyright 2001,2003 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.util;
19
20 /**
21  * A simple Doubly Linked list class, designed to avoid
22  * O(n) behaviour on insert and delete.
23  */
24 public class DoublyLinkedList {
25
26     /**
27      * Basic doubly linked list node interface.
28      */
29     public static class Node {
30         private Node next = null;
31         private Node prev = null;
32             
33         public final Node getNext() { return next; }
34         public final Node getPrev() { return prev; }
35                         
36         protected final void setNext(Node newNext) { next = newNext; }
37         protected final void setPrev(Node newPrev) { prev = newPrev; }
38
39         /**
40          * Unlink this node from it's current list...
41          */
42         protected final void unlink() {
43             if (getNext() != null)
44                 getNext().setPrev(getPrev());
45             if (getPrev() != null)
46                 getPrev().setNext(getNext());
47             
48             setNext(null);
49             setPrev(null);
50         }
51                         
52         /**
53          * Link this node in, infront of nde (unlinks it's self
54          * before hand if needed).
55          * @param nde the node to link in before.
56          */
57         protected final void insertBefore(Node nde) {
58             // Already here...
59 if (this == nde) return;
60
61             if (getPrev() != null)
62                 unlink();
63             
64             // Actually insert this node...
65 if (nde == null) {
66                 // empty lst...
67 setNext(this);
68                 setPrev(this);
69             } else {
70                 setNext(nde);
71                 setPrev(nde.getPrev());
72                 nde.setPrev(this);
73                 if (getPrev() != null)
74                     getPrev().setNext(this);
75             }
76         }
77     }
78
79
80     private Node head = null;
81     private int size = 0;
82             
83     public DoublyLinkedList() {}
84             
85     /**
86      * Returns the number of elements currently in the list.
87      */
88     public synchronized int getSize() { return size; }
89
90     /**
91      * Removes all elements from the list.
92      */
93     public synchronized void empty() {
94         while(size > 0) pop();
95     }
96             
97     /**
98      * Get the current head element
99      * @return The current 'first' element in list.
100      */
101     public Node getHead() { return head; }
102     /**
103      * Get the current tail element
104      * @return The current 'last' element in list.
105      */
106     public Node getTail() { return head.getPrev(); }
107
108     /**
109      * Moves <tt>nde</tt> to the head of the list (equivilent to
110      * remove(nde); add(nde); but faster.
111      */
112     public void touch(Node nde) {
113         if (nde == null) return;
114         nde.insertBefore(head);
115         head = nde;
116     }
117
118     public void add(int index, Node nde) {
119         if (nde == null) return;
120         if (index == 0) {
121               // This makes it the first element in the list.
122 nde.insertBefore(head);
123             head = nde;
124         } else if (index == size) {
125               // Because the list is circular this
126 // makes it the last element in the list.
127 nde.insertBefore(head);
128         } else {
129             Node after = head;
130             while (index != 0) {
131                 after = after.getNext();
132                 index--;
133             }
134             nde.insertBefore(after);
135         }
136         size++;
137     }
138
139     /**
140      * Adds <tt>nde</tt> to the head of the list.
141      * In perl this is called an 'unpop'. <tt>nde</tt> should
142      * not currently be part of any list.
143      * @param nde the node to add to the list.
144      */
145     public void add(Node nde) {
146         if (nde == null) return;
147         nde.insertBefore(head);
148         head = nde;
149         size++;
150     }
151         
152     /**
153      * Removes nde from the list it is part of (should be this
154      * one, otherwise results are undefined). If nde is the
155      * current head element, then the next element becomes head,
156      * if there are no more elements the list becomes empty.
157      * @param nde node to remove.
158      */
159     public void remove(Node nde) {
160         if (nde == null) return;
161         if (nde == head) {
162             if (head.getNext() == head)
163                 head = null; // Last node...
164 else
165                 head = head.getNext();
166         }
167         nde.unlink();
168         size--;
169     }
170
171     /**
172      * Removes 'head' from list and returns it. Returns null if list is empty.
173      * @return current head element, next element becomes head.
174      */
175     public Node pop() {
176         if (head == null) return null;
177             
178         Node nde = head;
179         remove(nde);
180         return nde;
181     }
182
183     /**
184      * Removes 'tail' from list and returns it. Returns null if list is empty.
185      * @return current tail element.
186      */
187     public Node unpush() {
188         if (head == null) return null;
189             
190         Node nde = getTail();
191         remove(nde);
192         return nde;
193     }
194
195
196
197     /**
198      * Adds <tt>nde</tt> to tail of list
199      */
200     public void push(Node nde) {
201         nde.insertBefore(head);
202         if (head == null) head = nde;
203         size++;
204     }
205
206     /**
207      * Adds <tt>nde</tt> to head of list
208      */
209     public void unpop(Node nde) {
210         nde.insertBefore(head);
211         head = nde;
212         size++;
213     }
214 }
215
216
Popular Tags