概念
链表 LinkedList 与 数组 ArrayList 一样是「表」的一种。与数组会占用一块连续内存不同的是，链表的内存占用不一定是连续的。链表由一系列节点 nodes 组成，每一个节点均含有表元素和到包含该元素后继元的节点的链，即「next 链」，这是单向链表。如果还有对前驱元的节点的引用，则为双向链表。
下面是我自己实现的双向链表。这里仿照 Swift 对 Array 的实现，给出一些常用的方法，并考虑泛型和合理的封装。
节点 ListNode
节点的结构比较简单。 element 为节点携带的元素/值，next指向后继节点， prev指向前驱节点。由于 ListNode 类的主要功能是承载链表的元素 Element 和维护对前驱、后继节点的引用，并不需要向外界暴露，因此加 private。
private class ListNode<Element> {
/// The associated value with the node.
var element: Element
/// Next node in the list.
var next: ListNode<Element>?
/// Previous node in the list.
weak var prev: ListNode<Element>?
init(_ element: Element) {
self.element = element
}
}
链表 LinkList
这里实现的是双链表，因此要维护头节点head和尾节点tail，并保存当前链表的节点总数 count。同时我们把上面 ListNode类声明在此类里。
class LinkedList<Element> {
var first: Element? {
head?.element
}
var last: Element? {
tail?.element
}
var isEmpty: Bool {
head == nil
}
private(set)
var count: Int = 0
private class ListNode<Element> { /* ... */ }
private var head: ListNode<Element>?
private var tail: ListNode<Element>?
}
常用方法
- 随机索引
getter/setter：这里使用 Swift 的 subscript 语法来实现。 注意的是，链表的随机索引时间复杂度为 O(n)，而不像数组的 O(1)。
subscript(index: Int) -> Element? {
get {
self[nodeAt: index]?.element
}
set {
if let newValue = newValue {
self[nodeAt: index] = ListNode(newValue)
} else {
self[nodeAt: index] = nil
}
}
}
private subscript(nodeAt index: Int) -> ListNode<Element>? {
get {
assert(index >= 0, "Index should be not less than 0.")
if index == 0 {
return head
} else if index == count - 1 {
return tail
} else {
if index <= count / 2 {
// Find from head.
var i: Int = 1
var curr: ListNode<Element>? = head
while curr?.next != nil, i < index {
curr = curr?.next
i += 1
}
return curr?.next
} else {
// Find from tail.
var i: Int = count - 2
var curr: ListNode<Element>? = tail
while curr?.prev != nil, index < i {
curr = curr?.prev
i -= 1
}
return curr?.prev
}
}
}
set {
assert(index >= 0, "Index should be not less than 0.")
if let newValue = newValue {
if index == 0 {
// Replace the head.
newValue.next = head?.next
head?.next?.prev = newValue
head?.next = nil
head = newValue
} else if index == count - 1 {
// Replace the tail.
newValue.prev = tail?.prev
tail?.prev?.next = newValue
tail?.prev = nil
tail = newValue
} else if let curr = self[nodeAt: index] {
newValue.next = curr.next
newValue.prev = curr.prev
curr.next?.prev = newValue
curr.prev?.next = newValue
curr.next = nil
curr.prev = nil
}
} else {
remove(at: index)
}
}
}
- 添加
append：在链表尾部添加一个新节点。时间复杂度为 O(1)。
func append(_ newElement: Element) {
append(node: ListNode(newElement))
}
private func append(node: ListNode<Element>) {
if isEmpty {
head = node
tail = node
} else {
tail?.next = node
node.prev = tail
tail = node
}
count += 1
}
- 插入
insert: 在指定位置插入一个新的节点。因为涉及在随机位置上的索引，因此时间复杂度最好情况为 O(1)，即对头尾两端的操作；一般情况为 O(n)。
func insert(_ newElement: Element, at index: Int) {
insert(node: ListNode(newElement), at: index)
}
private func insert(node: ListNode<Element>, at index: Int) {
if let curr = self[nodeAt: index] {
node.next = curr
node.prev = curr.prev
curr.prev = node
node.prev?.next = node
if index == 0 {
head = node
}
count += 1
} else if index == count {
append(node: node)
}
}
- 删除
remove：移除指定位置上的节点。同样因为涉及在随机位置上的索引，因此时间复杂度最好情况为 O(1)，最差情况为 O(n)。
func remove(at index: Int) -> Element? {
return remove(nodeAt: index)?.element
}
private func remove(nodeAt index: Int) -> ListNode<Element>? {
var result: ListNode<Element>?
if let curr = self[nodeAt: index] {
if index == 0 {
head = head?.next
} else if index == count - 1 {
tail = tail?.prev
}
curr.prev?.next = curr.next
curr.next?.prev = curr.prev
curr.prev = nil
curr.next = nil
result = curr
count -= 1
}
return result
}
- 包含
contains：判定是否包含某个元素值或引用。这要求 Element 本身是 Equatable。
extension LinkedList where Element: Equatable {
func contains(_ element: Element) -> Bool {
var curr = head
while curr != nil {
if curr?.element == element {
return true
}
curr = curr?.next
}
return false
}
}
理解
current.next： 当前节点的后继指向(setter) / 当前节点的后继节点(getter)
current.next.next：后继节点的指向(setter) / 后继节点的下一节点(getter)
技巧
有关链表的解题技巧，个人小结如下：
