数据结构:Linked List

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看396 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 396|回复: 2
收起左侧

数据结构:Linked List

[复制链接]
Ding 发表于 2016-11-4 17:05:15 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
本帖最后由 Ding 于 2016-11-5 09:59 编辑

链表(Linked List)

链表极像数组,但是数组往往需要开辟一大块连续内存来存元素,而链表里的元素在内存里是分散在各处的,只是用指针(引用)串起来:

+--------+    +--------+    +--------+    +--------+
|        |    |        |    |        |    |        |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
|        |    |        |    |        |    |        |
+--------+    +--------+    +--------+    +--------+
   
链表里的元素我们一般称作结点(Node)。上图展示了一个单链表, 每个结点只持有一个引用——或曰指针——来记住其下一个结点的引用(地址)。在双链表里(如下),结点同时需要持有其前一个结点的引用:

+--------+    +--------+    +--------+    +--------+
|        |--->|        |--->|        |--->|        |
| node 0 |    | node 1 |    | node 2 |    | node 3 |
|        |<---|        |<---|        |<---|        |
+--------+    +--------+    +--------+    +--------+
   
我们需要时时地确定链表从哪开始,一般用一个叫head的指针来记录。

+--------+    +--------+    +--------+    +--------+
head --->|        |--->|        |--->|        |--->|        |---> nil
| node 0 |    | node 1 |    | node 2 |    | node 3 |
nil <---|        |<---|        |<---|        |<---|        |<--- tail
+--------+    +--------+    +--------+    +--------+
   

同样,用一个叫tail的指针记住链表的结束位置也很有用。注意到最后一个结点的next引用是nil,正如第一个结点的previous引用为空一样。

链表的性能

链表的大多数操作都是O(n)时间复杂度的,往往比数组慢。但也不能一概而论,由于不像数组那样总是开辟一大块连续空间,链表的某些操作只需要简单地改改指针的值。

O(n)时间复杂度的缘由是你不能简单地写个list[2]就直接访问到链表里的node 2。如果不是已经有了那个结点的地址,你必须从头按照每个结点的next指针走下去一直走到目标结点(或者从尾部按照previous指针找)。

但如果你已经有了某个结点的地址,像插入或删除这样的操作就会相当快。链表就是找结点慢。

这意味着当你处理链表的时候,应该尽可能地在最开始处插入新结点,那是O(1)复杂度的操作。如果你用了tail指针,从最后边插入也一样。

单链表和双链表

单链表比双链表节省一点点空间,因为每个结点只需要存储下个结点的引用而不用关心前一个结点。

不过,如果你有一个结点,需要知道其前一个结点的时候你就拧巴了。那就不得不从头开始遍历整个表直到你找到目标。

对于许多任务,双链表都使事情简单些。

为什么用链表?

最典型的需要链表的例子是队列(Queue)。如果队列用数组实现,从前边移除元素会很慢,因为需要在内存里把其他元素一一往前移动。但要使用上链表,只需要把head指针指向第二个结点,快多了。

不过老实说,在如今的编程环境下,你几乎从不需要写自己的链表。但了解它怎么工作的还是很有用;把元素链接在一起的原理同样用在树和图上。

开始燃烧

我们从定义结点开始:
[Swift] 纯文本查看 复制代码
public class LinkedListNode<T> {
    var value: T
    var next: LinkedListNode?
    weak var previous: LinkedListNode?
    
    public init(value: T) {
        self.value = value
    }
}

这是个泛型类型,你可以在node里存任何类型的数据。在下边我们只以String做例子。

我们这是个双链表,所以结点既有next也有previous指针,如果没有前结点或后结点,指针应是nil,所以是可选类型。

后文我会指出,如果链表是单的而不是双的,哪些函数需要改变。

注:为规避循环引用,我们用weak声明previous指针。假设链表里有个结点A,后边是结点B,A指向B,B也指向A。在某些情况下,这个循环引用会使结点一直存活,即使你删了它们。这不美好,所以我们声明其中一个为weak来打破循环。

开始建立链表
[Swift] 纯文本查看 复制代码
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
    }
}


我很想把LinkedListNode的定义放在LinkedList里边,但如今的Swift不允许泛型嵌套了。我们在LinkedList内部用了typealias,这样就可以在用到LinkedListNode<T>的地方简写为Node。

这个链表只定义了头指针而没有尾指针。添加尾指针的事儿你可以当作练习做一做。 (后文同样会指出如果有尾指针哪些函数需要改动。)

若头指针是nil,链表就是空的。因head是私有的,我加了first这个属性。

让我们在playground里玩一玩:
[Swift] 纯文本查看 复制代码
let list = LinkedList<String>()
list.isEmpty   // true
list.first     // nil


同样添加一个属性表明链表的最后一个结点。事情开始有意思了:
[Swift] 纯文本查看 复制代码
public var last: Node? {
    if var node = head {
        while case let next? = node.next {
            node = next
        }
        return node
    } else {
        return nil
    }
}

如果你是Swift新手,可能见过 if let 但没见过 if var 。其实做的事儿差不多 —— 把可选的head变量解包并把结果赋给局域变量node。不同之处是node不是常量而是变量,这样我们就可以在循环里改变它了。

循环里还有另外的Swift魔法:while case let next? = node。和下边的写法是等价的:
[Swift] 纯文本查看 复制代码
var node: Node? = head
while node != nil && node!.next != nil {
    node = node!.next
}

只是这样写对我来