OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of dart.collection; | 5 part of dart.collection; |
6 | 6 |
7 /** | 7 /** |
8 * A specialized double-linked list of elements that extends [LinkedListEntry]. | 8 * A specialized double-linked list of elements that extends [LinkedListEntry]. |
9 * | 9 * |
10 * This is not a generic data structure. It only accepts elements that extend | 10 * This is not a generic data structure. It only accepts elements that extend |
11 * the [LinkedListEntry] class. See the [Queue] implementations for | 11 * the [LinkedListEntry] class. See the [Queue] implementations for |
12 * generic collections that allow constant time adding and removing at the ends. | 12 * generic collections that allow constant time adding and removing at the ends. |
13 * | 13 * |
14 * This is not a [List] implementation. Despite its name, this class does not | 14 * This is not a [List] implementation. Despite its name, this class does not |
15 * implement the [List] interface. It does not allow constant time lookup by | 15 * implement the [List] interface. It does not allow constant time lookup by |
16 * index. | 16 * index. |
17 * | 17 * |
18 * Because the elements themselves contain the links of this linked list, | 18 * Because the elements themselves contain the links of this linked list, |
19 * each element can be in only one list at a time. To add an element to another | 19 * each element can be in only one list at a time. To add an element to another |
20 * list, it must first be removed from its current list (if any). | 20 * list, it must first be removed from its current list (if any). |
21 * | 21 * |
22 * In return, each element knows its own place in the linked list, as well as | 22 * In return, each element knows its own place in the linked list, as well as |
23 * which list it is in. This allows constant time [LinkedListEntry.addAfter], | 23 * which list it is in. This allows constant time [LinkedListEntry.insertAfter], |
24 * [LinkedListEntry.addBefore] and [LinkedListEntry.unlink] operations | 24 * [LinkedListEntry.insertBefore] and [LinkedListEntry.unlink] operations |
25 * when all you have is the element. | 25 * when all you have is the element. |
26 * | 26 * |
27 * A `LinkedList` also allows constant time adding and removing at either end, | 27 * A `LinkedList` also allows constant time adding and removing at either end, |
28 * and a constant time length getter. | 28 * and a constant time length getter. |
29 */ | 29 */ |
30 class LinkedList<E extends LinkedListEntry<E>> extends Iterable<E> { | 30 class LinkedList<E extends LinkedListEntry<E>> extends Iterable<E> { |
31 int _modificationCount = 0; | 31 int _modificationCount = 0; |
32 int _length = 0; | 32 int _length = 0; |
33 E _first; | 33 E _first; |
34 | 34 |
(...skipping 249 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
284 /** | 284 /** |
285 * Insert an element before this element in this element's linked list. | 285 * Insert an element before this element in this element's linked list. |
286 * | 286 * |
287 * This entry must be in a linked list when this method is called. | 287 * This entry must be in a linked list when this method is called. |
288 * The [entry] must not be in a linked list. | 288 * The [entry] must not be in a linked list. |
289 */ | 289 */ |
290 void insertBefore(E entry) { | 290 void insertBefore(E entry) { |
291 _list._insertBefore(this as dynamic/*=E*/, entry, updateFirst: true); | 291 _list._insertBefore(this as dynamic/*=E*/, entry, updateFirst: true); |
292 } | 292 } |
293 } | 293 } |
OLD | NEW |