一角撞、什么是鏈表
鏈表跟數(shù)組類似哲鸳，也是一個有序集合摹量。但他們的區(qū)別在于涤伐，創(chuàng)建數(shù)組時需要分配一大塊內(nèi)存用來存儲元素，而鏈表中的元素在內(nèi)存分配上是相互獨立的缨称，元素與元素之間是通過指針或者引用連接起來的凝果。
+--------+ +--------+ +--------+ +--------+
| | next | | next | | next | |
| node 0 |----->| node 1 |----->| node 2 |----->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
圖 1. 單向鏈表
1. 節(jié)點
一般我們把鏈表中的元素稱為“節(jié)點”。
2. 單向鏈表與雙向鏈表（Singly vs doubly linked lists）
節(jié)點與節(jié)點之間會通過指針或者引用連接起來睦尽，根據(jù)節(jié)點連接方式的不同器净，我們可以把鏈表分為單向鏈表和雙向鏈表兩種。
單向鏈表
上面圖 1 中所示的就是一個單向鏈表当凡。單向鏈表中的節(jié)點只有一個指向下一個元素的指針/引用(“next”指針)山害。
雙向鏈表
下面圖 2 中所示的是一個雙向鏈表。雙向鏈表中的節(jié)點有一個指向下一個元素的指針/引用（“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. 其他類型的鏈表
- 循環(huán)鏈表（Circular Linked list）
- 多重表（Multiply linked list）
二、為什么使用鏈表（鏈表的特點）
相比數(shù)組侦啸，鏈表的插入和刪除效率更高冗茸，對于不需要搜索但變動頻繁且無法預(yù)知數(shù)量上限的數(shù)據(jù)，更適合用鏈表匹中。
比如，當(dāng)我們從一個數(shù)組中移除第一個元素后豪诲，需要將后面的元素在內(nèi)存中的位置都往前移顶捷，這就意味著需要重新進行內(nèi)存分配和內(nèi)存布局，因為數(shù)組中的元素在內(nèi)存上是連續(xù)的屎篱。但是對于鏈表服赎，我們只需要把 head 指針/引用指向第二個元素就可以了葵蒂。
所以鏈表的特點顯而易見：
- 優(yōu)點
- 鏈表是一個動態(tài)的數(shù)據(jù)結(jié)構(gòu)，其容量可以隨意增大和減小
- 鏈表不需要在初始化時重虑，提前申請用于存儲元素的內(nèi)存
- 鏈表是一個將多個局部節(jié)點連接起來的數(shù)據(jù)結(jié)構(gòu)（類似的還有樹和圖）
- 插入刪除不需要移動其他元素践付，操作起來非常簡單
- 缺點
- 鏈表比數(shù)組要占用更多的內(nèi)存，因為鏈表除了需要用于值存儲之外缺厉，還有一些指針也需要占用空間
- 讀取鏈表的節(jié)點時永高，必須要從表頭或者表尾開始一個一個按順序讀
- 從鏈表中查找元素是比較費時的，因為鏈表中的節(jié)點不是連續(xù)存儲的提针，所以訪問單個節(jié)點的效率比較低
三命爬、鏈表的實現(xiàn)
實現(xiàn)鏈表有幾個要點：
- 設(shè)計鏈表的兩個要素
- 節(jié)點
-
next指針 -
previous指針（雙向鏈表）
-
- 表頭和表尾
-
head指針 -
tail指針（可選）
-
- 節(jié)點
- 操作鏈表時的兩個要點
- 更新
next指針和previous指針 - 更新
head指針和tail指針
- 更新
1. Swift（源碼）
注：這里是基于
class實現(xiàn)的，當(dāng)然你也可以使用enum辐脖。
/// 鏈表節(jié)點
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 開始往后一步一步走饲宛，直到最后一個節(jié)點
// 注：如果我們有一個記錄 tail 節(jié)點的實例變量，那么這個 last 方法就可以直接返回 tail 節(jié)點嗜价。但是我們在這里沒有這么做艇抠，所以這個 last 方法是一個比較耗時的操作，尤其是當(dāng)鏈表特別長的時候
public var last: Node? {
if var node = head {
while let next = node.next {
node = next
}
return node
} else {
return nil
}
}
// 找到最后一個節(jié)點久锥，將新節(jié)點拼接在后面
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
// 注：這種方式的復(fù)雜度為 O(n)，如果我們給鏈表添加一個實例變量用來追蹤 count 值的話奴拦，復(fù)雜度就變成了O(1)媒鼓，但是這樣我們就需要在每次添加或者移除一個節(jié)點的同時，去更新這個變量
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 步就可以得到結(jié)果了
// 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 // 剩余步數(shù)減 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
}
// 下標(biāo)方法绿鸣，內(nèi)部直接調(diào)用的是 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 方法同樣適用于單向鏈表暂氯，因為它們的實現(xiàn)不依賴于 prev 指針
public func insert(_ value: T, atIndex index: Int) {
// 找到要插入的位置的前后節(jié)點潮模，要注意為 nil 的情況
let (prev, next) = nodesBeforeAndAfter(index)
// 將新節(jié)點插入鏈表中，將其與前后節(jié)點鏈接起來
let newNode = Node(value: value)
newNode.previous = prev
newNode.next = next
prev?.next = newNode
next?.previous = newNode
// 當(dāng)插入的位置是 0痴施，那么就需要更新 head 了
// 注：如果有 tail 并且插入的位置是最后的話擎厢，也需要更新 tail
if prev == nil {
head = newNode
}
}
// 跟 nodeAt 方法類似，也是從 head 開始辣吃，一個一個往后找
// 這個方法是用來查找位于 index 位置的節(jié)點以及位于 index 前面一位的節(jié)點
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)
}
// 移除某個節(jié)點
// 這個方法的操作最簡單动遭，因為它不需要從頭開始一個一個去找這個節(jié)點
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!)
}
// 移除所有的節(jié)點
// 注：如果有 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
*/
// 反轉(zhuǎn)鏈表
// 如上圖所示：一步一步往后走神得，依次將每個節(jié)點的 prev 指針和 next 指針反轉(zhuǎn)過來厘惦，同時還要把 head 和 tail（如果有的話）調(diào)換一下
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
/**
鏈表節(jié)點
*/
@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; ///< 第一個節(jié)點
@property (strong, nonatomic, readonly) SCNode *last; ///< 最后一個節(jié)點
@property (assign, nonatomic) NSUInteger count; ///< 節(jié)點個數(shù)
// 插入節(jié)點
- (void)appendNodeWithValue:(ObjectType)value;
- (void)insertNodeWithValue:(ObjectType)value atIndex:(NSInteger)index;
// 訪問節(jié)點
- (SCNode *)nodeAtIndex:(NSInteger)index;
- (ObjectType)objectAtIndexedSubscript:(NSInteger)index;
// 移除操作
- (SCNode *)removeNode:(SCNode *)node;
- (SCNode *)removeNodeAtIndex:(NSUInteger)index;
- (SCNode *)removeLastNode;
- (void)removeAllNodes;
// 翻轉(zhuǎn)鏈表
- (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 開始往后一步一步走哩簿，直到最后一個節(jié)點
// 注：如果我們有一個記錄 tail 節(jié)點的實例變量宵蕉，那么這個 last 方法就可以直接返回 tail 節(jié)點酝静。但是我們在這里沒有這么做，所以這個 last 方法是一個比較耗時的操作羡玛，尤其是當(dāng)鏈表特別長的時候
- (SCNode *)last {
// 如果表頭為空别智，直接返回 nil
if (self.head == nil) {
return nil;
}
// 0(head) -> 1 -> 2 -> 3 -> 4(last)
SCNode *currentNode = self.head;
while (currentNode.next != nil) { // 下一個節(jié)點不是空的就去下一個
currentNode = currentNode.next;
}
return currentNode;
}
// 從 head 開始往后一步一步走，每走一步 count 加 1
// 注：這種方式的復(fù)雜度為 O(n)稼稿，如果我們給鏈表添加一個實例變量用來追蹤 count 值的話薄榛，復(fù)雜度就變成了O(1)，但是這樣我們就需要在每次添加或者移除一個節(jié)點的同時渺杉，去更新這個變量
- (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) { // 下一個節(jié)點不是空的蛇数，就往下去一個
count++;
currentNode = currentNode.next;
}
return count;
}
#pragma mark - 讀取節(jié)點
// 從 head 開始往后走，走 index 步就可以得到結(jié)果了
// 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;
// 剩余步數(shù)不為 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
// 下標(biāo)方法是越，內(nèi)部直接調(diào)用的是 nodeAt 方法耳舅，同時做了越界拋異常處理
- (id)objectAtIndexedSubscript:(NSInteger)index {
SCNode *node = [self nodeAtIndex:index];
NSAssert(node != nil, nil);
return node.value;
}
#pragma mark - 插入節(jié)點
// 找到最后一個節(jié)點，將新節(jié)點拼接在后面
- (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 位置的節(jié)點以及位于 index 前面一位的節(jié)點
- (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");
// 返回結(jié)果
if (completion) {
completion(prevOfCurrentNode, currentNode);
}
}
/* 示意圖：
* head --> A --> B --> C --> D --> E --> F --> nil
* prev next
*/
// 這個方法和 nodesBeforeAndAtIndex 方法同樣適用于單向鏈表，因為它們的實現(xiàn)不依賴于 prev 指針
- (void)insertNodeWithValue:(id)value atIndex:(NSInteger)index {
[self p_findNodesBeforeAndAtIndex:index completion:^(SCNode *prev, SCNode *next) {
// 將新節(jié)點插入鏈表中天梧，將其與前后節(jié)點鏈接起來
SCNode *newNode = [[SCNode alloc] initWithValue:value];
newNode.previous = prev;
newNode.next = next;
prev.next = newNode;
next.previous = newNode;
// 當(dāng)插入的位置是 0盔性，那么就需要更新 head 了
// 注：如果有 tail 并且插入的位置是最后的話，也需要更新 tail
if (prev == nil) {
self.head = prev;
}
}];
}
#pragma mark - 移除節(jié)點
- (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];
}
// 移除所有的節(jié)點
// 注：如果有 tail 的話，也要把 tail 置為 nil
- (void)removeAllNodes {
self.head = nil;
}
#pragma mark - 翻轉(zhuǎn)鏈表
/*
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
*/
// 反轉(zhuǎn)鏈表
// 一步一步往后走后豫，依次將每個節(jié)點的 prev 指針和 next 指針反轉(zhuǎn)過來悉尾，同時還要把 head 和 tail（如果有的話）調(diào)換一下
- (void)reverse {
SCNode *currentNode = self.head;
while (currentNode != nil) {
// 獲取當(dāng)前的這一步的節(jié)點
SCNode *nodeToSwap = currentNode;
// 往前走一步
currentNode = nodeToSwap.next;
// 翻轉(zhuǎn)當(dāng)前的這一步的節(jié)點
SCNode *previous = nodeToSwap.previous;
SCNode *next = nodeToSwap.next;
nodeToSwap.next = previous;
nodeToSwap.previous = next;
// 設(shè)置 head
self.head = currentNode;
}
}
@end
3. C（TODO）
四、復(fù)雜度
1. 訪問鏈表的單個元素的復(fù)雜度為 O(n)
如果我們想要訪問鏈表中的第 3 個元素挫酿，并不能想數(shù)組那樣直接通過 list[2] 就能訪問到构眯。因為我們沒有直接指向鏈表中每個元素的引用，我們只能從 head 指針指向的第一個元素開始查找早龟，然后通過每個節(jié)點 next 指針惫霸，一個節(jié)點一個節(jié)點往后查找，直到指定位置的節(jié)點葱弟。
所以壹店，查找元素并不是鏈表的特長。
2. 更快捷的插入和刪除操作
從前面的『為什么使用鏈表』部分芝加，我們就已經(jīng)了解到茫打，鏈表相比數(shù)組的優(yōu)勢就在于更高效的插入和刪除。
如果你已經(jīng)有了一個指向鏈表中某節(jié)點的指針/引用，那么在該位置插入新節(jié)點和刪除該節(jié)點的復(fù)雜度都為 O(1)老赤。
所以，我們在操作鏈表時制市，應(yīng)該盡可能利用已知的節(jié)點抬旺，比如借助 head、tail 插入新節(jié)點祥楣。
五开财、鏈表的應(yīng)用
六、我所理解的鏈表
- 鏈表是一種有序集合
- 鏈表是一種最基本误褪、最簡單责鳍、最常見的數(shù)據(jù)結(jié)構(gòu)之一，它可以被用來實現(xiàn)其它的一些抽象數(shù)據(jù)結(jié)構(gòu)（ADT）兽间，比如表历葛、棧、隊列
- 鏈表中的元素就是節(jié)點嘀略，節(jié)點包含存儲內(nèi)容的
value變量和next指針（雙向鏈表的節(jié)點還包含previous指針） - 鏈表除了節(jié)點還有指向第 1 個元素的
head指針和指向最后一個元素的tail指針 - 鏈表的優(yōu)勢在于插入刪除操作的高效
- 鏈表的查找操作復(fù)雜度為 O(n)恤溶，無須查找的插入或者刪除操作的復(fù)雜度為 O(1)
七、面試題
- 為什么在使用 for-in 語句遍歷 NSArray 變量時帜羊，同時插入或者刪除元素會導(dǎo)致 crash咒程？
八、參考資料
- raywenderlich/swift-algorithm-club: Linked List
- Linked list - Wikipedia
- 鏈表(linked list)這一數(shù)據(jù)結(jié)構(gòu)具體有哪些實際應(yīng)用讼育？
- 用鏈表的目的是什么帐姻？省空間還是省時間？
如果你也喜歡交流技術(shù)奶段、喜歡閱讀饥瓷、積極踐行，歡迎關(guān)注我的公眾號：祥龍Shannon寫字的地方忧饭，一起成長扛伍。
qrcode_for_gh_cc686217be41_344.jpg
