author | psandoz |
Fri, 09 Sep 2016 14:54:29 -0700 | |
changeset 40806 | 46132d430504 |
parent 32108 | aa5490a167ee |
child 44743 | f0bbd698c486 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
2 |
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. |
2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
2 | 24 |
*/ |
25 |
||
26 |
package java.util; |
|
27 |
||
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
28 |
import java.util.function.Consumer; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
29 |
|
2 | 30 |
/** |
7976
f273c0d04215
7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents:
7816
diff
changeset
|
31 |
* Doubly-linked list implementation of the {@code List} and {@code Deque} |
f273c0d04215
7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents:
7816
diff
changeset
|
32 |
* interfaces. Implements all optional list operations, and permits all |
f273c0d04215
7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents:
7816
diff
changeset
|
33 |
* elements (including {@code null}). |
2 | 34 |
* |
4184 | 35 |
* <p>All of the operations perform as could be expected for a doubly-linked |
2 | 36 |
* list. Operations that index into the list will traverse the list from |
4184 | 37 |
* the beginning or the end, whichever is closer to the specified index. |
2 | 38 |
* |
39 |
* <p><strong>Note that this implementation is not synchronized.</strong> |
|
40 |
* If multiple threads access a linked list concurrently, and at least |
|
41 |
* one of the threads modifies the list structurally, it <i>must</i> be |
|
42 |
* synchronized externally. (A structural modification is any operation |
|
43 |
* that adds or deletes one or more elements; merely setting the value of |
|
44 |
* an element is not a structural modification.) This is typically |
|
45 |
* accomplished by synchronizing on some object that naturally |
|
46 |
* encapsulates the list. |
|
47 |
* |
|
48 |
* If no such object exists, the list should be "wrapped" using the |
|
49 |
* {@link Collections#synchronizedList Collections.synchronizedList} |
|
50 |
* method. This is best done at creation time, to prevent accidental |
|
51 |
* unsynchronized access to the list:<pre> |
|
52 |
* List list = Collections.synchronizedList(new LinkedList(...));</pre> |
|
53 |
* |
|
4184 | 54 |
* <p>The iterators returned by this class's {@code iterator} and |
55 |
* {@code listIterator} methods are <i>fail-fast</i>: if the list is |
|
2 | 56 |
* structurally modified at any time after the iterator is created, in |
4184 | 57 |
* any way except through the Iterator's own {@code remove} or |
58 |
* {@code add} methods, the iterator will throw a {@link |
|
2 | 59 |
* ConcurrentModificationException}. Thus, in the face of concurrent |
60 |
* modification, the iterator fails quickly and cleanly, rather than |
|
61 |
* risking arbitrary, non-deterministic behavior at an undetermined |
|
62 |
* time in the future. |
|
63 |
* |
|
64 |
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed |
|
65 |
* as it is, generally speaking, impossible to make any hard guarantees in the |
|
66 |
* presence of unsynchronized concurrent modification. Fail-fast iterators |
|
4184 | 67 |
* throw {@code ConcurrentModificationException} on a best-effort basis. |
2 | 68 |
* Therefore, it would be wrong to write a program that depended on this |
69 |
* exception for its correctness: <i>the fail-fast behavior of iterators |
|
70 |
* should be used only to detect bugs.</i> |
|
71 |
* |
|
72 |
* <p>This class is a member of the |
|
73 |
* <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
|
74 |
* Java Collections Framework</a>. |
|
75 |
* |
|
76 |
* @author Josh Bloch |
|
77 |
* @see List |
|
78 |
* @see ArrayList |
|
79 |
* @since 1.2 |
|
80 |
* @param <E> the type of elements held in this collection |
|
81 |
*/ |
|
82 |
||
83 |
public class LinkedList<E> |
|
84 |
extends AbstractSequentialList<E> |
|
85 |
implements List<E>, Deque<E>, Cloneable, java.io.Serializable |
|
86 |
{ |
|
4184 | 87 |
transient int size = 0; |
88 |
||
89 |
/** |
|
90 |
* Pointer to first node. |
|
91 |
*/ |
|
92 |
transient Node<E> first; |
|
93 |
||
94 |
/** |
|
95 |
* Pointer to last node. |
|
96 |
*/ |
|
97 |
transient Node<E> last; |
|
2 | 98 |
|
31425
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
99 |
/* |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
100 |
void dataStructureInvariants() { |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
101 |
assert (size == 0) |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
102 |
? (first == null && last == null) |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
103 |
: (first.prev == null && last.next == null); |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
104 |
} |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
105 |
*/ |
276b895af81c
8050091: (coll) LinkedList has incorrect implementation comment
martin
parents:
26451
diff
changeset
|
106 |
|
2 | 107 |
/** |
108 |
* Constructs an empty list. |
|
109 |
*/ |
|
110 |
public LinkedList() { |
|
111 |
} |
|
112 |
||
113 |
/** |
|
114 |
* Constructs a list containing the elements of the specified |
|
115 |
* collection, in the order they are returned by the collection's |
|
116 |
* iterator. |
|
117 |
* |
|
118 |
* @param c the collection whose elements are to be placed into this list |
|
119 |
* @throws NullPointerException if the specified collection is null |
|
120 |
*/ |
|
121 |
public LinkedList(Collection<? extends E> c) { |
|
122 |
this(); |
|
123 |
addAll(c); |
|
124 |
} |
|
125 |
||
126 |
/** |
|
4184 | 127 |
* Links e as first element. |
128 |
*/ |
|
129 |
private void linkFirst(E e) { |
|
130 |
final Node<E> f = first; |
|
7803
56bc97d69d93
6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents:
6124
diff
changeset
|
131 |
final Node<E> newNode = new Node<>(null, e, f); |
4184 | 132 |
first = newNode; |
133 |
if (f == null) |
|
134 |
last = newNode; |
|
135 |
else |
|
136 |
f.prev = newNode; |
|
137 |
size++; |
|
138 |
modCount++; |
|
139 |
} |
|
140 |
||
141 |
/** |
|
142 |
* Links e as last element. |
|
143 |
*/ |
|
144 |
void linkLast(E e) { |
|
145 |
final Node<E> l = last; |
|
7803
56bc97d69d93
6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents:
6124
diff
changeset
|
146 |
final Node<E> newNode = new Node<>(l, e, null); |
4184 | 147 |
last = newNode; |
148 |
if (l == null) |
|
149 |
first = newNode; |
|
150 |
else |
|
151 |
l.next = newNode; |
|
152 |
size++; |
|
153 |
modCount++; |
|
154 |
} |
|
155 |
||
156 |
/** |
|
157 |
* Inserts element e before non-null Node succ. |
|
158 |
*/ |
|
159 |
void linkBefore(E e, Node<E> succ) { |
|
160 |
// assert succ != null; |
|
161 |
final Node<E> pred = succ.prev; |
|
7803
56bc97d69d93
6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents:
6124
diff
changeset
|
162 |
final Node<E> newNode = new Node<>(pred, e, succ); |
4184 | 163 |
succ.prev = newNode; |
164 |
if (pred == null) |
|
165 |
first = newNode; |
|
166 |
else |
|
167 |
pred.next = newNode; |
|
168 |
size++; |
|
169 |
modCount++; |
|
170 |
} |
|
171 |
||
172 |
/** |
|
173 |
* Unlinks non-null first node f. |
|
174 |
*/ |
|
175 |
private E unlinkFirst(Node<E> f) { |
|
176 |
// assert f == first && f != null; |
|
177 |
final E element = f.item; |
|
178 |
final Node<E> next = f.next; |
|
179 |
f.item = null; |
|
180 |
f.next = null; // help GC |
|
181 |
first = next; |
|
182 |
if (next == null) |
|
183 |
last = null; |
|
184 |
else |
|
185 |
next.prev = null; |
|
186 |
size--; |
|
187 |
modCount++; |
|
188 |
return element; |
|
189 |
} |
|
190 |
||
191 |
/** |
|
192 |
* Unlinks non-null last node l. |
|
193 |
*/ |
|
194 |
private E unlinkLast(Node<E> l) { |
|
195 |
// assert l == last && l != null; |
|
196 |
final E element = l.item; |
|
197 |
final Node<E> prev = l.prev; |
|
198 |
l.item = null; |
|
199 |
l.prev = null; // help GC |
|
200 |
last = prev; |
|
201 |
if (prev == null) |
|
202 |
first = null; |
|
203 |
else |
|
204 |
prev.next = null; |
|
205 |
size--; |
|
206 |
modCount++; |
|
207 |
return element; |
|
208 |
} |
|
209 |
||
210 |
/** |
|
211 |
* Unlinks non-null node x. |
|
212 |
*/ |
|
213 |
E unlink(Node<E> x) { |
|
214 |
// assert x != null; |
|
215 |
final E element = x.item; |
|
216 |
final Node<E> next = x.next; |
|
217 |
final Node<E> prev = x.prev; |
|
218 |
||
219 |
if (prev == null) { |
|
220 |
first = next; |
|
221 |
} else { |
|
222 |
prev.next = next; |
|
223 |
x.prev = null; |
|
224 |
} |
|
225 |
||
226 |
if (next == null) { |
|
227 |
last = prev; |
|
228 |
} else { |
|
229 |
next.prev = prev; |
|
230 |
x.next = null; |
|
231 |
} |
|
232 |
||
233 |
x.item = null; |
|
234 |
size--; |
|
235 |
modCount++; |
|
236 |
return element; |
|
237 |
} |
|
238 |
||
239 |
/** |
|
2 | 240 |
* Returns the first element in this list. |
241 |
* |
|
242 |
* @return the first element in this list |
|
243 |
* @throws NoSuchElementException if this list is empty |
|
244 |
*/ |
|
245 |
public E getFirst() { |
|
4184 | 246 |
final Node<E> f = first; |
247 |
if (f == null) |
|
2 | 248 |
throw new NoSuchElementException(); |
4184 | 249 |
return f.item; |
2 | 250 |
} |
251 |
||
252 |
/** |
|
253 |
* Returns the last element in this list. |
|
254 |
* |
|
255 |
* @return the last element in this list |
|
256 |
* @throws NoSuchElementException if this list is empty |
|
257 |
*/ |
|
7976
f273c0d04215
7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents:
7816
diff
changeset
|
258 |
public E getLast() { |
4184 | 259 |
final Node<E> l = last; |
260 |
if (l == null) |
|
2 | 261 |
throw new NoSuchElementException(); |
4184 | 262 |
return l.item; |
2 | 263 |
} |
264 |
||
265 |
/** |
|
266 |
* Removes and returns the first element from this list. |
|
267 |
* |
|
268 |
* @return the first element from this list |
|
269 |
* @throws NoSuchElementException if this list is empty |
|
270 |
*/ |
|
271 |
public E removeFirst() { |
|
4184 | 272 |
final Node<E> f = first; |
273 |
if (f == null) |
|
274 |
throw new NoSuchElementException(); |
|
275 |
return unlinkFirst(f); |
|
2 | 276 |
} |
277 |
||
278 |
/** |
|
279 |
* Removes and returns the last element from this list. |
|
280 |
* |
|
281 |
* @return the last element from this list |
|
282 |
* @throws NoSuchElementException if this list is empty |
|
283 |
*/ |
|
284 |
public E removeLast() { |
|
4184 | 285 |
final Node<E> l = last; |
286 |
if (l == null) |
|
287 |
throw new NoSuchElementException(); |
|
288 |
return unlinkLast(l); |
|
2 | 289 |
} |
290 |
||
291 |
/** |
|
292 |
* Inserts the specified element at the beginning of this list. |
|
293 |
* |
|
294 |
* @param e the element to add |
|
295 |
*/ |
|
296 |
public void addFirst(E e) { |
|
4184 | 297 |
linkFirst(e); |
2 | 298 |
} |
299 |
||
300 |
/** |
|
301 |
* Appends the specified element to the end of this list. |
|
302 |
* |
|
303 |
* <p>This method is equivalent to {@link #add}. |
|
304 |
* |
|
305 |
* @param e the element to add |
|
306 |
*/ |
|
307 |
public void addLast(E e) { |
|
4184 | 308 |
linkLast(e); |
2 | 309 |
} |
310 |
||
311 |
/** |
|
4184 | 312 |
* Returns {@code true} if this list contains the specified element. |
313 |
* More formally, returns {@code true} if and only if this list contains |
|
314 |
* at least one element {@code e} such that |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
31425
diff
changeset
|
315 |
* {@code Objects.equals(o, e)}. |
2 | 316 |
* |
317 |
* @param o element whose presence in this list is to be tested |
|
4184 | 318 |
* @return {@code true} if this list contains the specified element |
2 | 319 |
*/ |
320 |
public boolean contains(Object o) { |
|
26451 | 321 |
return indexOf(o) >= 0; |
2 | 322 |
} |
323 |
||
324 |
/** |
|
325 |
* Returns the number of elements in this list. |
|
326 |
* |
|
327 |
* @return the number of elements in this list |
|
328 |
*/ |
|
329 |
public int size() { |
|
330 |
return size; |
|
331 |
} |
|
332 |
||
333 |
/** |
|
334 |
* Appends the specified element to the end of this list. |
|
335 |
* |
|
336 |
* <p>This method is equivalent to {@link #addLast}. |
|
337 |
* |
|
338 |
* @param e element to be appended to this list |
|
4184 | 339 |
* @return {@code true} (as specified by {@link Collection#add}) |
2 | 340 |
*/ |
341 |
public boolean add(E e) { |
|
4184 | 342 |
linkLast(e); |
2 | 343 |
return true; |
344 |
} |
|
345 |
||
346 |
/** |
|
347 |
* Removes the first occurrence of the specified element from this list, |
|
348 |
* if it is present. If this list does not contain the element, it is |
|
349 |
* unchanged. More formally, removes the element with the lowest index |
|
4184 | 350 |
* {@code i} such that |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
31425
diff
changeset
|
351 |
* {@code Objects.equals(o, get(i))} |
4184 | 352 |
* (if such an element exists). Returns {@code true} if this list |
2 | 353 |
* contained the specified element (or equivalently, if this list |
354 |
* changed as a result of the call). |
|
355 |
* |
|
356 |
* @param o element to be removed from this list, if present |
|
4184 | 357 |
* @return {@code true} if this list contained the specified element |
2 | 358 |
*/ |
359 |
public boolean remove(Object o) { |
|
4184 | 360 |
if (o == null) { |
361 |
for (Node<E> x = first; x != null; x = x.next) { |
|
362 |
if (x.item == null) { |
|
363 |
unlink(x); |
|
2 | 364 |
return true; |
365 |
} |
|
366 |
} |
|
367 |
} else { |
|
4184 | 368 |
for (Node<E> x = first; x != null; x = x.next) { |
369 |
if (o.equals(x.item)) { |
|
370 |
unlink(x); |
|
2 | 371 |
return true; |
372 |
} |
|
373 |
} |
|
374 |
} |
|
375 |
return false; |
|
376 |
} |
|
377 |
||
378 |
/** |
|
379 |
* Appends all of the elements in the specified collection to the end of |
|
380 |
* this list, in the order that they are returned by the specified |
|
381 |
* collection's iterator. The behavior of this operation is undefined if |
|
382 |
* the specified collection is modified while the operation is in |
|
383 |
* progress. (Note that this will occur if the specified collection is |
|
384 |
* this list, and it's nonempty.) |
|
385 |
* |
|
386 |
* @param c collection containing elements to be added to this list |
|
4184 | 387 |
* @return {@code true} if this list changed as a result of the call |
2 | 388 |
* @throws NullPointerException if the specified collection is null |
389 |
*/ |
|
390 |
public boolean addAll(Collection<? extends E> c) { |
|
391 |
return addAll(size, c); |
|
392 |
} |
|
393 |
||
394 |
/** |
|
395 |
* Inserts all of the elements in the specified collection into this |
|
396 |
* list, starting at the specified position. Shifts the element |
|
397 |
* currently at that position (if any) and any subsequent elements to |
|
398 |
* the right (increases their indices). The new elements will appear |
|
399 |
* in the list in the order that they are returned by the |
|
400 |
* specified collection's iterator. |
|
401 |
* |
|
402 |
* @param index index at which to insert the first element |
|
403 |
* from the specified collection |
|
404 |
* @param c collection containing elements to be added to this list |
|
4184 | 405 |
* @return {@code true} if this list changed as a result of the call |
2 | 406 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
407 |
* @throws NullPointerException if the specified collection is null |
|
408 |
*/ |
|
409 |
public boolean addAll(int index, Collection<? extends E> c) { |
|
4184 | 410 |
checkPositionIndex(index); |
411 |
||
2 | 412 |
Object[] a = c.toArray(); |
413 |
int numNew = a.length; |
|
4184 | 414 |
if (numNew == 0) |
2 | 415 |
return false; |
4184 | 416 |
|
417 |
Node<E> pred, succ; |
|
418 |
if (index == size) { |
|
419 |
succ = null; |
|
420 |
pred = last; |
|
421 |
} else { |
|
422 |
succ = node(index); |
|
423 |
pred = succ.prev; |
|
424 |
} |
|
2 | 425 |
|
4184 | 426 |
for (Object o : a) { |
427 |
@SuppressWarnings("unchecked") E e = (E) o; |
|
7803
56bc97d69d93
6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents:
6124
diff
changeset
|
428 |
Node<E> newNode = new Node<>(pred, e, null); |
4184 | 429 |
if (pred == null) |
430 |
first = newNode; |
|
431 |
else |
|
432 |
pred.next = newNode; |
|
433 |
pred = newNode; |
|
2 | 434 |
} |
4184 | 435 |
|
436 |
if (succ == null) { |
|
437 |
last = pred; |
|
438 |
} else { |
|
439 |
pred.next = succ; |
|
440 |
succ.prev = pred; |
|
441 |
} |
|
2 | 442 |
|
443 |
size += numNew; |
|
4184 | 444 |
modCount++; |
2 | 445 |
return true; |
446 |
} |
|
447 |
||
448 |
/** |
|
449 |
* Removes all of the elements from this list. |
|
4184 | 450 |
* The list will be empty after this call returns. |
2 | 451 |
*/ |
452 |
public void clear() { |
|
4184 | 453 |
// Clearing all of the links between nodes is "unnecessary", but: |
454 |
// - helps a generational GC if the discarded nodes inhabit |
|
455 |
// more than one generation |
|
456 |
// - is sure to free memory even if there is a reachable Iterator |
|
457 |
for (Node<E> x = first; x != null; ) { |
|
458 |
Node<E> next = x.next; |
|
459 |
x.item = null; |
|
460 |
x.next = null; |
|
461 |
x.prev = null; |
|
462 |
x = next; |
|
2 | 463 |
} |
4184 | 464 |
first = last = null; |
2 | 465 |
size = 0; |
466 |
modCount++; |
|
467 |
} |
|
468 |
||
469 |
||
470 |
// Positional Access Operations |
|
471 |
||
472 |
/** |
|
473 |
* Returns the element at the specified position in this list. |
|
474 |
* |
|
475 |
* @param index index of the element to return |
|
476 |
* @return the element at the specified position in this list |
|
477 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
|
478 |
*/ |
|
479 |
public E get(int index) { |
|
4184 | 480 |
checkElementIndex(index); |
481 |
return node(index).item; |
|
2 | 482 |
} |
483 |
||
484 |
/** |
|
485 |
* Replaces the element at the specified position in this list with the |
|
486 |
* specified element. |
|
487 |
* |
|
488 |
* @param index index of the element to replace |
|
489 |
* @param element element to be stored at the specified position |
|
490 |
* @return the element previously at the specified position |
|
491 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
|
492 |
*/ |
|
493 |
public E set(int index, E element) { |
|
4184 | 494 |
checkElementIndex(index); |
495 |
Node<E> x = node(index); |
|
496 |
E oldVal = x.item; |
|
497 |
x.item = element; |
|
2 | 498 |
return oldVal; |
499 |
} |
|
500 |
||
501 |
/** |
|
502 |
* Inserts the specified element at the specified position in this list. |
|
503 |
* Shifts the element currently at that position (if any) and any |
|
504 |
* subsequent elements to the right (adds one to their indices). |
|
505 |
* |
|
506 |
* @param index index at which the specified element is to be inserted |
|
507 |
* @param element element to be inserted |
|
508 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
|
509 |
*/ |
|
510 |
public void add(int index, E element) { |
|
4184 | 511 |
checkPositionIndex(index); |
512 |
||
513 |
if (index == size) |
|
514 |
linkLast(element); |
|
515 |
else |
|
516 |
linkBefore(element, node(index)); |
|
2 | 517 |
} |
518 |
||
519 |
/** |
|
520 |
* Removes the element at the specified position in this list. Shifts any |
|
521 |
* subsequent elements to the left (subtracts one from their indices). |
|
522 |
* Returns the element that was removed from the list. |
|
523 |
* |
|
524 |
* @param index the index of the element to be removed |
|
525 |
* @return the element previously at the specified position |
|
526 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
|
527 |
*/ |
|
528 |
public E remove(int index) { |
|
4184 | 529 |
checkElementIndex(index); |
530 |
return unlink(node(index)); |
|
531 |
} |
|
532 |
||
533 |
/** |
|
534 |
* Tells if the argument is the index of an existing element. |
|
535 |
*/ |
|
536 |
private boolean isElementIndex(int index) { |
|
537 |
return index >= 0 && index < size; |
|
538 |
} |
|
539 |
||
540 |
/** |
|
541 |
* Tells if the argument is the index of a valid position for an |
|
542 |
* iterator or an add operation. |
|
543 |
*/ |
|
544 |
private boolean isPositionIndex(int index) { |
|
545 |
return index >= 0 && index <= size; |
|
2 | 546 |
} |
547 |
||
548 |
/** |
|
4184 | 549 |
* Constructs an IndexOutOfBoundsException detail message. |
550 |
* Of the many possible refactorings of the error handling code, |
|
551 |
* this "outlining" performs best with both server and client VMs. |
|
2 | 552 |
*/ |
4184 | 553 |
private String outOfBoundsMsg(int index) { |
554 |
return "Index: "+index+", Size: "+size; |
|
555 |
} |
|
556 |
||
557 |
private void checkElementIndex(int index) { |
|
558 |
if (!isElementIndex(index)) |
|
559 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
|
560 |
} |
|
561 |
||
562 |
private void checkPositionIndex(int index) { |
|
563 |
if (!isPositionIndex(index)) |
|
564 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
|
2 | 565 |
} |
566 |
||
4184 | 567 |
/** |
568 |
* Returns the (non-null) Node at the specified element index. |
|
569 |
*/ |
|
570 |
Node<E> node(int index) { |
|
571 |
// assert isElementIndex(index); |
|
572 |
||
573 |
if (index < (size >> 1)) { |
|
574 |
Node<E> x = first; |
|
575 |
for (int i = 0; i < index; i++) |
|
576 |
x = x.next; |
|
577 |
return x; |
|
578 |
} else { |
|
579 |
Node<E> x = last; |
|
580 |
for (int i = size - 1; i > index; i--) |
|
581 |
x = x.prev; |
|
582 |
return x; |
|
583 |
} |
|
584 |
} |
|
2 | 585 |
|
586 |
// Search Operations |
|
587 |
||
588 |
/** |
|
589 |
* Returns the index of the first occurrence of the specified element |
|
590 |
* in this list, or -1 if this list does not contain the element. |
|
4184 | 591 |
* More formally, returns the lowest index {@code i} such that |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
31425
diff
changeset
|
592 |
* {@code Objects.equals(o, get(i))}, |
2 | 593 |
* or -1 if there is no such index. |
594 |
* |
|
595 |
* @param o element to search for |
|
596 |
* @return the index of the first occurrence of the specified element in |
|
597 |
* this list, or -1 if this list does not contain the element |
|
598 |
*/ |
|
599 |
public int indexOf(Object o) { |
|
600 |
int index = 0; |
|
4184 | 601 |
if (o == null) { |
602 |
for (Node<E> x = first; x != null; x = x.next) { |
|
603 |
if (x.item == null) |
|
2 | 604 |
return index; |
605 |
index++; |
|
606 |
} |
|
607 |
} else { |
|
4184 | 608 |
for (Node<E> x = first; x != null; x = x.next) { |
609 |
if (o.equals(x.item)) |
|
2 | 610 |
return index; |
611 |
index++; |
|
612 |
} |
|
613 |
} |
|
614 |
return -1; |
|
615 |
} |
|
616 |
||
617 |
/** |
|
618 |
* Returns the index of the last occurrence of the specified element |
|
619 |
* in this list, or -1 if this list does not contain the element. |
|
4184 | 620 |
* More formally, returns the highest index {@code i} such that |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
31425
diff
changeset
|
621 |
* {@code Objects.equals(o, get(i))}, |
2 | 622 |
* or -1 if there is no such index. |
623 |
* |
|
624 |
* @param o element to search for |
|
625 |
* @return the index of the last occurrence of the specified element in |
|
626 |
* this list, or -1 if this list does not contain the element |
|
627 |
*/ |
|
628 |
public int lastIndexOf(Object o) { |
|
629 |
int index = size; |
|
4184 | 630 |
if (o == null) { |
631 |
for (Node<E> x = last; x != null; x = x.prev) { |
|
2 | 632 |
index--; |
4184 | 633 |
if (x.item == null) |
2 | 634 |
return index; |
635 |
} |
|
636 |
} else { |
|
4184 | 637 |
for (Node<E> x = last; x != null; x = x.prev) { |
2 | 638 |
index--; |
4184 | 639 |
if (o.equals(x.item)) |
2 | 640 |
return index; |
641 |
} |
|
642 |
} |
|
643 |
return -1; |
|
644 |
} |
|
645 |
||
646 |
// Queue operations. |
|
647 |
||
648 |
/** |
|
649 |
* Retrieves, but does not remove, the head (first element) of this list. |
|
4184 | 650 |
* |
651 |
* @return the head of this list, or {@code null} if this list is empty |
|
2 | 652 |
* @since 1.5 |
653 |
*/ |
|
654 |
public E peek() { |
|
4184 | 655 |
final Node<E> f = first; |
656 |
return (f == null) ? null : f.item; |
|
2 | 657 |
} |
658 |
||
659 |
/** |
|
660 |
* Retrieves, but does not remove, the head (first element) of this list. |
|
4184 | 661 |
* |
2 | 662 |
* @return the head of this list |
663 |
* @throws NoSuchElementException if this list is empty |
|
664 |
* @since 1.5 |
|
665 |
*/ |
|
666 |
public E element() { |
|
667 |
return getFirst(); |
|
668 |
} |
|
669 |
||
670 |
/** |
|
4184 | 671 |
* Retrieves and removes the head (first element) of this list. |
672 |
* |
|
673 |
* @return the head of this list, or {@code null} if this list is empty |
|
2 | 674 |
* @since 1.5 |
675 |
*/ |
|
676 |
public E poll() { |
|
4184 | 677 |
final Node<E> f = first; |
678 |
return (f == null) ? null : unlinkFirst(f); |
|
2 | 679 |
} |
680 |
||
681 |
/** |
|
682 |
* Retrieves and removes the head (first element) of this list. |
|
683 |
* |
|
684 |
* @return the head of this list |
|
685 |
* @throws NoSuchElementException if this list is empty |
|
686 |
* @since 1.5 |
|
687 |
*/ |
|
688 |
public E remove() { |
|
689 |
return removeFirst(); |
|
690 |
} |
|
691 |
||
692 |
/** |
|
693 |
* Adds the specified element as the tail (last element) of this list. |
|
694 |
* |
|
695 |
* @param e the element to add |
|
4184 | 696 |
* @return {@code true} (as specified by {@link Queue#offer}) |
2 | 697 |
* @since 1.5 |
698 |
*/ |
|
699 |
public boolean offer(E e) { |
|
700 |
return add(e); |
|
701 |
} |
|
702 |
||
703 |
// Deque operations |
|
704 |
/** |
|
705 |
* Inserts the specified element at the front of this list. |
|
706 |
* |
|
707 |
* @param e the element to insert |
|
4184 | 708 |
* @return {@code true} (as specified by {@link Deque#offerFirst}) |
2 | 709 |
* @since 1.6 |
710 |
*/ |
|
711 |
public boolean offerFirst(E e) { |
|
712 |
addFirst(e); |
|
713 |
return true; |
|
714 |
} |
|
715 |
||
716 |
/** |
|
717 |
* Inserts the specified element at the end of this list. |
|
718 |
* |
|
719 |
* @param e the element to insert |
|
4184 | 720 |
* @return {@code true} (as specified by {@link Deque#offerLast}) |
2 | 721 |
* @since 1.6 |
722 |
*/ |
|
723 |
public boolean offerLast(E e) { |
|
724 |
addLast(e); |
|
725 |
return true; |
|
726 |
} |
|
727 |
||
728 |
/** |
|
729 |
* Retrieves, but does not remove, the first element of this list, |
|
4184 | 730 |
* or returns {@code null} if this list is empty. |
2 | 731 |
* |
4184 | 732 |
* @return the first element of this list, or {@code null} |
2 | 733 |
* if this list is empty |
734 |
* @since 1.6 |
|
735 |
*/ |
|
736 |
public E peekFirst() { |
|
4184 | 737 |
final Node<E> f = first; |
738 |
return (f == null) ? null : f.item; |
|
739 |
} |
|
2 | 740 |
|
741 |
/** |
|
742 |
* Retrieves, but does not remove, the last element of this list, |
|
4184 | 743 |
* or returns {@code null} if this list is empty. |
2 | 744 |
* |
4184 | 745 |
* @return the last element of this list, or {@code null} |
2 | 746 |
* if this list is empty |
747 |
* @since 1.6 |
|
748 |
*/ |
|
749 |
public E peekLast() { |
|
4184 | 750 |
final Node<E> l = last; |
751 |
return (l == null) ? null : l.item; |
|
2 | 752 |
} |
753 |
||
754 |
/** |
|
755 |
* Retrieves and removes the first element of this list, |
|
4184 | 756 |
* or returns {@code null} if this list is empty. |
2 | 757 |
* |
4184 | 758 |
* @return the first element of this list, or {@code null} if |
2 | 759 |
* this list is empty |
760 |
* @since 1.6 |
|
761 |
*/ |
|
762 |
public E pollFirst() { |
|
4184 | 763 |
final Node<E> f = first; |
764 |
return (f == null) ? null : unlinkFirst(f); |
|
2 | 765 |
} |
766 |
||
767 |
/** |
|
768 |
* Retrieves and removes the last element of this list, |
|
4184 | 769 |
* or returns {@code null} if this list is empty. |
2 | 770 |
* |
4184 | 771 |
* @return the last element of this list, or {@code null} if |
2 | 772 |
* this list is empty |
773 |
* @since 1.6 |
|
774 |
*/ |
|
775 |
public E pollLast() { |
|
4184 | 776 |
final Node<E> l = last; |
777 |
return (l == null) ? null : unlinkLast(l); |
|
2 | 778 |
} |
779 |
||
780 |
/** |
|
781 |
* Pushes an element onto the stack represented by this list. In other |
|
782 |
* words, inserts the element at the front of this list. |
|
783 |
* |
|
784 |
* <p>This method is equivalent to {@link #addFirst}. |
|
785 |
* |
|
786 |
* @param e the element to push |
|
787 |
* @since 1.6 |
|
788 |
*/ |
|
789 |
public void push(E e) { |
|
790 |
addFirst(e); |
|
791 |
} |
|
792 |
||
793 |
/** |
|
794 |
* Pops an element from the stack represented by this list. In other |
|
795 |
* words, removes and returns the first element of this list. |
|
796 |
* |
|
797 |
* <p>This method is equivalent to {@link #removeFirst()}. |
|
798 |
* |
|
799 |
* @return the element at the front of this list (which is the top |
|
800 |
* of the stack represented by this list) |
|
801 |
* @throws NoSuchElementException if this list is empty |
|
802 |
* @since 1.6 |
|
803 |
*/ |
|
804 |
public E pop() { |
|
805 |
return removeFirst(); |
|
806 |
} |
|
807 |
||
808 |
/** |
|
809 |
* Removes the first occurrence of the specified element in this |
|
810 |
* list (when traversing the list from head to tail). If the list |
|
811 |
* does not contain the element, it is unchanged. |
|
812 |
* |
|
813 |
* @param o element to be removed from this list, if present |
|
4184 | 814 |
* @return {@code true} if the list contained the specified element |
2 | 815 |
* @since 1.6 |
816 |
*/ |
|
817 |
public boolean removeFirstOccurrence(Object o) { |
|
818 |
return remove(o); |
|
819 |
} |
|
820 |
||
821 |
/** |
|
822 |
* Removes the last occurrence of the specified element in this |
|
823 |
* list (when traversing the list from head to tail). If the list |
|
824 |
* does not contain the element, it is unchanged. |
|
825 |
* |
|
826 |
* @param o element to be removed from this list, if present |
|
4184 | 827 |
* @return {@code true} if the list contained the specified element |
2 | 828 |
* @since 1.6 |
829 |
*/ |
|
830 |
public boolean removeLastOccurrence(Object o) { |
|
4184 | 831 |
if (o == null) { |
832 |
for (Node<E> x = last; x != null; x = x.prev) { |
|
833 |
if (x.item == null) { |
|
834 |
unlink(x); |
|
2 | 835 |
return true; |
836 |
} |
|
837 |
} |
|
838 |
} else { |
|
4184 | 839 |
for (Node<E> x = last; x != null; x = x.prev) { |
840 |
if (o.equals(x.item)) { |
|
841 |
unlink(x); |
|
2 | 842 |
return true; |
843 |
} |
|
844 |
} |
|
845 |
} |
|
846 |
return false; |
|
847 |
} |
|
848 |
||
849 |
/** |
|
850 |
* Returns a list-iterator of the elements in this list (in proper |
|
851 |
* sequence), starting at the specified position in the list. |
|
4184 | 852 |
* Obeys the general contract of {@code List.listIterator(int)}.<p> |
2 | 853 |
* |
854 |
* The list-iterator is <i>fail-fast</i>: if the list is structurally |
|
855 |
* modified at any time after the Iterator is created, in any way except |
|
4184 | 856 |
* through the list-iterator's own {@code remove} or {@code add} |
2 | 857 |
* methods, the list-iterator will throw a |
4184 | 858 |
* {@code ConcurrentModificationException}. Thus, in the face of |
2 | 859 |
* concurrent modification, the iterator fails quickly and cleanly, rather |
860 |
* than risking arbitrary, non-deterministic behavior at an undetermined |
|
861 |
* time in the future. |
|
862 |
* |
|
863 |
* @param index index of the first element to be returned from the |
|
4184 | 864 |
* list-iterator (by a call to {@code next}) |
2 | 865 |
* @return a ListIterator of the elements in this list (in proper |
866 |
* sequence), starting at the specified position in the list |
|
867 |
* @throws IndexOutOfBoundsException {@inheritDoc} |
|
868 |
* @see List#listIterator(int) |
|
869 |
*/ |
|
870 |
public ListIterator<E> listIterator(int index) { |
|
4184 | 871 |
checkPositionIndex(index); |
2 | 872 |
return new ListItr(index); |
873 |
} |
|
874 |
||
875 |
private class ListItr implements ListIterator<E> { |
|
23746 | 876 |
private Node<E> lastReturned; |
4184 | 877 |
private Node<E> next; |
2 | 878 |
private int nextIndex; |
879 |
private int expectedModCount = modCount; |
|
880 |
||
881 |
ListItr(int index) { |
|
4184 | 882 |
// assert isPositionIndex(index); |
883 |
next = (index == size) ? null : node(index); |
|
884 |
nextIndex = index; |
|
2 | 885 |
} |
886 |
||
887 |
public boolean hasNext() { |
|
4184 | 888 |
return nextIndex < size; |
2 | 889 |
} |
890 |
||
891 |
public E next() { |
|
892 |
checkForComodification(); |
|
4184 | 893 |
if (!hasNext()) |
2 | 894 |
throw new NoSuchElementException(); |
895 |
||
896 |
lastReturned = next; |
|
897 |
next = next.next; |
|
898 |
nextIndex++; |
|
4184 | 899 |
return lastReturned.item; |
2 | 900 |
} |
901 |
||
902 |
public boolean hasPrevious() { |
|
4184 | 903 |
return nextIndex > 0; |
2 | 904 |
} |
905 |
||
906 |
public E previous() { |
|
4184 | 907 |
checkForComodification(); |
908 |
if (!hasPrevious()) |
|
2 | 909 |
throw new NoSuchElementException(); |
910 |
||
4184 | 911 |
lastReturned = next = (next == null) ? last : next.prev; |
2 | 912 |
nextIndex--; |
4184 | 913 |
return lastReturned.item; |
2 | 914 |
} |
915 |
||
916 |
public int nextIndex() { |
|
917 |
return nextIndex; |
|
918 |
} |
|
919 |
||
920 |
public int previousIndex() { |
|
4184 | 921 |
return nextIndex - 1; |
2 | 922 |
} |
923 |
||
924 |
public void remove() { |
|
925 |
checkForComodification(); |
|
4184 | 926 |
if (lastReturned == null) |
2 | 927 |
throw new IllegalStateException(); |
4184 | 928 |
|
929 |
Node<E> lastNext = lastReturned.next; |
|
930 |
unlink(lastReturned); |
|
931 |
if (next == lastReturned) |
|
2 | 932 |
next = lastNext; |
933 |
else |
|
934 |
nextIndex--; |
|
4184 | 935 |
lastReturned = null; |
2 | 936 |
expectedModCount++; |
937 |
} |
|
938 |
||
939 |
public void set(E e) { |
|
4184 | 940 |
if (lastReturned == null) |
2 | 941 |
throw new IllegalStateException(); |
942 |
checkForComodification(); |
|
4184 | 943 |
lastReturned.item = e; |
2 | 944 |
} |
945 |
||
946 |
public void add(E e) { |
|
947 |
checkForComodification(); |
|
4184 | 948 |
lastReturned = null; |
949 |
if (next == null) |
|
950 |
linkLast(e); |
|
951 |
else |
|
952 |
linkBefore(e, next); |
|
2 | 953 |
nextIndex++; |
954 |
expectedModCount++; |
|
955 |
} |
|
956 |
||
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
957 |
public void forEachRemaining(Consumer<? super E> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
958 |
Objects.requireNonNull(action); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
959 |
while (modCount == expectedModCount && nextIndex < size) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
960 |
action.accept(next.item); |
17432
efdf6eb85a17
8013150: Iterator.remove and forEachRemaining relationship not specified
mduigou
parents:
17180
diff
changeset
|
961 |
lastReturned = next; |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
962 |
next = next.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
963 |
nextIndex++; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
964 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
965 |
checkForComodification(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
966 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
967 |
|
2 | 968 |
final void checkForComodification() { |
969 |
if (modCount != expectedModCount) |
|
970 |
throw new ConcurrentModificationException(); |
|
971 |
} |
|
972 |
} |
|
973 |
||
4184 | 974 |
private static class Node<E> { |
975 |
E item; |
|
976 |
Node<E> next; |
|
977 |
Node<E> prev; |
|
2 | 978 |
|
4184 | 979 |
Node(Node<E> prev, E element, Node<E> next) { |
980 |
this.item = element; |
|
981 |
this.next = next; |
|
982 |
this.prev = prev; |
|
983 |
} |
|
2 | 984 |
} |
985 |
||
986 |
/** |
|
987 |
* @since 1.6 |
|
988 |
*/ |
|
989 |
public Iterator<E> descendingIterator() { |
|
990 |
return new DescendingIterator(); |
|
991 |
} |
|
992 |
||
4184 | 993 |
/** |
994 |
* Adapter to provide descending iterators via ListItr.previous |
|
995 |
*/ |
|
996 |
private class DescendingIterator implements Iterator<E> { |
|
997 |
private final ListItr itr = new ListItr(size()); |
|
2 | 998 |
public boolean hasNext() { |
999 |
return itr.hasPrevious(); |
|
1000 |
} |
|
1001 |
public E next() { |
|
1002 |
return itr.previous(); |
|
1003 |
} |
|
1004 |
public void remove() { |
|
1005 |
itr.remove(); |
|
1006 |
} |
|
1007 |
} |
|
1008 |
||
4184 | 1009 |
@SuppressWarnings("unchecked") |
1010 |
private LinkedList<E> superClone() { |
|
2 | 1011 |
try { |
4184 | 1012 |
return (LinkedList<E>) super.clone(); |
2 | 1013 |
} catch (CloneNotSupportedException e) { |
10419
12c063b39232
7084245: Update usages of InternalError to use exception chaining
sherman
parents:
9035
diff
changeset
|
1014 |
throw new InternalError(e); |
2 | 1015 |
} |
4184 | 1016 |
} |
1017 |
||
1018 |
/** |
|
1019 |
* Returns a shallow copy of this {@code LinkedList}. (The elements |
|
1020 |
* themselves are not cloned.) |
|
1021 |
* |
|
1022 |
* @return a shallow copy of this {@code LinkedList} instance |
|
1023 |
*/ |
|
1024 |
public Object clone() { |
|
1025 |
LinkedList<E> clone = superClone(); |
|
2 | 1026 |
|
1027 |
// Put clone into "virgin" state |
|
4184 | 1028 |
clone.first = clone.last = null; |
2 | 1029 |
clone.size = 0; |
1030 |
clone.modCount = 0; |
|
1031 |
||
1032 |
// Initialize clone with our elements |
|
4184 | 1033 |
for (Node<E> x = first; x != null; x = x.next) |
1034 |
clone.add(x.item); |
|
2 | 1035 |
|
1036 |
return clone; |
|
1037 |
} |
|
1038 |
||
1039 |
/** |
|
1040 |
* Returns an array containing all of the elements in this list |
|
1041 |
* in proper sequence (from first to last element). |
|
1042 |
* |
|
1043 |
* <p>The returned array will be "safe" in that no references to it are |
|
1044 |
* maintained by this list. (In other words, this method must allocate |
|
1045 |
* a new array). The caller is thus free to modify the returned array. |
|
1046 |
* |
|
1047 |
* <p>This method acts as bridge between array-based and collection-based |
|
1048 |
* APIs. |
|
1049 |
* |
|
1050 |
* @return an array containing all of the elements in this list |
|
1051 |
* in proper sequence |
|
1052 |
*/ |
|
1053 |
public Object[] toArray() { |
|
1054 |
Object[] result = new Object[size]; |
|
1055 |
int i = 0; |
|
4184 | 1056 |
for (Node<E> x = first; x != null; x = x.next) |
1057 |
result[i++] = x.item; |
|
2 | 1058 |
return result; |
1059 |
} |
|
1060 |
||
1061 |
/** |
|
1062 |
* Returns an array containing all of the elements in this list in |
|
1063 |
* proper sequence (from first to last element); the runtime type of |
|
1064 |
* the returned array is that of the specified array. If the list fits |
|
1065 |
* in the specified array, it is returned therein. Otherwise, a new |
|
1066 |
* array is allocated with the runtime type of the specified array and |
|
1067 |
* the size of this list. |
|
1068 |
* |
|
1069 |
* <p>If the list fits in the specified array with room to spare (i.e., |
|
1070 |
* the array has more elements than the list), the element in the array |
|
4184 | 1071 |
* immediately following the end of the list is set to {@code null}. |
2 | 1072 |
* (This is useful in determining the length of the list <i>only</i> if |
1073 |
* the caller knows that the list does not contain any null elements.) |
|
1074 |
* |
|
1075 |
* <p>Like the {@link #toArray()} method, this method acts as bridge between |
|
1076 |
* array-based and collection-based APIs. Further, this method allows |
|
1077 |
* precise control over the runtime type of the output array, and may, |
|
1078 |
* under certain circumstances, be used to save allocation costs. |
|
1079 |
* |
|
4184 | 1080 |
* <p>Suppose {@code x} is a list known to contain only strings. |
2 | 1081 |
* The following code can be used to dump the list into a newly |
4184 | 1082 |
* allocated array of {@code String}: |
2 | 1083 |
* |
1084 |
* <pre> |
|
1085 |
* String[] y = x.toArray(new String[0]);</pre> |
|
1086 |
* |
|
4184 | 1087 |
* Note that {@code toArray(new Object[0])} is identical in function to |
1088 |
* {@code toArray()}. |
|
2 | 1089 |
* |
1090 |
* @param a the array into which the elements of the list are to |
|
1091 |
* be stored, if it is big enough; otherwise, a new array of the |
|
1092 |
* same runtime type is allocated for this purpose. |
|
1093 |
* @return an array containing the elements of the list |
|
1094 |
* @throws ArrayStoreException if the runtime type of the specified array |
|
1095 |
* is not a supertype of the runtime type of every element in |
|
1096 |
* this list |
|
1097 |
* @throws NullPointerException if the specified array is null |
|
1098 |
*/ |
|
4184 | 1099 |
@SuppressWarnings("unchecked") |
2 | 1100 |
public <T> T[] toArray(T[] a) { |
1101 |
if (a.length < size) |
|
1102 |
a = (T[])java.lang.reflect.Array.newInstance( |
|
1103 |
a.getClass().getComponentType(), size); |
|
1104 |
int i = 0; |
|
1105 |
Object[] result = a; |
|
4184 | 1106 |
for (Node<E> x = first; x != null; x = x.next) |
1107 |
result[i++] = x.item; |
|
2 | 1108 |
|
1109 |
if (a.length > size) |
|
1110 |
a[size] = null; |
|
1111 |
||
1112 |
return a; |
|
1113 |
} |
|
1114 |
||
1115 |
private static final long serialVersionUID = 876323262645176354L; |
|
1116 |
||
1117 |
/** |
|
4184 | 1118 |
* Saves the state of this {@code LinkedList} instance to a stream |
1119 |
* (that is, serializes it). |
|
2 | 1120 |
* |
1121 |
* @serialData The size of the list (the number of elements it |
|
1122 |
* contains) is emitted (int), followed by all of its |
|
1123 |
* elements (each an Object) in the proper order. |
|
1124 |
*/ |
|
1125 |
private void writeObject(java.io.ObjectOutputStream s) |
|
1126 |
throws java.io.IOException { |
|
1127 |
// Write out any hidden serialization magic |
|
1128 |
s.defaultWriteObject(); |
|
1129 |
||
1130 |
// Write out size |
|
1131 |
s.writeInt(size); |
|
1132 |
||
1133 |
// Write out all elements in the proper order. |
|
4184 | 1134 |
for (Node<E> x = first; x != null; x = x.next) |
1135 |
s.writeObject(x.item); |
|
2 | 1136 |
} |
1137 |
||
1138 |
/** |
|
4184 | 1139 |
* Reconstitutes this {@code LinkedList} instance from a stream |
1140 |
* (that is, deserializes it). |
|
2 | 1141 |
*/ |
4184 | 1142 |
@SuppressWarnings("unchecked") |
2 | 1143 |
private void readObject(java.io.ObjectInputStream s) |
1144 |
throws java.io.IOException, ClassNotFoundException { |
|
1145 |
// Read in any hidden serialization magic |
|
1146 |
s.defaultReadObject(); |
|
1147 |
||
1148 |
// Read in size |
|
1149 |
int size = s.readInt(); |
|
1150 |
||
1151 |
// Read in all elements in the proper order. |
|
4184 | 1152 |
for (int i = 0; i < size; i++) |
1153 |
linkLast((E)s.readObject()); |
|
2 | 1154 |
} |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1155 |
|
19435
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1156 |
/** |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1157 |
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1158 |
* and <em>fail-fast</em> {@link Spliterator} over the elements in this |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1159 |
* list. |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1160 |
* |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1161 |
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1162 |
* {@link Spliterator#ORDERED}. Overriding implementations should document |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1163 |
* the reporting of additional characteristic values. |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1164 |
* |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1165 |
* @implNote |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1166 |
* The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED} |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1167 |
* and implements {@code trySplit} to permit limited parallelism.. |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1168 |
* |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1169 |
* @return a {@code Spliterator} over the elements in this list |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1170 |
* @since 1.8 |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1171 |
*/ |
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
18788
diff
changeset
|
1172 |
@Override |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1173 |
public Spliterator<E> spliterator() { |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
19435
diff
changeset
|
1174 |
return new LLSpliterator<>(this, -1, 0); |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1175 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1176 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1177 |
/** A customized variant of Spliterators.IteratorSpliterator */ |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1178 |
static final class LLSpliterator<E> implements Spliterator<E> { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1179 |
static final int BATCH_UNIT = 1 << 10; // batch array size increment |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1180 |
static final int MAX_BATCH = 1 << 25; // max batch array size; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1181 |
final LinkedList<E> list; // null OK unless traversed |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1182 |
Node<E> current; // current node; null until initialized |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1183 |
int est; // size estimate; -1 until first needed |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1184 |
int expectedModCount; // initialized when est set |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1185 |
int batch; // batch size for splits |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1186 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1187 |
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1188 |
this.list = list; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1189 |
this.est = est; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1190 |
this.expectedModCount = expectedModCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1191 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1192 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1193 |
final int getEst() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1194 |
int s; // force initialization |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1195 |
final LinkedList<E> lst; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1196 |
if ((s = est) < 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1197 |
if ((lst = list) == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1198 |
s = est = 0; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1199 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1200 |
expectedModCount = lst.modCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1201 |
current = lst.first; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1202 |
s = est = lst.size; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1203 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1204 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1205 |
return s; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1206 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1207 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1208 |
public long estimateSize() { return (long) getEst(); } |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1209 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1210 |
public Spliterator<E> trySplit() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1211 |
Node<E> p; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1212 |
int s = getEst(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1213 |
if (s > 1 && (p = current) != null) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1214 |
int n = batch + BATCH_UNIT; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1215 |
if (n > s) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1216 |
n = s; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1217 |
if (n > MAX_BATCH) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1218 |
n = MAX_BATCH; |
18788
1bfd5f623662
8017141: java.util/stream Spliterators from sequential sources should not catch OOME
henryjen
parents:
17432
diff
changeset
|
1219 |
Object[] a = new Object[n]; |
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1220 |
int j = 0; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1221 |
do { a[j++] = p.item; } while ((p = p.next) != null && j < n); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1222 |
current = p; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1223 |
batch = j; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1224 |
est = s - j; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1225 |
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1226 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1227 |
return null; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1228 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1229 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1230 |
public void forEachRemaining(Consumer<? super E> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1231 |
Node<E> p; int n; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1232 |
if (action == null) throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1233 |
if ((n = getEst()) > 0 && (p = current) != null) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1234 |
current = null; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1235 |
est = 0; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1236 |
do { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1237 |
E e = p.item; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1238 |
p = p.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1239 |
action.accept(e); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1240 |
} while (p != null && --n > 0); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1241 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1242 |
if (list.modCount != expectedModCount) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1243 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1244 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1245 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1246 |
public boolean tryAdvance(Consumer<? super E> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1247 |
Node<E> p; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1248 |
if (action == null) throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1249 |
if (getEst() > 0 && (p = current) != null) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1250 |
--est; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1251 |
E e = p.item; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1252 |
current = p.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1253 |
action.accept(e); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1254 |
if (list.modCount != expectedModCount) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1255 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1256 |
return true; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1257 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1258 |
return false; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1259 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1260 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1261 |
public int characteristics() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1262 |
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1263 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1264 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
10419
diff
changeset
|
1265 |
|
2 | 1266 |
} |