数据结构:Linked List

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看269 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 269|回复: 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
}

只是这样写对我来说不够Swift范儿。 我们也可以用Swift内建的可选绑定,你能在后边看到一大波。

注:如果用了tail指针,last这个属性只需要简单地return tail即可。但我们没用,所以不得不从头遍历。如果链表很长,代价很大。

当然,如果是空链表,last返回的是nil。我们写个向尾部添加新结点的方法:
[Swift] 纯文本查看 复制代码
public func append(value: T) {
    let newNode = Node(value: value)
    if let lastNode = last {
        newNode.previous = lastNode
        lastNode.next = newNode
    } else {
        head = newNode
    }
}

append()方法先是创建了一个结点,又通过刚才定义的last属性获得最后一个结点。 如果是nil, 链表就是空的,就把这个newNode作为head;如果不是nil,我们通过next和previous指针把新结点加到链表里。 链表的实现代码,大量涉及到next和previous指针。

在playground里玩一玩:
[Swift] 纯文本查看 复制代码
list.append("Hello")
list.isEmpty         // false
list.first!.value    // "Hello"
list.last!.value     // "Hello"
链表看起来是这样:

+---------+
head --->|         |---> nil
| "Hello" |
nil <---|         |
+---------+
   
再加一个:
[Swift] 纯文本查看 复制代码
list.append("World")
list.first!.value    // "Hello"
list.last!.value     // "World"


现在是这样:

+---------+    +---------+
head --->|         |--->|         |---> nil
| "Hello" |    | "World" |
nil <---|         |<---|         |
+---------+    +---------+
   
你可以用next 和 previous来验证:
[Swift] 纯文本查看 复制代码
list.first!.previous          // nil
list.first!.next!.value       // "World"
list.last!.previous!.value    // "Hello"
list.last!.next               // nil


再加一个计算长度的属性,这个看起来很像上边提过的:
[Swift] 纯文本查看 复制代码
public var count: Int {
    if var node = head {
        var c = 1
        while case let next? = node.next {
            node = next
            c += 1
        }
        return c
    } else {
        return 0
    }
}

同样遍历了表,但是这次用了个计数的变量。

注:把count从O(n)复杂度变成O(1)复杂度的办法之一是定义一个存储属性。不管添加还是移除一个结点,你就更新一下该属性的值。

如果想访问某个特定位置的结点呢?在数组那儿只需要写array[index]就行,那是O(1)复杂度的操作。在链表里稍稍复杂点,还是类似的代码:
[Swift] 纯文本查看 复制代码
public func nodeAt(_ index: Int) -> Node? {
    if index >= 0 {
        var node = head
        var i = index
        while node != nil {
            if i == 0 { return node }
            i -= 1
            node = node!.next
        }
    }
    return nil
}


试一试:
[Swift] 纯文本查看 复制代码
list.nodeAt(0)!.value    // "Hello"
list.nodeAt(1)!.value    // "World"
list.nodeAt(2)           // nil


为了方便,可以写写subscript:
[Swift] 纯文本查看 复制代码
public subscript(index: Int) -> T {
    let node = nodeAt(index)
    assert(node != nil)
    return node!.value
}
现在好多了:
[Swift] 纯文本查看 复制代码
list[0]   // "Hello"
list[1]   // "World"
list[2]   // crash!
list[2]崩了,因为2那个位置没有元素,链表没那么长。

我们写了在尾部添加新结点的方法,但执行起来比较慢,因为先要找到最后一个元素。(如果用了tail指针就快了)。也可以在头部插入新元素,这个是O(1)复杂度的操作。

为了在任意位置插入结点,先写个工具方法:
[Swift] 纯文本查看 复制代码
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)
}
用元组返回index位置的两个结点。
注意循环后的断言检查表里是否有足够的结点。如果这时候i>0,说明index太大了。

现在写插入方法就简单了:
[Swift] 纯文本查看 复制代码
public func insert(value: T, atIndex index: Int) {
    let (prev, next) = nodesBeforeAndAfter(index)     // 1
    
    let newNode = Node(value: value)    // 2
    newNode.previous = prev
    newNode.next = next
    prev?.next = newNode
    next?.previous = newNode
    
    if prev == nil {                    // 3
        head = newNode
    }
}


我们还需做什么?移除元素!先写 removeAll(),超简单:
[Swift] 纯文本查看 复制代码
public func removeAll() {
    head = nil
}

如果有tail指针,也该在这里置为nil

如果你已经获得了某个结点,移除它就是这样:
[Swift] 纯文本查看 复制代码
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
}

别忘了head指针!如果要删的是head结点,那么head需要指向下一个。(若有tail指针也是类似处理),当然,如果没有结点剩余,head该置为nil。

试试:
[Swift] 纯文本查看 复制代码
list.remove(list.first!)   // "Hello"
list.count                     // 2
list[0]                        // "Swift"
list[1]                        // "World"


如果没有node的引用,可以用removeLast() 或 removeAt():
[Swift] 纯文本查看 复制代码
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!)
}


所有移除函数都返回了被移除的结点。
[Swift] 纯文本查看 复制代码
list.removeLast()              // "World"
list.count                     // 1
list[0]                        // "Swift"

list.removeAt(0)          // "Swift"
list.count                     // 0
注:如果是单链表,移除最后一个结点会略微复杂。不只需要最后结点的引用,倒数第二个结点的也需要。可以用nodesBeforeAndAfter() 帮忙。如果有tail指针,removeLast() 会相当快, 但记得把tail指向前一个结点。

还有些有趣的事做,比如方便调试的扩展:
[Swift] 纯文本查看 复制代码
extension LinkedList: CustomStringConvertible {
    public var description: String {
        var s = "["
        var node = head
        while node != nil {
            s += "\(node!.value)"
            node = node!.next
            if node != nil { s += ", " }
        }
        return s + "]"
    }
}

再比如翻。有个相当快的算法做翻转:
[Swift] 纯文本查看 复制代码
public func reverse() {
    var node = head
    while let currentNode = node {
        node = currentNode.next
        swap(¤tNode.next, ¤tNode.previous)
        head = currentNode
    }
}

遍历了链表并把每个结点的next和previous交换了。同时把head已到了最后。(如果有tail指针也要记得更改。)

数组它们有map啊filter这些方法,我们的链表为什么不支持呢?
[Swift] 纯文本查看 复制代码
public func map<U>(transform: T -> U) -> LinkedList<U> {
    let result = LinkedList<U>()
    var node = head
    while node != nil {
        result.append(transform(node!.value))
        node = node!.next
    }
    return result
}
可以这样用了:
[Swift] 纯文本查看 复制代码
let list = LinkedList<String>()
list.append("Hello")
list.append("Swifty")
list.append("Universe")

let m = list.map { s in s.characters.count }
m  // [5, 6, 8]

下边是filter:
[Swift] 纯文本查看 复制代码
public func filter(predicate: T -> Bool) -> LinkedList<T> {
    let result = LinkedList<T>()
    var node = head
    while node != nil {
        if predicate(node!.value) {
            result.append(node!.value)
        }
        node = node!.next
    }
    return result
}

用法:
[Swift] 纯文本查看 复制代码
let f = list.filter { s in s.characters.count > 5 }
f    // [Universe, Swifty]

思考: 这里的 map() 和 filter() 的实现并不快,因为它们在表尾append()新元素。 重复调append()是 O(n)的复杂度,因为需要遍历整个表去找最后一个元素。你能做得更快吗? (提示: 用一个变量记住每次添加的最后一个元素)

替代方案

上边介绍的链表用的结点使用class定义的,所以有引用语义。这没什么错,但是比起Swift的其他集合如Array和Dictionary的值语义,有点重了。

用值语义的enum来定义结点是可行的。看起来会像这样:
[Swift] 纯文本查看 复制代码
enum ListNode<T> {
    indirect case Node(T, next: ListNode<T>)
    case End
}

不过要使用值语义,大多数对链表的修改都会导致创建新的拷贝,这也是我们不用这个方案的原因。

数据机构:Linked List

数据结构:Linked List - 敏捷大拇指 - 数据机构:Linked List



原作者: Matthijs Hollemans




都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

买定离手 发表于 2016-11-7 09:05:05 | 显示全部楼层
链表算法,很复杂的
 楼主| Ding 发表于 2016-11-7 10:38:49 | 显示全部楼层
买定离手 发表于 2016-11-7 09:05
链表算法,很复杂的

还好~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
关闭

站长推荐 上一条 /3 下一条

热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表