【譯】Swift演算法俱樂部-連結串列
本文是對 ofollow,noindex">Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club 是 raywenderlich.com 網站出品的用Swift實現演算法和資料結構的開源專案,目前在GitHub上有18000+:star:️,我初略統計了一下,大概有一百左右個的演算法和資料結構,基本上常見的都包含了,是iOSer學習演算法和資料結構不錯的資源。
:octopus: andyRon/swift-algorithm-club-cn 是我對Swift Algorithm Club,邊學習邊翻譯的專案。由於能力有限,如發現錯誤或翻譯不妥,請指正,歡迎pull request。也歡迎有興趣、有時間的小夥伴一起參與翻譯和學習 。當然也歡迎加:star:️, 。
本文的翻譯原文和程式碼可以檢視:octopus: swift-algorithm-club-cn/Linked List
連結串列(Linked List)
這個主題已經有輔導 文章
連結串列是一系列資料項,就像陣列一樣。 陣列分配了一大塊記憶體來儲存物件,而連結串列中的元素在記憶體中是完全獨立的物件,並通過連結連線:
+--------++--------++--------++--------+ |||||||| | node 0 |--->| node 1 |--->| node 2 |--->| node 3 | |||||||| +--------++--------++--------++--------+
連結串列的元素稱為 節點 。 上圖顯示了 單鏈表 ,其中每個節點只有一個引用 - 或叫做“指標” - 到下一個節點。 在 雙向連結串列 中,如下所示,節點還有指向前一個節點的指標:
+--------++--------++--------++--------+ ||--->||--->||--->|| | node 0 || node 1 || node 2 || node 3 | ||<---||<---||<---|| +--------++--------++--------++--------+
您需要跟蹤連結串列的開始位置。 這通常用一個名為 head 的指標完成:
+--------++--------++--------++--------+ head --->||--->||--->||--->||---> nil | node 0 || node 1 || node 2 || node 3 | nil <---||<---||<---||<---||<--- tail +--------++--------++--------++--------+
引用連結串列末尾也很有用,稱為 tail 。 注意,最後一個節點的“下一個”指標是 nil
,第一個節點的“前一個”指標也是 nil
。
連結串列的效能
連結串列上的大多數操作時間複雜度都是 O(n) ,因此連結串列通常比陣列慢。但是,它們也更加靈活 —— 而不是像陣列一樣複製大塊記憶體,連結串列上的許多操作只需要更改幾個指標。
時間複雜度是 O(n) 的原因是你不能簡單地寫 list[2]
來從連結串列中訪問節點2。 如果你已經沒有對該節點的引用,你必須從 head
開始,然後按照 next
指標逐個訪問(或者從 tail
開始,使用 previous
指標,逐個訪問並找到指定節點)。
但是一旦你有一個節點的引用,插入和刪除等操作真的很快。 只是尋找節點慢。
這意味著當您處理連結串列時,應儘可能在前面插入新專案。 這是 O(1) 操作。 如果你跟蹤 tail
指標,同樣可以在後面插入。
單鏈表 vs 雙鏈表
單鏈表使用比雙鏈表使用更少的記憶體,因為它不需要儲存所有那些 previous
指標。
但是如果你需要找到一個節點以前的節點,你就搞砸了。 您必須從頭部開始並遍歷整個連結串列,直到到達正確的節點。
對於許多工,雙向連結串列使事情變得更容易。
為什麼使用連結串列?
使用連結串列的典型示例是 佇列 。 使用陣列,從佇列前面刪除元素很慢,因為它需要向下移動記憶體中的所有其他元素。 但是通過連結連結串列,只需將 head
更改為指向第二個元素即可。 快多了。
但說實話,現在你幾乎不需要編寫自己的連結串列。 不過,瞭解它們的工作方式仍然很有用; 將物件連結在一起的原則也與 樹 和 圖 一起使用。
程式碼
我們首先定義一個描述節點的型別:
public class LinkedListNode<T> { var value: T var next: LinkedListNode? weak var previous: LinkedListNode? public init(value: T) { self.value = value } }
這是一種泛型型別,因此 T
可以是您想要儲存在節點中的任何型別的資料。 我們將在後面的示例中使用字串。
這邊定義的是一個雙向連結串列,每個節點都有一個 next
和 previous
指標。 如果沒有下一個或前一個節點,則這些可以是 nil
,因此這些變數必須是可選項。 (在下文中,我將指出哪些函式需要更改,如果這只是單個而不是雙向連結串列。)
注意:為避免迴圈強引用,我們宣告 previous
指標為弱。 如果連結串列中有一個節點 A
後面跟著節點 B
,那麼 A
指向 B
,而 B
指向 A
。 在某些情況下,即使在刪除節點後,此迴圈強引用也可能導致節點保持活動狀態。 我們不希望這樣,所以我們使其中一個指標 weak
來打破迴圈。
讓我們開始構建 LinkedList
。 這是第一點:
public class LinkedList<T> { public typealias Node = LinkedListNode<T> private var head: Node? public var isEmpty: Bool { return head == nil } public var first: Node? { return head } }
理想情況下,我們希望類名儘可能具有描述性,但是,我們不希望每次要使用類時都打長名稱,因此,我們在 LinkedList
中給 LinkedListNode<T>
定義了一個短的別名 Node
。
這個連結串列只有一個 head
指標,沒有尾部。 新增尾指標留給讀者練習。 (如果我們還有一個尾指標,我會指出哪些函式會有所不同。)
如果 head
為nil,則連結串列為空。 因為 head
是一個私有變數,所以我添加了屬性 first
來返回對連結串列中第一個節點的引用。
在playground中測試:
let list = LinkedList<String>() list.isEmpty// true list.first// nil
我們還新增一個屬性,為您提供連結串列中的最後一個節點。 這是將開始變得有趣了:
public var last: Node? { guard var node = head else { return nil } while let next = node.next { node = next } return node }
如果你是Swift的新手,你可能已經看過 if let
但也許不是 if var
。 它做了同樣的事情 - 它解開 head
可選項並將結果放入一個名為 node
的新區域性變數中。 區別在於 node
不是常量而是當前執行環境下的變數,因此我們可以在迴圈內更改它。
迴圈也做了一些Swift魔法。 while let next = node.next
保持迴圈,直到 node.next
為 nil
。 您可以寫如下:
var node: Node? = head while node != nil && node!.next != nil { node = node!.next }
但這對我來說並不是很開心。 我們可以很好地利用Swift對解包選項的內建支援。 你會在隨後的程式碼中看到一堆這樣的迴圈。
注意:如果我們保留一個尾指標, last
只會做 return tail
。 但我們沒有,所以它必須從頭到尾逐步完成整個連結串列。這是一項昂貴的操作,特別是如果連結串列很長的話。
當然, last
只返回nil,因為連結串列中沒有任何節點。 讓我們新增一個方法,將新節點新增到連結串列的末尾:
public func append(value: T) { let newNode = Node(value: value) if let lastNode = last { newNode.previous = lastNode lastNode.next = newNode } else { head = newNode } }
append()
方法首先建立一個新的 Node
物件,然後請求我們剛剛新增的最後一個節點 last
屬性。 如果沒有這樣的節點,連結串列仍然是空的,我們使 head
指向這個新的 Node
。但是如果我們確實找到了一個有效的最後節點物件,我們連線 next
和 previous
指標將這個新節點連結到鏈中。許多連結串列程式碼涉及這種 next
和 previous
指標操作。
在playground中測試:
list.append("Hello") list.isEmpty// false list.first!.value// "Hello" list.last!.value// "Hello"
The list looks like this:
這個連結串列目前看上去是:
+---------+ head --->||---> nil | "Hello" | nil <---|| +---------+
增加第二個節點:
list.append("World") list.first!.value// "Hello" list.last!.value// "World"
現在連結串列看上去是:
+---------++---------+ head --->||--->||---> nil | "Hello" || "World" | nil <---||<---|| +---------++---------+
您可以通過檢視 next
和 previous
指標來自行驗證:
list.first!.previous// nil list.first!.next!.value// "World" list.last!.previous!.value// "Hello" list.last!.next// nil
讓我們新增一個方法來計算連結串列中有多少個節點。 這與我們已經完成的工作非常相似:
public var count: Int { guard var node = head else { return 0 } var count = 1 while let next = node.next { node = next count += 1 } return count }
它以相同的方式迴圈遍歷連結串列,但這次增加了一個計數器。
注意:加快獲得 count
的速度(從 O(n) 到 O(1) )的一種方法是跟蹤一個計算連結串列中有多少節點的變數。 無論何時新增或刪除節點,都會更新此變數。
如果我們想在連結串列中的特定索引處找到節點,該怎麼辦?使用陣列我們可以編寫一個 O(1) 操作 array[index]
。這更多地涉及連結連結串列,但程式碼遵循類似的模式:
public func node(atIndex index: Int) -> Node { if index == 0 { return head! } else { var node = head!.next for _ in 1..<index { node = node?.next if node == nil { //(*1) break } } return node! } }
首先,我們檢查給定的索引是否為0。 因為如果它是0,它會按原樣返回head。
但是,當給定索引大於0時,它從頭開始,然後繼續追蹤node.next指標逐步執行連結串列。
與此時計數方法的不同之處在於存在兩種終止條件。
一種是當for迴圈語句到達索引時,我們能夠獲取給定索引的節點。
第二個是 for-loop
語句中的 node.next
返回nil並導致break。( *1
)
這意味著給定的索引超出範圍並導致崩潰。
測試一下:
list.nodeAt(0)!.value// "Hello" list.nodeAt(1)!.value// "World" // list.nodeAt(2)// crash
為了好玩,我們也可以實現 subscript
(下標)方法:
public subscript(index: Int) -> T { let node = node(atIndex: index) return node.value }
現在可以編寫如下內容:
list[0]// "Hello" list[1]// "World" list[2]// crash!
它在 list [2]
上崩潰,因為該索引上沒有節點。
到目前為止,我們已經編寫了將新節點新增到連結串列末尾的程式碼,但這很慢,因為您需要先找到連結串列的末尾。(如果我們使用尾指標會很快。)因此,如果連結串列中專案的順序無關緊要,則應在連結串列的前面執行插入操作。 這總是一個 O(1) 操作。
讓我們編寫一個方法,允許您在連結串列中的任何索引處插入新節點。
public func insert(_ node: Node, at index: Int) { let newNode = node if index == 0 { newNode.next = head head?.previous = newNode head = newNode } else { let prev = self.node(at: index-1) let next = prev.next newNode.previous = prev newNode.next = prev.next prev.next = newNode next?.previous = newNode } }
與 node(at:)
方法一樣, insert(_:at:)
方法也會根據索引引數是否為0進行判斷。
首先讓我們來看看前一種情況(譯註:也就是 index == 0
,插入最前面的情況)。 假設我們有以下連結串列和新節點(C)。
+---------++---------+ head --->||---->||-----//-----> |A||B| nil <---||<----||<----//------ +---------++---------+ [0][1] +---------+ new --->||----> nil |C| || +---------+
現在將新節點放在第一個節點之前。 通過這種方式:
new.next = head head.previous = new +---------++---------++---------+ new --->||--> head -->||---->||-----//-----> |C||A||B| ||<-----------||<----||<----//------ +---------++---------++---------+
最後,用新節點作為頭部。
head = new +---------++---------++---------+ head --->||--->||---->||-----//-----> |C||A||B| nil <---||<---||<----||<----//------ +---------++---------++---------+ [0][1][2]
但是,當給定索引大於0時,必須獲取節點的上一個和下一個索引並在它們之間插入。
您還可以使用 node(at:)
獲取上一個和下一個節點,如下所示:
+---------++---------++---------+ head --->||---//--->||---->||---- |||A||B| nil <---||---//<---||<----||<--- +---------++---------++---------+ [0][index-1][index] ^^ || prevnext prev = node(at: index-1) next = prev.next
現在在prev和next之間插入新節點。
new.prev = prev; prev.next = new// connect prev and new. new.next = next; next.prev = new// connect new and next. +---------++---------++---------++---------+ head --->||---//--->||---->||---->|| |||A||C||B| nil <---||---//<---||<----||<----|| +---------++---------++---------++---------+ [0][index-1][index][index+1] ^^^ ||| prevnewnext
測試:
list.insert(LinedListNode(value: "Swift"), at: 1) list[0]// "Hello" list[1]// "Swift" list[2]// "World
還可以嘗試在連結串列的前面和後面新增新節點,以驗證其是否正常工作。
注意: node(at:)
和 insert(_:at:)
函式也可以與單鏈表一起使用,因為我們不依賴於節點的 previous
指標來查詢前一個元素。
我們還需要什麼? 當然要刪除節點! 首先我們要做 removeAll()
,這很簡單:
public func removeAll() { head = nil }
如果你有一個尾指標,你也可以在這裡設定為 nil
。
接下來,我們將新增一些可以刪除單個節點的函式。 如果你已經有了對節點的引用,那麼使用 remove()
是最優的,因為你不需要遍歷連結串列來首先找到節點。
public func remove(node: Node) -> T { let prev = node.previous let next = node.next if let prev = prev { prev.next = next } else { head = next } next?.previous = prev node.previous = nil node.next = nil return node.value }
當我們將此節點從連結串列中取出時,我們將斷開指向上一個節點和下一個節點的連結。 要使連結串列再次完整,我們必須將前一個節點連結到下一個節點。
不要忘記 head
指標! 如果這是連結串列中的第一個節點,則需要更新 head
以指向下一個節點。 (同樣,當你有一個尾指標,這是最後一個節點)。 當然,如果沒有剩餘的節點, head
應該變為 nil
。
嘗試一下:
list.remove(node: list.first!)// "Hello" list.count// 2 list[0]// "Swift" list[1]// "World"
如果你沒有對節點的引用,你可以使用 removeLast()
或 removeAt()
:
public func removeLast() -> T { assert(!isEmpty) return remove(node: last!) } public func remove(at index: Int) -> T { let node = self.node(at: index) return remove(node: node) }
所有這些刪除函式都返回已刪除元素的值。
list.removeLast()// "World" list.count// 1 list[0]// "Swift" list.remove(at: 0)// "Swift" list.count// 0
注意:對於單鏈表,刪除最後一個節點稍微複雜一些。 您不能只使用 last
來查詢連結串列的末尾,因為您還需要對倒數第二個節點的引用。 相反,使用 nodesBeforeAndAfter()
輔助方法。 如果連結串列有一個尾指標,那麼 removeLast()
非常快,但你需要記住讓 tail
指向前一個節點。
我們的 LinkedList
類還可以做一些有趣的事情。 一些很方便可讀的除錯輸出:
extension LinkedList: CustomStringConvertible { public var description: String { var s = "[" var node = head while node != nil { s += "\(node!.value)" node = node!.next if node != nil { s += ", " } } return s + "]" } }
這將如下形式列印連結串列:
[Hello, Swift, World]
如何反轉連結串列,使頭部成為尾部,反之亦然? 有一個非常快速的演算法:
public func reverse() { var node = head tail = node// If you had a tail pointer while let currentNode = node { node = currentNode.next swap(¤tNode.next, ¤tNode.previous) head = currentNode } }
這迴圈遍歷整個連結串列,並簡單地交換每個節點的 next
和 previous
指標。 它還將 head
指標移動到最後一個元素。 (如果你有一個尾部指標,你還需要更新它。)你最終得到這樣的東西:
+--------++--------++--------++--------+ tail --->||<---||<---||<---||---> nil | node 0 || node 1 || node 2 || node 3 | nil <---||--->||--->||--->||<--- head +--------++--------++--------++--------+
陣列有 map()
和 filter()
函式,那麼沒有理由說連結連結串列沒有。
public func map<U>(transform: (T) -> U) -> LinkedList<U> { let result = LinkedList<U>() var node = head while node != nil { result.append(transform(node!.value)) node = node!.next } return result }
使用如下:(譯註:建立一個新連結串列,用來存放之前連結串列中字串的長度)
let list = LinkedList<String>() list.append("Hello") list.append("Swifty") list.append("Universe") let m = list.map { s in s.count } m// [5, 6, 8]
filter()
函式:
public func filter(predicate: (T) -> Bool) -> LinkedList<T> { let result = LinkedList<T>() var node = head while node != nil { if predicate(node!.value) { result.append(node!.value) } node = node!.next } return result }
一個簡單的使用例子:(譯註:篩選出連結串列中字串長度大於5的元素並組成新的連結串列)
let f = list.filter { s in s.count > 5 } f// [Universe, Swifty]
為讀者練習: map()
和 filter()
的這些實現不是很快,因為它們將新節點追加到新連結串列的末尾。 回想一下,append是 O(n) ,因為它需要掃描整個連結串列以找到最後一個節點。 你能加快速度嗎? (提示:跟蹤您新增的最後一個節點。)
另一種方法
到目前為止,您看到的 LinkedList
版本使用的是類,具有引用語義。 這沒有什麼不對,但這確實使它們比Swift的其他集合(例如 Array
和 Dictionary
)更重要。( 譯註: 這裡應該是想表達, Array
和 Dictionary
都是結構體,連結串列也可以使用結構體和列舉實現)
可以使用列舉實現具有值語義的連結串列。 這看起來有點像這樣:
enum ListNode<T> { indirect case node(T, next: ListNode<T>) case end }
與基於類的版本的最大區別在於,您對此連結串列所做的任何修改都將導致建立 新副本 。 這是否是您想要的取決於應用程式。
[如果有需求,我可能會更詳細地填寫此部分。]
符合Collection協議
符合Sequence協議的型別,其元素可以多次遍歷。非破壞性地通過索引的下標訪問,應該符合Swift標準庫中定義的Collection協議。
這樣做可以訪問處理資料集合時常見的大量屬性和操作。 除此之外,它還允許自定義型別遵循Swift開發人員常用的模式。
為了符合這個協議,類需要提供:
1 startIndex
和 endIndex
屬性。
2 對元素的下標訪問為O(1)。 需要記錄這種時間複雜性的變化。
/// The position of the first element in a nonempty collection. public var startIndex: Index { get { return LinkedListIndex<T>(node: head, tag: 0) } } /// The collection's "past the end" position---that is, the position one /// greater than the last valid subscript argument. /// - Complexity: O(n), where n is the number of elements in the list. ///This diverts from the protocol's expectation. public var endIndex: Index { get { if let h = self.head { return LinkedListIndex<T>(node: h, tag: count) } else { return LinkedListIndex<T>(node: nil, tag: startIndex.tag) } } }
public subscript(position: Index) -> T { get { return position.node!.value } }
因為集合負責管理自己的索引,下面的實現保留對連結串列中節點的引用。 索引中的標記屬性表示連結串列中節點的位置。
/// Custom index type that contains a reference to the node at index 'tag' public struct LinkedListIndex<T> : Comparable { fileprivate let node: LinkedList<T>.LinkedListNode<T>? fileprivate let tag: Int public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool { return (lhs.tag == rhs.tag) } public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool { return (lhs.tag < rhs.tag) } }
最後,連結能夠通過以下實現計算給定的索引之後的索引。
public func index(after idx: Index) -> Index { return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag+1) }
要注意的一些事情
連結連結串列是靈活的,但許多操作是 O(n) 。
在連結串列上執行操作時,您總是需要小心更新相關的 next
和 previous
指標,還可能更新 head
和 tail
指標。 如果你搞砸了,你的連結串列將不再正確,你的程式可能會在某些時候崩潰。 小心!
處理連結串列時,通常可以使用遞迴:處理第一個元素,然後在連結串列的其餘部分再次遞迴呼叫該函式。 當沒有下一個元素時你就完成了。 這就是連結串列是LISP等函數語言程式設計語言的基礎的原因。
作者:Matthijs Hollemans
翻譯: Andy Ron
校對: Andy Ron