一個鏈表就是一串節(jié)點(diǎn)(Node). 每個Node有兩個責(zé)任：
- 持有一個value
- 持有下一個Node的引用。nil表示鏈表最后一個Node
先寫一個工具方法方便打印
func example(of desc: String,block: (()->Void)){
print("---Example of \(desc)---")
block()
}
創(chuàng)建一個基本的Node類, 并重寫description
public class Node<Value> {
public var value: Value
public var next: Node?
public init(value: Value,next: Node? = nil) {
self.value = value
self.next = next
}
}
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next)
}
}
嘗試創(chuàng)建幾個Node并將他們鏈接起來。
example(of: "creating and linking nodes") {
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
print(node1)
}
控制臺輸出
---Example of creating and linking nodes---
1 -> 2 -> 3
這個離我們想要的還差很遠(yuǎn)，如果list比較長，創(chuàng)建起來將會是災(zāi)難性的。所以我們應(yīng)該用一個LinkedList將Node管理起來。
創(chuàng)建LinkList
public struct LinkedList<Value> {
public var head: Node<Value>?
public var tail: Node<Value>?
public init(){}
public var isEmpty: Bool {
return head == nil
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}
一個LinkedList 只需要知道頭和尾，就能確定整個鏈表。
如何給鏈表添加數(shù)據(jù)呢，三種方式：
-
push:從head處添加 -
append:從tail處添加 -
insert(after:)指定位置添加
push 操作
extension LinkedList {
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
if tail == nil {
tail = head
}
}
}
從頭部添加很簡單，只需要重新設(shè)置head并將之前的head設(shè)置為next，考慮到鏈表元素只有一個的情況。tail即使head。
example(of: "push") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print(list)
}
// result:
---Example of push---
1 -> 2 -> 3
append 操作
extension LinkedList {
public mutating func append(_ value: Value){
guard !isEmpty else {
push(value)
return
}
tail?.next = Node(value: value)
tail = tail?.next
}
}
首先考慮鏈表為空的情況，如果不為空則直接將Node賦值給當(dāng)前的tail?.next，而此Node也作為新的tail。
example(of: "append") {
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)
print(list)
}
// result:
---Example of append---
1 -> 2 -> 3
insert(after:) 操作
再新增一個便利方法node(at:)
extension LinkedList {
// 只有空list或者index超過邊界才會返回nil
public func node(at index: Int) -> Node<Value>? {
var currentNode = head
var currentIndex = 0
while currentNode != nil && currentIndex < index {
currentNode = currentNode?.next
currentIndex += 1
}
return currentNode
}
@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
guard tail !== node else {
append(value)
return tail!
}
node.next = Node(value: value, next: node.next)
return node.next!
}
}
insert(after:)的思想也很簡單，如果傳進(jìn)來的Node就是tail，則相當(dāng)于執(zhí)行一個append。剩下就是把傳進(jìn)來的Node的next設(shè)置為value， value的next設(shè)置為node.next。
example(of: "inserting at a particular index") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before inserting: \(list)")
var middleNode = list.node(at: 1)!
for _ in 1...4 {
middleNode = list.insert(-1, after: middleNode)
}
print("After inserting: \(list)")
}
// result:
---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3
方法性能分析
| 方法 | 時間復(fù)雜度 |
|---|---|
| push | O(1) |
| append | O(1) |
| insert(after:) | O(1) |
| node(at:) | O(i) i表示給定的index |
性能看起來都不錯。
從鏈表中刪除數(shù)據(jù)
也是三個方法
-
pop從表頭刪除 -
removeLast從結(jié)尾刪除 -
remove(after:)任意位置刪除
pop 操作
跟push一樣 非常簡單。
extension LinkedList {
public mutating func pop() -> Value?{
defer {
head = head?.next
if isEmpty {
tail = nil
}
}
return head?.value
}
}
如果是只有一個元素或者空元素的列表head?.next就為nil。這時候需要設(shè)置tail為nil。
example(of: "pop") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before popping list: \(list)")
let poppedValue = list.pop()
print("After popping list: \(list)")
print("Popped value: " + String(describing: poppedValue))
}
// result:
---Example of pop---
Before popping list: 1 -> 2 -> 3
After popping list: 2 -> 3
Popped value: Optional(1)
removeLast 操作
這個方法會有點(diǎn)麻煩，我們雖然保存了tail但是并不知道tail的上一個元素。所以這里只能用遍歷的方法
extension LinkedList {
public mutating func removeLast() -> Value? {
guard let head = head else {
return nil
}
guard head.next != nil else {
// 只有一個元素的情況
return pop()
}
var prev = head
var current = head
// 循環(huán)取next直到?jīng)]有next
while let next = current.next {
prev = current
current = next
}
prev.next = nil
tail = prev
return current.value
}
}
注釋已經(jīng)很清楚了。
example(of: "removing the last node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before removing last node: \(list)")
let removedValue = list.removeLast()
print("After removing last node: \(list)")
print("Removed value: " + String(describing: removedValue))
}
// result:
---Example of removing the last node---
Before removing last node: 1 -> 2 -> 3
After removing last node: 1 -> 2
Removed value: Optional(3)
removeLast需要把整個list遍歷一遍，所以這里的時間復(fù)雜度為 O(n)
remove(after:) 操作
這個跟insert(after:)差不多，都是比較簡單
extension LinkedList {
@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
defer {
if node.next === tail {
tail = node
}
node.next = node.next?.next
}
return node.next?.value
}
}
如果移除的Node的下一個是tail，直接將tail設(shè)置為此node。并將node的下一個設(shè)置為下下個。
example(of: "removing a node after a particular node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before removing at particular index: \(list)")
let index = 1
let node = list.node(at: index - 1)!
let removedValue = list.remove(after: node)
print("After removing at index \(index): \(list)")
print("Removed value: " + String(describing: removedValue))
}
// result:
---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: Optional(2)
方法性能分析
| 方法 | 時間復(fù)雜度 |
|---|---|
| pop | O(1) |
| removeLast | O(n) |
| remove(after:) | O(1) |
更swifty的方式
Collection protocol提供了很多便利的方式去訪問和操作列表。這里也可以讓自己的LinkedList實(shí)現(xiàn)Collection 協(xié)議。
因?yàn)殒湵聿僮鞯氖?code>Node，所以我們的Index需要自定義下。
extension LinkedList: Collection {
public struct Index: Comparable {
public var node: Node<Value>?
static public func == (lhs: Index, rhs: Index) -> Bool{
switch (lhs.node,rhs.node) {
case let (left?,right?):
return left.next === right.next
case (nil,nil):
return true
default:
return false
}
}
static public func < (lhs: Index,rhs: Index) -> Bool {
guard lhs != rhs else {
return false
}
let nodes = sequence(first: lhs.node) { $0?.next }
return nodes.contains(where: { $0 === rhs.node })
}
}
public var startIndex: Index {
return Index(node: head)
}
public var endIndex: Index {
return Index(node: tail?.next)
}
public func index(after i: Index) -> Index {
return Index(node: i.node?.next)
}
public subscript(position: Index) -> Value {
return position.node!.value
}
}
這里Index持有Node并實(shí)現(xiàn) Comparable協(xié)議 。 再實(shí)現(xiàn)Collection 的幾個必要的方法。就可以使用了。
example(of: "using collection") {
var list = LinkedList<Int>()
for i in 0...0{
list.append(i)
}
print("List: \(list)")
print("First element: \(list[list.startIndex])")
print("Array containing first 3 elements: \(Array(list.prefix(3)))")
print("Array containing last 3 elements: \(Array(list.suffix(3)))")
let sum = list.reduce(0, +)
print("Sum of all values: \(sum)")
}
// result:
---Example of using collection---
List: 0
First element: 0
Array containing first 3 elements: [0]
Array containing last 3 elements: [0]
Sum of all values: 0
Swift中的Collection為值類型，使用copy-on-write機(jī)制實(shí)現(xiàn)的。
例子：
example(of: "array cow") {
let array1 = [1, 2]
var array2 = array1
print("array1: \(array1)")
print("array2: \(array2)")
print("---After adding 3 to array 2---")
array2.append(3)
print("array1: \(array1)")
print("array2: \(array2)")
}
// result:
---Example of array cow---
array1: [1, 2]
array2: [1, 2]
---After adding 3 to array 2---
array1: [1, 2]
array2: [1, 2, 3]
這里可以看到array2執(zhí)行append方法，列表改變了，但是array1并沒有改變。這是值類型的特質(zhì)。array2 本質(zhì)是在 append 方法調(diào)用的時候才真正copy。在append方法執(zhí)行前，array1和array2都指向同一個地址。
再來看下LinkedList
example(of: "linked list cow") {
var list1 = LinkedList<Int>()
list1.append(1)
list1.append(2)
var list2 = list1
print("List1: \(list1)")
print("List2: \(list2)")
print("After appending 3 to list2")
list2.append(3)
print("List1: \(list1)")
print("List2: \(list2)")
}
// result:
---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2 -> 3
List2: 1 -> 2 -> 3
我們自己寫的鏈表并沒有值類型的特質(zhì)，是因?yàn)槲覀兊?code>Node是使用class（引用類型）實(shí)現(xiàn)的。
一個方法就是在我們每次操作新增或者刪除某個Node之前，將所有元素更新一遍
extension LinkedList {
private mutating func copyNodes(){
guard var oldNode = head else {
return
}
head = Node(value: oldNode.value)
var newNode = head
while let nextOldNode = oldNode.next {
newNode?.next = Node(value: nextOldNode.value)
newNode = newNode?.next
oldNode = nextOldNode
}
tail = newNode
}
}
在所有包含mutating的方法前調(diào)用copyNodes 。但是這樣相當(dāng)于在所有方法時間復(fù)雜度前提下增加了一個O(n)。明顯是不可接受的。
所以這里還可以對此進(jìn)行優(yōu)化。
isKnownUniquelyReferenced
isKnownUniquelyReferenced方法可以判斷是否只有被一個對象引用。沒有共享，這樣我們只需要在兩個對象同時引用的情況下才需要使用值類型的特點(diǎn)。
在copyNodes最上面加上
guard !isKnownUniquelyReferenced(&head) else {
return
}
這樣大部分情況下就不會復(fù)制。
- 對方法進(jìn)行評估
push方法并不會造成兩者不一樣。
example(of: "linked list cow") {
var list1 = LinkedList<Int>()
list1.append(1)
list1.append(2)
var list2 = list1
print("List1: \(list1)")
print("List2: \(list2)")
print("After appending 3 to list2")
list2.push(0)
print("List1: \(list1)")
print("List2: \(list2)")
}
// result:
---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2
List2: 0 -> 1 -> 2
所以在push中并不需要調(diào)用copyNodes
參考自《Data Structure & Algorithms in Swift》
