相关掌握点
- 单向链表
- 双向链表
- 反转单向链表
- 判断链表是否含有环
链表构建
链表是一种线性结构，是通过指针引用节点完成线性连接的。无论单向链表还是双向链表都需要通过节点来存储数据内容。构建链表需要以下几个基本元素：
1. 链表节点 `Node`
2. 头结点 `first`
3. 容量大小 `size`
节点构建
链表的节点链接需要指针引用，所以定义节点的时候，需要几个基本要素：
- 用于存储节点数据的变量
element - 用于存储下一个节点的引用指针
next - 如果是双向链表的话，还需要一个前向指针引用
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")
}
}
}
单向链表
实现单向链表的时候，需要注意以下几点：
节点的添加可以使用
头插法删除或者插入步骤为先查找，再操作
-
有关
操作的下标超出链表容量的异常处理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 } }
双向链表
相比于单向列表，双向链表在单向链表基础上增加了前向指针引用，双向链表的有点在于查找效率的提升，通过折半查找的方式进行。需要注意以下几点：
增加或者删除的时候的前向指针指向问题
-
查找可以通过折半思想提升效率
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. 先搞清楚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 }
判断链表是否含有环
使用快慢指针来判定，原理类似于两个人操场跑圈，跑的快的迟早会遇到跑的慢的那位
快指针迭代依次走两步
慢指针迭代一次走一步
-
按照以上两个步骤走步是最快相遇的可能
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 }
