用Swift实现LinkedList(双向链表结构的集合)

1. 什么是双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。---维基百科

2. 集合有哪些功能

  • 添加元素
  • 删除元素
  • 更新元素
  • 查找元素
  • 查找元素的位置

3. 文章中要实现的功能

  • 2中的特性
  • for in 遍历
  • 通过下标进行取值赋值
    *[字面量赋值
  • 把集合转成数组
  • 复制
  • 自定义打印

4.未实现的功能

  • 未把list定义成结构体
  • 若把list改成结构体则,未实现写时复制

原因:为了了解Swift中的集合以及学习链表,所以就简单的来了。

5. 如何实现

定义链表结构如下
  • size代表链表的长度
  • firstNode 表示第一个节点
  • lastNode 表示最后一个节点
  • Node 表示节点的类型
  • 通过序列初始化list
    1. 遍历序列,通过序列里的值生成节点newNode。
    2. 遍历到首个元素时,让firstNode和lastNode都指向newNode
    3. 遍历到其他元素时,把lastNode的next指向newNode,把newNode的prev指向lastNode,最后把lastNode指向newNode
    4. 每次遍历都把size += 1
final public class LinkedList<E>  {
    private var size = 0
    private var firstNode:Node<E>?
    private var lastNode:Node<E>?
    
    /// 初始化一个空list
    public init() { }
    
     /// 通过序列初始化一个list
    public init<S>(_ s: S) where Element == S.Element, S : Sequence {
        for (index,item) in s.enumerated() {
            let newNode = Node(element: item)
            if index == 0 {
                firstNode = newNode
                lastNode = newNode
            }else {
                newNode.prev = lastNode
                lastNode?.next = newNode
                lastNode = newNode
            }
            size += 1
        }
    }
}
/// 节点
fileprivate class Node<Element> {
    /// 节点元素的值
    var item:Element
    /// 下一个节点
    var next:Node<Element>?
    /// 上一个节点
    var prev:Node<Element>?
    init(element:Element, next:Node<Element>? = nil, prev:Node<Element>? = nil) {
        self.item = element
        self.next = next
        self.prev = prev
    }
}
如何查找指定位置的元素

如果查找的位置在前半部分就顺序查找,否则就逆序查找,以顺序查找为例,从首个节点开始,一直取next节点,直到要查找的位置。在查找之前首先要判断查找的位置是有效的,即index>=0 && index < size。

由于对使用者来说并不关心节点,只关心节点里的值,而且也不允许使用者修改节点的前后节点,所以对外暴露的是对外节点里的值,而不是节点。所以下面的方法定义为私有的。在文章的下面利用下标来进行取值和赋值

// MARK: - private
extension LinkedList {
    /// 通过下标找到对应的节点
    private func node(at index:Int) -> Node<E> {
        //如果下标位置无效,则直接报错
        if !indexIsVaild(index) {
            fatalError("Index out of range:\(index) not belong 0..<\(size)")
        }
        //如果节点在前一半顺序查找,否则逆序查找
        if index < (size >> 1) {
            var node = firstNode
            for _ in 0..<index {
                node = node?.next
            }
            return node!
        }else {
            var node = lastNode
            for _ in stride(from: size - 1, to: index, by: -1) {
                node = node?.prev
            }
            return node!
        }
    }
    /// 下标是否是有效的
    private func indexIsVaild(_ index:Int) -> Bool {
        return index >= 0 && index < size
    }
}
如何追加和插入元素

追加单个元素
只需要把lastNode的next指向要追加的节点,把要追加的节点的prev指向lastNode,最后把lastNode指向要追加的节点,并且把size+1。若追加时list为空,需要把firstNode也指向要追加的节点

插入单个元素

  1. 若插入的位置为0并且list长度为0时,直接把firstNode和lastNode都指向newNode;
  2. 获取插入位置的节点insertNode,把newNode的next指向要insertNode,把insertNode的prev指向newNode,把newNode的prev指向要insertNode的prev,把insertNode的prev的next指向newNode,若插入的位置为0,则把firstNode指向newNode,更新size的值

追加多个元素
只需要依次追加单个元素即可

插入多个元素

  1. 若插入的位置为0并且list长度为0时,则直接调用追加多个元素
  2. 把多个元素的节点连接起来,连接思路同如何通过一个序列初始化一个list。并记录下连接起来后的firstNode和lastNode,更新size的值
  3. 获取插入位置的节点insertNode,把lastNode的next指向insertNode,把insertNode的prev指向lastNode,把firstNode的prev指向要insertNode的prev,把insertNode的prev的next指向firstNode。若插入的位置为0,则把list的firstNode指向firstNode
// MARK: - 添加元素
extension LinkedList {
    /// 追加单个元素
    public func append(_ newElement: E) {
        let newNode = Node(element: newElement, next: nil, prev: lastNode)
        if lastNode == nil {
            firstNode = newNode
        }
        lastNode?.next = newNode
        lastNode = newNode
        size += 1
    }
    
    /// 追加多个元素
    public func append<S>(contentsOf newElements: S) where S : Sequence, E == S.Element {
        for item in newElements {
            append(item)
        }
    }
    
    /// 插入单个元素
    public func insert(_ newElement: E, at i: Int){
        let newNode = Node(element: newElement, next: nil, prev: nil)
        if i == 0 && size == 0{
            firstNode = newNode
            lastNode = newNode
        }else {
            let insertNode = node(at: i)
            newNode.next = insertNode
            insertNode.prev = newNode
            newNode.prev = insertNode.prev
            insertNode.prev?.next = newNode
            if i == 0 {
                firstNode = newNode
            }
        }
        size += 1
    }
    
    /// 插入多个元素
    public func insert<S>(contentsOf newElements: S, at i: Int) where S : Collection, E == S.Element {
        if i == 0 && size == 0 {
            append(contentsOf: newElements)
        }else {
            let insertNode = node(at: i)
            var firstNode:Node<E>?
            var lastNode:Node<E>?
            for (index,item) in newElements.enumerated() {
                let newNode = Node(element: item, next: nil, prev: nil)
                if index == 0 {
                    firstNode = newNode
                    lastNode = newNode
                }else {
                    newNode.prev = lastNode
                    lastNode?.next = newNode
                    lastNode = newNode
                }
                size += 1
            }
            firstNode?.prev = insertNode.prev
            lastNode?.next = insertNode
            insertNode.prev?.next = firstNode
            insertNode.prev = lastNode
            if i == 0 {
                self.firstNode = firstNode
            }
        }
    }
}
删除元素

删除指定位置的元素

  1. 获取指定位置的元素removeNode
  2. 把removeNode的prev的next指向removeNode的next
  3. 把removeNode的netx的prev指向removeNode的prev
  4. 把size -= 1

删除所有元素

  1. 获取首个节点node
  2. 若node不为空,取node的next为tmp,然后node的next和prev置nil
  3. 把node指向tmp,重复第二步
// MARK: - 删除元素
extension LinkedList {
    /// 删除指定位置的元素
    @discardableResult
    public func remove(at position: Int) -> E {
        if (position >= 0 && position < size){
            let removeNode = node(at: position)
            removeNode.prev?.next = removeNode.next
            removeNode.next?.prev = removeNode.prev
            if (position == 0) {
                firstNode = firstNode.next
            }else if (position == size - 1){
                lastNode = lastNode.prev
            }
            size -= 1
            return removeNode.item
        }else {
            return nil  
      }
    }
    /// 删除第一个元素
    @discardableResult
    public func removefirstNode() -> E? {
        if ()
        return firstNode == nil ? nil : remove(at: 0)
    }
    /// 删除最后一个元素
    @discardableResult
    public func removelastNode() -> E? {
        return lastNode == nil ? nil : remove(at: size - 1)
    }
    /// 删除所有元素
    public func removeAll() {
        var next = firstNode
        while next != nil {
            let tmp = next
            next?.next = nil
            next?.prev = nil
            next = tmp
        }
        firstNode = nil
        lastNode = nil
        size = 0
    }
}
实现Collection协议

实现Collection协议,就能拥有Collection协议里的方法。Collection协议里有很多方法,如isEmpty,count,map,filter,dropLast...等方法
Collection参考喵神翻译的书swift进阶第2章这里不详细介绍了

for in 遍历的原理是,本质是遍历一个迭代器,一直取next,而实现Collection协议时,已经返回了一个迭代器,所以实现Collection协议之后已经实现了for in ,forEach遍历

链表的迭代器:从首个元素可以,一直遍历next,直到next为nil

如何实现Collection协议
需要实现以下方法

  • public var startIndex: Int { get } 开始位置
  • public var endIndex: Int { get } 结束位置
  • public func index(after i: Int) -> Int 给定位置后面的索引值
  • public func makeIterator() -> Iterator 遍历时需要的迭代器
  • public subscript(position: Int) -> E 通过下标存取元素
// MARK: - 实现Collection协议
extension LinkedList : Collection {
    /// 开始位置
    public var startIndex: Int {  return 0 }
    /// 结束位置
    public var endIndex: Int { return size }
    /// 给定位置后面的索引值
    public func index(after i: Int) -> Int {
        return i + 1
    }
    /// 返回指定的迭代器
    public func makeIterator() -> Iterator {
        return Iterator(self)
    }
    /// 通过下标存取元素
    public subscript(position: Int) -> E {
        get {
            return node(at: position).item
        }
        set {
            node(at: position).item = newValue
        }
    }
}

// MARK: - 迭代器
extension LinkedList {
    public struct Iterator: IteratorProtocol {
        let list: LinkedList
        var index: Int
        private var nextNode:Node<E>?
        init(_ list: LinkedList) {
            self.list = list
            self.index = 0
            self.nextNode = list.firstNode
        }
        /// 获取下一个元素,在for in里若返回nil,则停止循环
        public mutating func next() -> E? {
            let item = nextNode?.item
            nextNode = nextNode?.next
            return item
        }
    }
}
查找满足特定条件的元素的位置和查找元素的位置

查找满足特定条件的元素的位置
只需要遍历,若遇到满足条件的直接返回index

查找元素的位置
其实就是满足要元素和列表的某一元素相等,所有需要元素遵循Equatable协议,然后调用查找满足特定条件的元素的位置的方法即可

// MARK: - 通过条件查找位置
extension LinkedList {
    /// 顺序查找
    public func firstIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        for (index,item) in self.enumerated() {
            if try predicate(item) {
                return index
            }
        }
        return nil
    }
    
    /// 倒序查找
    public func lastIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        var prev = lastNode
        var currentIndex = size - 1
        while prev != nil {
            if try predicate(prev!.item) {
                return currentIndex
            }
            currentIndex -= 1
            prev = prev?.prev
        }
        return nil
    }
    
    /// 是否包含
    public func contains(where predicate: (E) throws -> Bool) rethrows -> Bool {
        for item in self{
            if try predicate(item) {
                return true
            }
        }
        return false
    }
}
// MARK: - 通过元素查找位置
extension LinkedList where E : Equatable {
    public func firstIndex(of element: E) -> Int? {
        return firstIndex { (item) -> Bool in
            return item == element
        }
    }
    public func lastIndex(of element: E) -> Int? {
        return lastIndex(where: { (item) -> Bool in
            return item == element
        })
    }
    
    public func contains(_ element: E) -> Bool {
        return contains(where: { (item) -> Bool in
            return item == element
        })
    }
}
实现字面量赋值

只需要实现ExpressibleByArrayLiteral即可

extension LinkedList : ExpressibleByArrayLiteral {
    public convenience init(arrayLiteral elements: E...) {
        //这里是调用通过序列初始化链表
        self.init(elements)
    }
}
把链表转成数组

利用map方法

extension LinkedList {
    public func toArray() -> [E] {
        return self.map({ (item) -> E in
            return item
        })
    }
}
实现copy
// MARK: - Copy
extension LinkedList {
    public func copy() -> LinkedList {
        let copyList = LinkedList()
        copyList.size = self.size
        if let firstNode = firstNode {
            copyList.firstNode = Node(element: firstNode.item, next: nil, prev: nil)
            copyList.lastNode = copyList.firstNode
        }
        var nextNode = firstNode?.next
        while nextNode != nil {
            let newNode = Node(element: nextNode!.item)
            copyList.lastNode?.next = newNode
            newNode.prev = copyList.lastNode
            copyList.lastNode = newNode
            nextNode = nextNode?.next
        }
        return copyList
    }
}
实现自定义打印

只需要实现CustomDebugStringConvertible即可

extension LinkedList : CustomDebugStringConvertible {
    public var debugDescription: String {
        var desc = ""
        if size > 0 {
            for item in self.dropLast() {
                desc += "\(item)-->"
            }
            desc += "\(lastNode!.item)"
        }
        return desc
    }
}
demo地址
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,204评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,091评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,548评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,657评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,689评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,554评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,302评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,216评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,661评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,851评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,977评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,697评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,306评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,898评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,019评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,138评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,927评论 2 355

推荐阅读更多精彩内容