数据结构-双向链表

数据结构是计算机存储、组织数据的方式
本文演示代码为Swift语言

链表

在前篇描述了数据结构-单向链表的结构，以及常见的一些操作、算法等；本文就描述一下双向链表

使用双向链表可以提升链表的综合性能，比如要查找双向链表的尾节点时可以直接通过last去找到了，而单向链表只能依次通过next去查找

双向链表 - node方法

由于双向链表可以通过前一个节点找到前一个元素，因此在设计根据index查找节点方法时，可以判断index位于总长度的前/后位置，从双向链表的前面或者后面开始查找; 比如要查找倒数第二个节点时，可以从last开始往前遍历查询，这比单向链表的性能要高很多

双向链表 - add(int index, T element)

往双向链表添加节点时，需要考虑以下情况

size == index(说明要添加在最后面)
1.用oldLast变量指向链表的last节点
2.给链表的last赋值为(prevNode=oldLast, 节点=element, nextNode=nil)
- 链表的last为空(说明链表是空的)
  - 将链表的first指向链表的last(链表为空，连接first指针)
- 链表的last不为空(说明链表不是空的)
  - 将oldLast的next指向链表的last(oldLast为链表添加前的last节点)
size != index(也有可能是往首节点添加)
1.用next变量指向要添加的节点
2.用prev变量指向要添加的节点的上一个节点
3.创建新节点node(prevNode=prev, 节点=element, nextNode=next)
4.连线(将第一步获取的next变量指向要添加的节点.prevNode=创建的新节点node)
- 获取要添加节点的prevNode== 空(说明要往首节点添加)
  - 将链表的firstNode赋值为创建新节点的node
- 获取要添加节点的prevNode != 空(说明不是往首节点添加)
  - 将第二步获取的prev变量.nextNode = 创建的新节点node

双向链表 - remove(int index)

双向链表删除元素，需要考虑以下情况

获取要删除节点的prevNode为空(删除首节点)
- 将链表的firstNode指向链表首节点的nextNode
获取要删除节点的prevNode不为空删除非首节点)
- 要删除节点的prevNode的nextNode = 要删除节点的nextNode(有点拗口哈哈)
获取要删除节点的nextNode为空(删除尾节点)
- 将链表的lastNode = 要删除节点的prevNode
获取要删除节点的nextNode不为空(删除非尾节点)
- 要删除节点的nextNode的prevNode = 要删除节点的prevNode(听懂没~~)

删除完成后不要忘记将链表的长度-1

完整代码

class DoubleLinkList<T: Comparable> {
    var size: Int = 0
    var firstNode: Node<T>? = nil
    var lastNode: Node<T>? = nil
    
    class Node<T> {
        var element: T
        var nextNode: Node<T>?
        var prevNode: Node<T>?
        
        init(prevNode: Node<T>?, element: T, nextNode: Node<T>?) {
            self.prevNode = prevNode
            self.element = element
            self.nextNode = nextNode
        }
    }
    
    /// 清空链表
    func clear() {
        self.size = 0
        self.firstNode = nil
        self.lastNode = nil
    }
    
    /// 删除index位置的节点
    ///
    /// - Parameter index: index
    /// - Returns: 删除的节点
    func remove(index: Int) -> T {
        let node = self.node(index: index)
        let prev = node.prevNode
        let next = node.nextNode
        
        // 首节点删除
        if prev == nil {
            self.firstNode = next
        }
        else {
            prev?.nextNode = next
        }
        
        // 尾节点删除
        if next == nil {
            self.lastNode = prev
        }
        else {
            next?.prevNode = prev
        }
        self.size = self.size - 1
        return node.element
    }
    
    /// 在index位置添加新节点
    ///
    /// - Parameters:
    ///   - index: index
    ///   - element: 节点
    func add(index: Int, element: T) {
        // 往最后节点添加元素
        if index == self.size {
            let oldLast: Node<T>? = self.lastNode
            self.lastNode = DoubleLinkList.Node(prevNode: oldLast, element: element, nextNode: nil)
            // 这是链表添加的第一个元素
            if oldLast == nil {
                self.firstNode = self.lastNode
            }
            else {
                oldLast?.nextNode = self.lastNode
            }
        }
        else {
            // 获取要添加节点
            let next = node(index: index);
            // 获取要添加节点的上一个节点
            let prev = next.prevNode;
            // 创建新节点
            let node = DoubleLinkList.Node(prevNode: prev, element: element, nextNode: next)
            // 连线
            next.prevNode = node
            
            // 如果要添加的节点在首节点(首节点.prev == nil)
            if prev == nil {
                self.firstNode = node
            }
            else {
                prev?.nextNode = node
            }
        }
        
        // 总长度+1
        self.size = self.size + 1
    }
    
    func add(element: T) {
        self.add(index: self.size, element: element)
    }
    
    /// 获取index位置的节点
    ///
    /// - Parameter index: index
    /// - Returns: 节点
    func get(index: Int) -> Node<T> {
        return self.node(index: index)
    }
    
    
    /// 根据index设置对应位置的节点
    ///
    /// - Parameters:
    ///   - index: index
    ///   - element: 节点
    /// - Returns: 旧节点值
    func set(index: Int, element: T) -> T {
        // 取出当前位置的Node
        let node: Node<T> = self.node(index: index)
        
        // 旧节点
        let oldElement: T = node.element;
        // 设置新的element
        node.element = element
        
        return oldElement
    }
    
    /// 获取节点指定的index索引
    ///
    /// - Parameter element: 节点
    /// - Returns: index
    func indexOf(element: T?) -> Int {
        if element == nil {
            var node: Node<T>? = self.firstNode
            for i in 0..<self.size {
                if node?.element == nil {
                    return i
                }
                node = node!.nextNode!
            }
        }
        else {
            var node: Node<T> = self.firstNode!
            
            for i in 0..<self.size {
                if element == node.element {
                    return i
                }
                node = node.nextNode!
            }
        }
        
        return -1
    }
    
    
    /// 根据index查找node节点
    ///
    /// - Parameter index: 索引
    /// - Returns: node节点
    private func node(index: Int) -> Node<T> {
        if index > self.size {
            // TODO: 索引检查
        }
        
        // 如果要查找的index < 当前总长度的一半
        // 说明要查找的元素在链表的左侧(往后找)
        if index < self.size >> 1 {
            var node: Node<T>? = self.firstNode
            for _ in 0..<index {
                node = node!.nextNode
            }
            return node!
        }
        else { // 要查找的元素在链表的右侧(往前找)
            var node: Node<T>? = self.lastNode
            // 从self.size-1开始，到index结束，每次-1
            for _ in stride(from: self.size-2, through: index, by: -1) {
                node = node!.prevNode
            }
            return node!
        }
    }
    
    func toString() -> Void {
        var node: Node<T>? = self.firstNode
        for _ in 0..<self.size {
            print(node?.element ?? "")
            node = node?.nextNode
        }
    }
    
    enum LinkListError: Error {
        case invalidSelection
        case insufficientFunds(coinsNeed: Int)
        case indexOutOfBounds(index: Int, size: Int)
    }
}

测试代码：

let doubleLinkedList = DoubleLinkList<String>()
doubleLinkedList.add(element: "1")
doubleLinkedList.add(element: "2")
doubleLinkedList.add(element: "3")
doubleLinkedList.add(element: "4")
doubleLinkedList.add(element: "5")

print(doubleLinkedList.get(index: 1).element) // 输出2
print("---------")
doubleLinkedList.remove(index: 3)
doubleLinkedList.toString() // 输出1 2 3 5

链表 VS 动态数组

动态数组
- 开辟、销毁内存空间的次数较少，但可能会造成内存空间浪费(可以通过缩容解决)
链表
- 开辟、销毁内存空间的次数较多，但不会造成内存空间的浪费

什么时候选择链表，什么时候选择动态数组？
1.如果频繁在尾部进行添加、删除操作，动态数组、链表均可以选择
2.如果频繁在头部进行添加、删除操作，建议选择链表
3.如果有频繁的(在任意位置)添加、删除操作，建议选择使用链表
4.如果有频繁的查询操作(随机访问操作)，建议选择使用动态数组

有了双向链表，单向链表是否就没有用处了?
并非如此，在哈希表的设计当中就用到了单向链表, 至于原因，在哈希表篇中会讲解

静态链表

前面所讲的链表，都是基于指针(引用)的方式实现的
有些编程语言是没有指针的，比如早期的BASIC、FORTRAN语言
假如不通过指针的方式，怎样去实现一个链表？ 可以通过数组来模拟链表，称为静态链表
数组里的每个元素存放2个数据: 一个是元素，另外一个是下个元素的索引

本文首次发布于孙忠良 Blog, 作者 [@sunzhongliang] , 转载请保留原文链接.