Introduce new LinkedList to dart:collection.

sdk/lib/collection/linked_list.dart

Index: sdk/lib/collection/linked_list.dart
diff --git a/sdk/lib/collection/linked_list.dart b/sdk/lib/collection/linked_list.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3d4ef6d2dd9991a15e9ae8129c3112814332d895
--- /dev/null
+++ b/sdk/lib/collection/linked_list.dart
@@ -0,0 +1,183 @@
+// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+part of dart.collection;
+
+
+class LinkedList<E extends LinkedListEntry<E>>

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Documentation of for class?

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+    extends IterableBase<E>
+    implements _LinkedListLink {
+  int _modificationCount = 0;
+
+  int _length = 0;
+  _LinkedListLink _next;
+  _LinkedListLink _previous;
+
+  LinkedList() {
+    _next = _previous = this;
+  }
+
+  void addFirst(E entry) {

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

And documentation for all public methods?

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+    _insertAfter(this, entry);
+  }
+
+  void add(E entry) {
+    _insertAfter(_previous, entry);
+  }
+
+  void addAll(Iterable<E> entries) {
+    entries.forEach(add);

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Consider having an internal method, e.g., called "_add", and have both this
method and the "add" method call that.

If someone extends LinkedList (which is likely), they can override add and also
affect this method by accident.
(Or, as general rule, don't call overridable methods from other methods unless
it's explicitly documented and intentional). 

Also consider having a special case if entries is LinkedList where you just link
all its elements into this in one operation.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  }
+
+  bool remove(E entry) {
+    if (entry._list != this) return false;
+    _unlink(entry);  // Unlink will decrement length.
+    return true;
+  }
+
+  void _insertAfter(_LinkedListLink entry, E newEntry) {
+    if (newEntry.list != null) {
+      throw new StateError(
+          'LinkedListEntry is already in a LinkedList');
+    }
+    _modificationCount++;
+    newEntry._list = this;
+    var predecessor = entry;
+    var successor = entry._next;
+    successor._previous = newEntry;
+    newEntry._previous = predecessor;
+    newEntry._next = successor;
+    predecessor._next = newEntry;
+    _length++;
+  }
+
+  void _unlink(E entry) {
+    _modificationCount++;
+    entry._next._previous = entry._previous;
+    entry._previous._next = entry._next;
+    _length--;
+    entry._list = entry._next = entry._previous = null;
+  }
+
+  Iterator<LinkedListEntry> get iterator {
+    return new _LinkedListIterator(this);

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Iterator<E> get iterator => new _LinkedListIterator<E>(this);

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  }
+
+  String toString() => ToString.iterableToString(this);
+
+  int get length => _length;
+
+  void clear() {
+    _modificationCount++;
+    _LinkedListLink next = _next;
+    while (!identical(next, this)) {
+      _LinkedListLink entry = next;
+      next = entry._next;
+      entry._next = entry._previous = entry._list = null;
+    }
+    _next = _previous = this;
+    _length = 0;
+  }
+
+  E get first {
+    if (identical(_next, this)) {
+      throw new StateError('No such element');
+    }
+    return _next;
+  }
+
+  E get last {
+    if (identical(_previous, this)) {
+      throw new StateError('No such element');
+    }
+    return _previous;
+  }
+
+  E get single {
+    if (identical(_previous, this)) {
+      throw new StateError('No such element');
+    }
+    if (!identical(_previous, _next)) {
+      throw new StateError('Too many elements');
+    }
+    return _next;
+  }
+
+  void forEach(void action(E entry)) {

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Mention that it is an error to remove or add elements during an iteration.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+    int modificationCount = _modificationCount;
+    _LinkedListLink current = _next;
+    while (!identical(current, this)) {
+      action(current);
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      current = current._next;
+    }
+  }
+
+  bool get isEmpty => _length == 0;
+}
+
+
+class _LinkedListIterator<E extends LinkedListEntry>
+    implements Iterator<E> {
+  final LinkedList<E> _list;
+  final int _modificationCount;
+  E _current;
+  _LinkedListLink _next;
+
+  _LinkedListIterator(LinkedList<E> list)
+    : _list = list,
+      _modificationCount = list._modificationCount,
+      _next = list._next;
+
+  E get current => _current;
+
+  bool moveNext() {
+    if (identical(_next, _list)) {
+      _current = null;
+      return false;
+    }
+    if (_modificationCount != _list._modificationCount) {
+      throw new ConcurrentModificationError(this);
+    }
+    _current = _next;
+    _next = _next._next;
+    return true;
+  }
+}
+
+
+class _LinkedListLink {
+  _LinkedListLink _next;
+  _LinkedListLink _previous;
+}
+
+
+abstract class LinkedListEntry<E> extends _LinkedListLink {

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Consider implementing _LinkedListLink instead of extending it.
You'll have to add the fields here again, but then this class can be used as a
mixin!

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  LinkedList<E> _list;
+
+  LinkedList<E> get list => _list;
+
+  void unlink() {
+    _list._unlink(this);
+  }
+
+  LinkedListEntry get next {
+    return _next;
+  }
+
+  LinkedListEntry get previous {
+    if (_previous == _list) return null;
+    return _previous;
+  }
+
+  void insertAfter(E entry) {
+    _list._insertAfter(this, entry);
+  }
+
+  void insertBefore(E entry) {
+    _list._insertAfter(_previous, entry);
+  }
+}