数据结构-链表

相关掌握点

• 单向链表
• 双向链表
• 反转单向链表
• 判断链表是否含有环

链表构建

链表是一种线性结构，是通过指针引用节点完成线性连接的。无论单向链表还是双向链表都需要通过节点来存储数据内容。构建链表需要以下几个基本元素：

1. 链表节点 `Node`
2. 头结点 `first`
3. 容量大小 `size`

节点构建

链表的节点链接需要指针引用，所以定义节点的时候，需要几个基本要素：

1. 用于存储节点数据的变量 element
2. 用于存储下一个节点的引用指针 next
3. 如果是双向链表的话，还需要一个前向指针引用 pre

class Node<E> {
    var next: Node?
    var pre: Node?
    var element: E?
    
    init(next: Node?, element: E?) {
        self.next = next
        self.element = element
    }
    
    convenience init(next: Node?, pre: Node?, element: E) {
        self.init(next: next, element: element)
        self.next = next
        self.pre = pre
    }
    
}

接口抽象

无论是单向链表还是双向链表，他们都有着基础的功能，所以可以将这些基本的方法功能都抽象成统一的接口以便使用，在 Swift 中可以使用协议 protocol 抽象相关的基础功能。

 enum ListRangeError: Error {
     case moreThanMax(String?)
     case lessThanMin(String?)
 }
 
 protocol ListActionProtocol : CustomStringConvertible {
     
     associatedtype E: Equatable
     var first: Node<E>? { get set }
     var size: Int { get set }
     mutating func add(element: E)
     mutating func remove(index: Int)
     mutating func remove(element: E)
     mutating func insert(index: Int, element: E)
     mutating func clear()
     func isContain(element: E) -> Bool
     func isEmpty() -> Bool
     
     init()
 }
 
 extension ListActionProtocol {
     
     var description: String {
         get {
             var des = "length: \(size), ["
             var node = first
             while node != nil {
                 let appendQuate = node?.next == nil ? "" : ","
                 des.append("\(String(describing: node?.element))\(appendQuate)")
                 node = node?.next
             }
             des.append("]")
             return des
         }
     }
     
     func isEmpty() -> Bool{
         size == 0
     }
     
     func checkRange(index: Int) throws {
         if index < 0 {
             throw ListRangeError.lessThanMin("下标越界：Min")
         }
         
         if index > size-1 && size != 0 {
             throw ListRangeError.moreThanMax("下标越界: Max")
         }
     }
 }

单向链表

实现单向链表的时候，需要注意以下几点：

1. 节点的添加可以使用 头插法

2. 删除或者插入步骤为先查找，再操作

3. 有关操作的下标超出链表容量的异常处理

   struct SignalList<E: Equatable>: ListActionProtocol, CustomStringConvertible {
       
       
       var size: Int = 0
       var first: Node<E>?
       
       init() {}
       
       mutating func add(element: E) {
           let node = Node(next: first, element: element)
           first = node
           size += 1
       }
       
       func nodeOfIndex(index: Int) -> Node<E>? {
           
           try!checkRange(index: index)
           
           var node = first
           for _ in 0 ..< index {
               node = node?.next
           }
           return node
       }
       
       mutating func remove(index: Int) {
           try!checkRange(index: index)
           //删除头结点
           if index == 0 {
               first = first?.next
           }
           
           //删除尾节点
           else if index == size-1 {
               let node = nodeOfIndex(index: index - 1 )
               node?.next = nil
           }
   
           //正常删除
           else {
               //利用间接删除,移动节点元素，删除移动的节点
               let node = nodeOfIndex(index: index)
               node?.element = node?.next?.element
               node?.next = node?.next?.next
           }
           
           size -= 1
       }
       
       mutating func remove(element: E) {
           var node = first
           var preNode = first
           while node?.next != nil {
               if node?.element == element {
                   preNode?.next = node?.next
                   size -= 1
               }
               preNode = node
               node = node?.next
           }
           
       }
       
       mutating func insert(index: Int, element: E) {
           try!checkRange(index: index)
           //头部
           if index == 0 {
               let node = Node(next: first?.next, element: element)
               first = node
               size += 1
               return
           }
           //正常插入
           let preNode = nodeOfIndex(index: index-1)
           let node = Node(next: preNode?.next, element: element)
           preNode?.next = node
           
           size += 1
           
       }
       
       mutating func clear() {
           first = nil
           size = 0
       }
       
       func isContain(element: E) -> Bool {
           var node = first
           while node?.next != nil {
               if node?.element == element {
                   return true
               }
               node = node?.next
           }
           
           return false
       }
       
   }
   
   

双向链表

相比于单向列表，双向链表在单向链表基础上增加了前向指针引用，双向链表的有点在于查找效率的提升，通过折半查找的方式进行。需要注意以下几点：

1. 增加或者删除的时候的前向指针指向问题

2. 查找可以通过折半思想提升效率

   struct DoubleList<T: Equatable>: ListActionProtocol {
       
       typealias E = T
       
       var size: Int = 0
       var first: Node<T>?
       var last: Node<T>?
       
       init() {}
       
       //头插法
       mutating func add(element: T) {
           let node = Node<T>(next: first, pre: nil, element: element)
           //注意在进行头插的时候，需要将当前的头结点的pre指针指向新的头结点保证正常指向
           first?.pre = node
           first = node
           
           if size == 0 {
               last = node
           }
           size += 1
       }
       
       func nodeOfIndex(index: Int) -> Node<E>? {
           
           if index > (self.size >> 1) {
               var node = last
               for _ in (self.size>>1..<index).reversed() {
                   node = node?.pre
               }
               
               return node
           }else{
               var node = first
               for _ in 0..<index {
                   node = node?.next
               }
               return node
           }
           
       }
       
       
       mutating func remove(index: Int) {
           try!checkRange(index: index)
           
           if index == 0 {
               first?.next?.pre = nil
               first = first?.next
           }
           
           else if index == size - 1 {
               let pre = last?.pre
               last = pre
               pre?.next = nil
           }
           
           else {
               let node = nodeOfIndex(index: index)
               node?.pre?.next = node?.next
               node?.next?.pre = node?.pre
           }
           
           size -= 1
       }
       
       mutating func remove(element: T) {
           var node = first
           while node?.next != nil {
               if node?.element == element {
                   node?.pre?.next = node?.next
                   node?.next?.pre = node?.pre
                   return
               }
               node = node?.next
           }
       
       }
       
       mutating func insert(index: Int, element: T) {
           try!checkRange(index: index)
           let indexNode = nodeOfIndex(index: index)
           let node = Node(next: indexNode, pre: indexNode?.pre, element: element)
           indexNode?.pre?.next = node
           indexNode?.next?.pre = node
       }
       
       mutating func clear() {
           self.first = nil
           self.last = nil
           self.size = 0
       }
       
       func isContain(element: T) -> Bool {
           return false
       }
       
   }
   
   

反转单向链表

对于一个链表的反转，有两种基本方案：

1. 利用递归思想依次递归逐步变更各个节点的指针达到反转目的

2. 直接遍历调整修改各个指针的指向达到反转目的

   /*
    利用递归思想
    1. 先搞清楚reverseListUseRecursive 功能是反转一个链表
    2. first.next 传入到 reverseListUseRecursive 之后是一个反转之后的链表，但是缺少了一个节点（缺少的节点刚好是first）
    3. 通过next指针引用链接缺少的节点达到所有节点的链接反转
    
    复杂度：O(n)
    */
   func reverseListUseRecursive(first: Node<Int>?) -> Node<Int>? {
   
       if first?.next == nil {
           return first
       }
       
       let newHeader = reverseListUseRecursive(first: first?.next)
       first?.next?.next = first
       first?.next = nil
       
       return newHeader
   }
   
   /*
    直接遍历，重新进行引用调整，达到反转目的。
    1. 构建的新的链表一开始为空
    2. 依次遍历原链表，将当前遍历的节点的next指针指向新的链表的头结点（当前的节点的next先用变量保存，用于下一次遍历）
    3. 新构建的链表的头指针指向当前的节点node
    4. 原链表的头指针指向当前节点的下一个节点（也即是第二个步骤保存的next）
    
     复杂度：O(n)
    */
   
   func reverseListUseEnumtor(first: Node<Int>?) -> Node<Int>? {
       
       var head = first
       var newFirst: Node<Int>?
   
       //需要注意下，此时的判定条件不是head?.next != nil
       while head != nil {
           let nextNode = head?.next
           head?.next = newFirst
           newFirst = head
           head = nextNode
       }
       
       return newFirst
   }
   

判断链表是否含有环

使用快慢指针来判定，原理类似于两个人操场跑圈，跑的快的迟早会遇到跑的慢的那位

1. 快指针迭代依次走两步

2. 慢指针迭代一次走一步

3. 按照以上两个步骤走步是最快相遇的可能

   func hasCycleLink(first: Node<Int>? ) -> Bool {
       
       if first == nil || first?.next == nil { return false }
       
       var snow = first?.next
       var fast = first?.next?.next
       
       while fast?.next != nil && fast?.next?.next != nil {
           if snow == fast { return true }
           
           snow = snow?.next
           fast = fast?.next?.next
       }
       
       return false
   }