数据结构和算法：链表（Linked List）
2017-10-22 本文已影响597人
ShannonChenCHN
一、什么是链表
链表跟数组类似，也是一个有序集合。但他们的区别在于，创建数组时需要分配一大块内存用来存储元素，而链表中的元素在内存分配上是相互独立的，元素与元素之间是通过指针或者引用连接起来的。
+--------+ +--------+ +--------+ +--------+
| | next | | next | | next | |
| node 0 |----->| node 1 |----->| node 2 |----->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
图 1. 单向链表
1. 节点
一般我们把链表中的元素称为“节点”。
2. 单向链表与双向链表（Singly vs doubly linked lists）
节点与节点之间会通过指针或者引用连接起来，根据节点连接方式的不同，我们可以把链表分为单向链表和双向链表两种。
单向链表
上面图 1 中所示的就是一个单向链表。单向链表中的节点只有一个指向下一个元素的指针/引用(“next”指针)。
双向链表
下面图 2 中所示的是一个双向链表。双向链表中的节点有一个指向下一个元素的指针/引用（“next”指针），同时还有一个指向上一个元素的指针/引用（“previous”指针）。
+--------+ next +--------+ next +--------+ next +--------+
| |----->| |----->| |----->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<-----| |<-----| |<-----| |
+--------+ prev +--------+ prev +--------+ prev +--------+
图 2. 双向链表
3. head 指针和 tail 指针
在使用链表时，我们一般需要知道链表从哪里开始的，所以链表一般会有一个 head 指针，指向链表中的第一个元素。此时第一个元素的 previous 指针为 nil。
有时候，我们还会有一个 tail 指针，指向链表中的最后一个元素。此时最后一个元素的 next 指针为 nil。
+--------+ next +--------+ next +--------+ next +--------+
head--->| |----->| |----->| |----->| |--->nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |<-----| |<-----| |<-----| |<---tail
+--------+ prev +--------+ prev +--------+ prev +--------+
图 3. head 指针和 tail 指针
4. 其他类型的链表
- 循环链表（Circular Linked list）
- 多重表（Multiply linked list）
二、为什么使用链表（链表的特点）
相比数组，链表的插入和删除效率更高，对于不需要搜索但变动频繁且无法预知数量上限的数据，更适合用链表。
比如，当我们从一个数组中移除第一个元素后，需要将后面的元素在内存中的位置都往前移，这就意味着需要重新进行内存分配和内存布局，因为数组中的元素在内存上是连续的。但是对于链表，我们只需要把 head 指针/引用指向第二个元素就可以了。
所以链表的特点显而易见：
- 优点
- 链表是一个动态的数据结构，其容量可以随意增大和减小
- 链表不需要在初始化时，提前申请用于存储元素的内存
- 链表是一个将多个局部节点连接起来的数据结构（类似的还有树和图）
- 插入删除不需要移动其他元素，操作起来非常简单
- 缺点
- 链表比数组要占用更多的内存，因为链表除了需要用于值存储之外，还有一些指针也需要占用空间
- 读取链表的节点时，必须要从表头或者表尾开始一个一个按顺序读
- 从链表中查找元素是比较费时的，因为链表中的节点不是连续存储的，所以访问单个节点的效率比较低
三、链表的实现
实现链表有几个要点：
- 设计链表的两个要素
- 节点
-
next指针 -
previous指针（双向链表）
-
- 表头和表尾
-
head指针 -
tail指针（可选）
-
- 节点
- 操作链表时的两个要点
- 更新
next指针和previous指针 - 更新
head指针和tail指针
- 更新
1. Swift（源码）
注：这里是基于
class实现的，当然你也可以使用enum。
/// 链表节点
public class LinkedListNode<T> {
var value: T
var next: LinkedListNode?
weak var previous: LinkedListNode?
public init(value: T) {
self.value = value
}
}
/// 一个双向链表
public class LinkedList<T> {
public typealias Node = LinkedListNode<T>
private var head: Node?
public var isEmpty: Bool {
return head == nil
}
public var first: Node? {
return head
}
// 从 head 开始往后一步一步走，直到最后一个节点
// 注：如果我们有一个记录 tail 节点的实例变量，那么这个 last 方法就可以直接返回 tail 节点。但是我们在这里没有这么做，所以这个 last 方法是一个比较耗时的操作，尤其是当链表特别长的时候
public var last: Node? {
if var node = head {
while let next = node.next {
node = next
}
return node
} else {
return nil
}
}
// 找到最后一个节点，将新节点拼接在后面
public func append(_ value: T) {
let newNode = Node(value: value)
if let lastNode = self.last {
newNode.previous = lastNode
lastNode.next = newNode
} else {
head = newNode
}
}
// 从 head 开始往后一步一步走，每走一步 count 加 1
// 注：这种方式的复杂度为 O(n)，如果我们给链表添加一个实例变量用来追踪 count 值的话，复杂度就变成了O(1)，但是这样我们就需要在每次添加或者移除一个节点的同时，去更新这个变量
public var count: Int {
if var node = head {
var c = 1
while let next = node.next {
node = next
c += 1
}
return c
} else {
return 0
}
}
// 从 head 开始往后走，走 index 步就可以得到结果了
// 0(head) -> 1 -> 2 -> 3
public func nodeAt(_ index: Int) -> Node? {
if index >= 0 {
var node = head
var leftStep = index // 需要走多少步
while node != nil {
if leftStep == 0 { return node } // 直到剩余 0 步时才返回
leftStep -= 1 // 剩余步数减 1
node = node!.next // 往前走一步
}
// // 另一种方案
// for _ in 0..<index {
// if let tempNode = node, tempNode.next != nil {
// node = tempNode.next
// } else {
// node = nil
// }
// }
// return node
}
return nil
}
// 下标方法，内部直接调用的是 nodeAt 方法，同时做了越界抛异常处理
public subscript(index: Int) -> T {
let node = nodeAt(index)
assert(node != nil)
return node!.value
}
/* 示意图：
* head --> A --> B --> C --> D --> E --> F --> nil
* prev next
*/
// 这个方法和 nodesBeforeAndAfter 方法同样适用于单向链表，因为它们的实现不依赖于 prev 指针
public func insert(_ value: T, atIndex index: Int) {
// 找到要插入的位置的前后节点，要注意为 nil 的情况
let (prev, next) = nodesBeforeAndAfter(index)
// 将新节点插入链表中，将其与前后节点链接起来
let newNode = Node(value: value)
newNode.previous = prev
newNode.next = next
prev?.next = newNode
next?.previous = newNode
// 当插入的位置是 0，那么就需要更新 head 了
// 注：如果有 tail 并且插入的位置是最后的话，也需要更新 tail
if prev == nil {
head = newNode
}
}
// 跟 nodeAt 方法类似，也是从 head 开始，一个一个往后找
// 这个方法是用来查找位于 index 位置的节点以及位于 index 前面一位的节点
private func nodesBeforeAndAfter(_ index: Int) -> (Node?, Node?) {
assert(index >= 0)
var i = index
var next = head
var prev: Node?
while next != nil && i > 0 {
i -= 1
prev = next
next = next!.next
}
assert(i == 0) // 越界的处理
return (prev, next)
}
// 移除某个节点
// 这个方法的操作最简单，因为它不需要从头开始一个一个去找这个节点
public func remove(node: Node) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
node.previous = nil
node.next = nil
return node.value
}
public func removeLast() -> T {
assert(!isEmpty)
return remove(node: last!)
}
public func removeAt(_ index: Int) -> T {
let node = nodeAt(index)
assert(node != nil)
return remove(node: node!)
}
// 移除所有的节点
// 注：如果有 tail 的话，也要把 tail 置为 nil
public func removeAll() {
head = nil
}
/*
pre +--------+ pre +--------+ pre +--------+ pre +--------+
nil <----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
head ---->| |----->| |----->| |----->| |-----> nil
+--------+ next +--------+ next +--------+ next +--------+ next
next +--------+ pre +--------+ pre +--------+ pre +--------+
nil <-----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |-----> nil
+--------+ pre +--------+ next +--------+ next +--------+ next
∧
|
head
next +--------+ next +--------+ pre +--------+ pre +--------+
nil <-----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |
+--------+ pre +--------+ pre +--------+ next +--------+
∧
|
head
next +--------+ next +--------+ next +--------+ next +--------+
nil <-----| |<-----| |<-----| |<-----| |<---- head
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |-----> nil
+--------+ pre +--------+ pre +--------+ pre +--------+ pre
*/
// 反转链表
// 如上图所示：一步一步往后走，依次将每个节点的 prev 指针和 next 指针反转过来，同时还要把 head 和 tail（如果有的话）调换一下
public func reverse() {
var node = head
// tail = node // If you had a tail pointer
while let currentNode = node {
node = currentNode.next
swap(¤tNode.next, ¤tNode.previous)
head = currentNode
}
}
2. Objective-C（源码）
NS_ASSUME_NONNULL_BEGIN
/**
链表节点
*/
@interface SCLinkedListNode<__covariant ObjectType> : NSObject
@property (strong, nonatomic) ObjectType value;
@property (strong, nonatomic, nullable) SCLinkedListNode *next;
@property (weak, nonatomic, nullable) SCLinkedListNode *previous;
- (instancetype)initWithValue:(ObjectType)value;
@end
NS_ASSUME_NONNULL_END
@implementation SCLinkedListNode
- (instancetype)initWithValue:(id)value {
self = [super init];
if (self) {
_value = value;
}
return self;
}
- (NSString *)description {
return self.value;
}
@end
NS_ASSUME_NONNULL_BEGIN
typedef SCLinkedListNode SCNode;
/**
一个双向链表
有 head，但是没有 tail
0(head/first) -> 1 -> 2 -> 3 -> 4(last)
*/
@interface SCLinkedList<__covariant ObjectType> : NSObject
@property (assign, nonatomic, readonly) BOOL isEmpty; ///< 是否为空
@property (strong, nonatomic, readonly) SCNode *first; ///< 第一个节点
@property (strong, nonatomic, readonly) SCNode *last; ///< 最后一个节点
@property (assign, nonatomic) NSUInteger count; ///< 节点个数
// 插入节点
- (void)appendNodeWithValue:(ObjectType)value;
- (void)insertNodeWithValue:(ObjectType)value atIndex:(NSInteger)index;
// 访问节点
- (SCNode *)nodeAtIndex:(NSInteger)index;
- (ObjectType)objectAtIndexedSubscript:(NSInteger)index;
// 移除操作
- (SCNode *)removeNode:(SCNode *)node;
- (SCNode *)removeNodeAtIndex:(NSUInteger)index;
- (SCNode *)removeLastNode;
- (void)removeAllNodes;
// 翻转链表
- (void)reverse;
@end
NS_ASSUME_NONNULL_END
@interface SCLinkedList ()
@property (strong, nonatomic, nullable) SCNode *head; ///< 链表头
@end
@implementation SCLinkedList
#pragma mark - Getter
- (BOOL)isEmpty {
return self.head == nil;
}
- (SCNode *)first {
return self.head;
}
// 从 head 开始往后一步一步走，直到最后一个节点
// 注：如果我们有一个记录 tail 节点的实例变量，那么这个 last 方法就可以直接返回 tail 节点。但是我们在这里没有这么做，所以这个 last 方法是一个比较耗时的操作，尤其是当链表特别长的时候
- (SCNode *)last {
// 如果表头为空，直接返回 nil
if (self.head == nil) {
return nil;
}
// 0(head) -> 1 -> 2 -> 3 -> 4(last)
SCNode *currentNode = self.head;
while (currentNode.next != nil) { // 下一个节点不是空的就去下一个
currentNode = currentNode.next;
}
return currentNode;
}
// 从 head 开始往后一步一步走，每走一步 count 加 1
// 注：这种方式的复杂度为 O(n)，如果我们给链表添加一个实例变量用来追踪 count 值的话，复杂度就变成了O(1)，但是这样我们就需要在每次添加或者移除一个节点的同时，去更新这个变量
- (NSUInteger)count {
// 0(head) -> 1 -> 2 -> 3 -> 4(last)
//
if (self.head == nil) {
return 0;
}
SCNode *currentNode = self.head;
NSInteger count = 1;
while (currentNode.next != nil) { // 下一个节点不是空的，就往下去一个
count++;
currentNode = currentNode.next;
}
return count;
}
#pragma mark - 读取节点
// 从 head 开始往后走，走 index 步就可以得到结果了
// 0(head) -> 1 -> 2 -> 3
- (SCNode *)nodeAtIndex:(NSInteger)index {
NSAssert(index >= 0, @"Error: Out of bounds");
// 链表为空就直接返回 nil
if (self.head == nil) {
return nil;
}
SCNode *currentNode = self.head; // 从 head 往后走
NSInteger step = index;
// 剩余步数不为 0
while (step > 0) {
// 往后走一步
step--;
currentNode = currentNode.next;
// 出界了就返回 nil
if (currentNode == nil) {
return nil;
}
}
return currentNode;
}
// http://www.cnblogs.com/zenny-chen/p/3593660.html
// 下标方法，内部直接调用的是 nodeAt 方法，同时做了越界抛异常处理
- (id)objectAtIndexedSubscript:(NSInteger)index {
SCNode *node = [self nodeAtIndex:index];
NSAssert(node != nil, nil);
return node.value;
}
#pragma mark - 插入节点
// 找到最后一个节点，将新节点拼接在后面
- (void)appendNodeWithValue:(id)value {
// 0(head) -> 1 -> 2 -> 3(last)
// 0(head) -> 1 -> 2 -> 3 -> 4(last)
SCNode *newNode = [[SCNode alloc] initWithValue:value];
if (self.last) {
newNode.previous = self.last;
self.last.next = newNode;
} else {
self.head = newNode;
}
}
// 跟 nodeAt 方法类似，也是从 head 开始，一个一个往后找
// 这个方法是用来查找位于 index 位置的节点以及位于 index 前面一位的节点
- (void)p_findNodesBeforeAndAtIndex:(NSInteger)index completion:(void(^)(SCNode *prev, SCNode *this))completion {
NSAssert(index >= 0, @"Error: out of bounds");
// 0(head) -> 1 -> 2 -> 3
NSInteger step = index;
SCNode *currentNode = self.head;
SCNode *prevOfCurrentNode = nil;
while (step > 0 && currentNode.next) {
step--;
prevOfCurrentNode = currentNode;
currentNode = currentNode.next;
}
NSAssert(step == 0, @"Error: Out of bounds");
// 返回结果
if (completion) {
completion(prevOfCurrentNode, currentNode);
}
}
/* 示意图：
* head --> A --> B --> C --> D --> E --> F --> nil
* prev next
*/
// 这个方法和 nodesBeforeAndAtIndex 方法同样适用于单向链表，因为它们的实现不依赖于 prev 指针
- (void)insertNodeWithValue:(id)value atIndex:(NSInteger)index {
[self p_findNodesBeforeAndAtIndex:index completion:^(SCNode *prev, SCNode *next) {
// 将新节点插入链表中，将其与前后节点链接起来
SCNode *newNode = [[SCNode alloc] initWithValue:value];
newNode.previous = prev;
newNode.next = next;
prev.next = newNode;
next.previous = newNode;
// 当插入的位置是 0，那么就需要更新 head 了
// 注：如果有 tail 并且插入的位置是最后的话，也需要更新 tail
if (prev == nil) {
self.head = prev;
}
}];
}
#pragma mark - 移除节点
- (SCNode *)removeNode:(SCNode *)node {
// head --> A --> B --> C --> D --> E
SCNode *prev = node.previous;
SCNode *next = node.next;
if (node == self.head) { // 要移除的是 head
self.head = next;
next.previous = nil;
} else { // 要移除的不是 head，而是 A，B.....
prev.next = next;
next.previous = prev;
}
// 切断 node 的前后连接
node.previous = nil;
node.next = nil;
return node.value;
}
- (SCNode *)removeNodeAtIndex:(NSUInteger)index {
SCNode *node = [self nodeAtIndex:index];
NSAssert(node != nil, nil);
return [self removeNode:node];
}
- (SCNode *)removeLastNode {
NSAssert(self.isEmpty == NO, nil);
return [self removeNode:self.last];
}
// 移除所有的节点
// 注：如果有 tail 的话，也要把 tail 置为 nil
- (void)removeAllNodes {
self.head = nil;
}
#pragma mark - 翻转链表
/*
pre +--------+ pre +--------+ pre +--------+ pre +--------+
nil <----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
head ---->| |----->| |----->| |----->| |-----> nil
+--------+ next +--------+ next +--------+ next +--------+ next
next +--------+ pre +--------+ pre +--------+ pre +--------+
nil <-----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |-----> nil
+--------+ pre +--------+ next +--------+ next +--------+ next
∧
|
head
next +--------+ next +--------+ pre +--------+ pre +--------+
nil <-----| |<-----| |<-----| |<-----| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |
+--------+ pre +--------+ pre +--------+ next +--------+
∧
|
head
next +--------+ next +--------+ next +--------+ next +--------+
nil <-----| |<-----| |<-----| |<-----| |<---- head
| node 0 | | node 1 | | node 2 | | node 3 |
| |----->| |----->| |----->| |-----> nil
+--------+ pre +--------+ pre +--------+ pre +--------+ pre
*/
// 反转链表
// 一步一步往后走，依次将每个节点的 prev 指针和 next 指针反转过来，同时还要把 head 和 tail（如果有的话）调换一下
- (void)reverse {
SCNode *currentNode = self.head;
while (currentNode != nil) {
// 获取当前的这一步的节点
SCNode *nodeToSwap = currentNode;
// 往前走一步
currentNode = nodeToSwap.next;
// 翻转当前的这一步的节点
SCNode *previous = nodeToSwap.previous;
SCNode *next = nodeToSwap.next;
nodeToSwap.next = previous;
nodeToSwap.previous = next;
// 设置 head
self.head = currentNode;
}
}
@end
3. C（TODO）
四、复杂度
1. 访问链表的单个元素的复杂度为 O(n)
如果我们想要访问链表中的第 3 个元素，并不能想数组那样直接通过 list[2] 就能访问到。因为我们没有直接指向链表中每个元素的引用，我们只能从 head 指针指向的第一个元素开始查找，然后通过每个节点 next 指针，一个节点一个节点往后查找，直到指定位置的节点。
所以，查找元素并不是链表的特长。
2. 更快捷的插入和删除操作
从前面的『为什么使用链表』部分，我们就已经了解到，链表相比数组的优势就在于更高效的插入和删除。
如果你已经有了一个指向链表中某节点的指针/引用，那么在该位置插入新节点和删除该节点的复杂度都为 O(1)。
所以，我们在操作链表时，应该尽可能利用已知的节点，比如借助 head、tail 插入新节点。
五、链表的应用
六、我所理解的链表
- 链表是一种有序集合
- 链表是一种最基本、最简单、最常见的数据结构之一，它可以被用来实现其它的一些抽象数据结构（ADT），比如表、栈、队列
- 链表中的元素就是节点，节点包含存储内容的
value变量和next指针（双向链表的节点还包含previous指针） - 链表除了节点还有指向第 1 个元素的
head指针和指向最后一个元素的tail指针 - 链表的优势在于插入删除操作的高效
- 链表的查找操作复杂度为 O(n)，无须查找的插入或者删除操作的复杂度为 O(1)
七、面试题
- 为什么在使用 for-in 语句遍历 NSArray 变量时，同时插入或者删除元素会导致 crash？
八、参考资料
- raywenderlich/swift-algorithm-club: Linked List
- Linked list - Wikipedia
- 链表(linked list)这一数据结构具体有哪些实际应用？
- 用链表的目的是什么？省空间还是省时间？
如果你也喜欢交流技术、喜欢阅读、积极践行，欢迎关注我的公众号：祥龙Shannon写字的地方，一起成长。
qrcode_for_gh_cc686217be41_344.jpg
