Dart LinkedList
最后修改于 2025 年 4 月 4 日
在 Dart 中，LinkedList 是一个专门的双向链表实现。它提供了在两端高效插入和删除操作。
LinkedList 的元素必须继承 LinkedListEntry。这个类维护着指向下一个和上一个条目的引用。列表会自动维护一致的链接。
创建 LinkedList
要使用 LinkedList，我们首先创建一个继承 LinkedListEntry 的条目类。
main.dart
import 'dart:collection';
class Person extends LinkedListEntry<Person> {
final String name;
final int age;
Person(this.name, this.age);
@override
String toString() => '$name ($age)';
}
void main() {
var people = LinkedList<Person>();
people.add(Person('Alice', 30));
people.add(Person('Bob', 25));
people.add(Person('Charlie', 35));
print(people);
}
我们定义一个继承 LinkedListEntry 的 Person 类。然后创建一个 LinkedList 并添加三个 Person 实例。列表会维护它们的顺序。
$ dart main.dart (Alice (30), Bob (25), Charlie (35))
插入元素
LinkedList 提供了几种在特定位置插入元素的方法。
main.dart
import 'dart:collection';
class Task extends LinkedListEntry<Task> {
final String description;
Task(this.description);
@override
String toString() => description;
}
void main() {
var tasks = LinkedList<Task>();
var first = Task('Wake up');
var second = Task('Brush teeth');
var third = Task('Have breakfast');
// Add to end
tasks.add(first);
tasks.add(third);
// Insert before
first.insertBefore(second);
// Insert after
third.insertAfter(Task('Go to work'));
print(tasks);
}
我们演示了 insertBefore 和 insertAfter 方法。这些方法允许在列表中精确地定位元素，无需进行索引计算。
$ dart main.dart (Brush teeth, Wake up, Have breakfast, Go to work)
移除元素
可以通过多种方式从 LinkedList 中删除元素。
main.dart
import 'dart:collection';
class Product extends LinkedListEntry<Product> {
final String name;
final double price;
Product(this.name, this.price);
@override
String toString() => '$name: \$$price';
}
void main() {
var cart = LinkedList<Product>();
var milk = Product('Milk', 2.99);
var bread = Product('Bread', 1.99);
var eggs = Product('Eggs', 3.49);
cart.addAll([milk, bread, eggs]);
print('Original: $cart');
// Remove specific item
bread.unlink();
print('After unlink: $cart');
// Remove first
cart.first.unlink();
print('After first removed: $cart');
// Clear all
cart.clear();
print('After clear: $cart');
}
unlink 方法可以移除列表中的一个条目。我们还可以使用 clear 一次性移除所有元素。
$ dart main.dart Original: (Milk: $2.99, Bread: $1.99, Eggs: $3.49) After unlink: (Milk: $2.99, Eggs: $3.49) After first removed: (Eggs: $3.49) After clear: ()
遍历 LinkedList
LinkedList 支持标准的迭代方法来遍历元素。
main.dart
import 'dart:collection';
class City extends LinkedListEntry<City> {
final String name;
final int population;
City(this.name, this.population);
@override
String toString() => '$name: $population';
}
void main() {
var cities = LinkedList<City>();
cities.addAll([
City('Tokyo', 37400068),
City('Delhi', 28514000),
City('Shanghai', 25582000)
]);
// Forward iteration
print('Forward:');
for (var city in cities) {
print(city);
}
// Manual backward iteration
print('\nBackward:');
var current = cities.last;
while (current != null) {
print(current);
current = current.previous;
}
}
我们演示了正向和反向遍历。LinkedList 会自动维护两个方向的链接。
$ dart main.dart Forward: Tokyo: 37400068 Delhi: 28514000 Shanghai: 25582000 Backward: Shanghai: 25582000 Delhi: 28514000 Tokyo: 37400068
LinkedList 属性
LinkedList 提供了几个有用的属性来访问列表元素。
main.dart
import 'dart:collection';
class Node extends LinkedListEntry<Node> {
final int value;
Node(this.value);
@override
String toString() => value.toString();
}
void main() {
var list = LinkedList<Node>();
list.addAll([Node(10), Node(20), Node(30), Node(40)]);
print('First: ${list.first}');
print('Last: ${list.last}');
print('Length: ${list.length}');
print('Is empty: ${list.isEmpty}');
print('Is not empty: ${list.isNotEmpty}');
print('\nElement at position 2:');
var element = list.first.next.next;
print('Current: $element');
print('Previous: ${element.previous}');
print('Next: ${element.next}');
}
我们访问了 LinkedList 及其条目的各种属性。每个条目通过 previous 和 next 引用知道它的邻居。
$ dart main.dart First: 10 Last: 40 Length: 4 Is empty: false Is not empty: true Element at position 2: Current: 30 Previous: 20 Next: 40
最佳实践
- 条目唯一性：一个条目一次只能属于一个 LinkedList。
- 内存效率：用于频繁的插入/删除。
- 性能：访问是 O(n)，而插入/删除是 O(1)。
- 线程安全：与所有 Dart 集合一样，不保证线程安全。
来源
本教程通过实际示例介绍了 Dart 的 LinkedList，演示了其主要功能和使用模式。
作者
列出 所有 Dart 教程。