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..57a2099a59d075646c88fa49cd181fc330e0bde5
--- /dev/null
+++ b/sdk/lib/collection/linked_list.dart
@@ -0,0 +1,139 @@
+// 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>>
+    extends IterableBase<E>
+    implements _LinkedListEntry {
+  int _length = 0;
+  _LinkedListEntry _next;
+  _LinkedListEntry _prev;

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

You need a modification count to catch concurrent modifications.

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+
+  LinkedList() {
+    _next = _prev = this;
+  }
+
+  void addFirst(E entry) {
+    _insertAfter(this, entry);
+  }
+
+  void add(E entry) {
+    _insertAfter(_prev, entry);
+  }
+
+  void addAll(Iterable<E> entries) {
+    entries.forEach(add);
+  }
+
+  void remove(E entry) {
+    if (entry._list != this) return;

[floitsch, 2013/05/23 19:01:26]

Shouldn't we throw here?

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

I think returning is fine. We don't throw in other collections if removing an
element that isn't there.

It should probably return a boolean that is true if it removes something.

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+    entry.unlink();  // Unlink will decrement length.
+  }
+
+  void _insertAfter(_LinkedListEntry entry, E newEntry) {
+    if (newEntry.list != null) {
+      throw new StateError(
+          'LinkedListEntry is already present in a LinkedList');

[floitsch, 2013/05/23 19:01:26]

is already in a LinkedList

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+    }
+    newEntry._list = this;

[floitsch, 2013/05/23 19:01:26]

I think this would read easier as follows (or use "previous", "next"):
_LinkedListEntry predecessor = entry;
_LinkedListEntry successor = entry._next;
predecessor._next = newEntry;
newEntry._prev = predecessor;
newEntry._next = successor;
successor._prev = newEntry;

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+    entry._next._prev = newEntry;
+    newEntry._prev = entry;
+    newEntry._next = entry._next;
+    entry._next = newEntry;
+    _length++;
+  }
+
+  Iterator<LinkedListEntry> get iterator {
+    return new _LinkedListIterator(this);
+  }
+
+  String toString() => ToString.iterableToString(this);
+
+  int get length => _length;
+
+  void clear() {
+    for (var entry in this) {

[floitsch, 2013/05/23 19:01:26]

This looks dangerous.
I would prefer not to use an iterator.

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

Agree.

_LinkedListEntry next = _this._next;
while (!identical(next, this)) {
  _LinkedListEntry entry = next;
  next = entry._next;
  entry._next = entry._prev = entry._list = null;
}
_next = _prev = this;
_length = 0;

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+      entry._next = entry._prev = entry._list = null;
+    }
+    _next = _prev = this;
+    _length = 0;
+  }
+
+  E get first {
+    if (identical(_next, this)) {
+      throw new StateError('No such element');
+    }
+    return _next;
+  }
+
+  E get last {
+    if (identical(_prev, this)) {
+      throw new StateError('No such element');
+    }
+    return _prev;
+  }

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

E get single {
  if (identical(_prev, this)) {
    throw new StateError('No such element');
  }
  if (!identical(_prev, _next)) {
    throw new StateError('Too many elements');
  }
  return _next;
}

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

Implement forEach without an iterator too.
Remember concurrent modifications.

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+  bool get isEmpty => _length == 0;
+}
+
+
+class _LinkedListIterator<E extends LinkedListEntry>
+    implements Iterator<E> {
+  LinkedList<E> _list;
+  E _current;
+  _LinkedListEntry _next;
+
+  _LinkedListIterator(LinkedList<E> list) : _list = list, _next = list._next;
+
+  E get current => _current;
+
+  bool moveNext() {
+    if (identical(_next, _list)) {

[floitsch, 2013/05/23 19:01:26]

Is it on purpose that you don't check the length (or maybe even more) for
concurrentModificationErrors ?
If I'm not wrong
for (var x in linkedList) linkedList.remove(x.next);
would crash.

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+      _current = null;
+      return false;
+    }
+    _current = _next;
+    _next = _next._next;
+    return true;
+  }
+}
+
+
+class _LinkedListEntry {

[floitsch, 2013/05/23 19:01:26]

Call it something else.
_LinkedListLink ?

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

_ListLink?

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+  _LinkedListEntry _next;
+  _LinkedListEntry _prev;
+}
+
+
+abstract class LinkedListEntry<E> extends _LinkedListEntry {
+  LinkedList<E> _list;
+
+  LinkedList<E> get list => _list;
+
+  void unlink() {
+    _next._prev = _prev;
+    _prev._next = _next;
+    _list._length--;
+    _list = _next = _prev = null;
+  }
+
+  LinkedListEntry get next {
+    return _next;
+  }
+
+  LinkedListEntry get prev {

[floitsch, 2013/05/23 19:01:26]

usually we don't abbreviate. Should "prev" really be an exception?

[Lasse Reichstein Nielsen, 2013/05/24 08:42:45]

I don't think so. I generally write it out (both "previous" and "_previous").

[Anders Johnsen, 2013/06/13 11:14:10]

Done.

+    if (_prev == _list) return null;
+    return _prev;
+  }
+
+  void insertAfter(E entry) {
+    _list._insertAfter(this, entry);
+  }
+
+  void insertBefore(E entry) {
+    _list._insertAfter(_prev, entry);
+  }
+}