Swift实现数据结构与算法1-链表

概念

链表(Linked list)是一组数据元素(又称为节点:node)在一个线性序列中的集合,它和数组一样都是一种线性结构,但与数组不同的是,数组内元素的逻辑次序和物理存储地址是对应的,而链表则不是,相邻元素的存储地址未必相邻。为了知道每个元素的地址,上一个元素中会存储下一个元素的地址。因此相比数组访问元素是通过“寻秩访问”(call-by-rank),链表则是“循位置访问”(call-by-position),或者“循链接访问”(call-by-link)。

链表又分为单向链表、双向链表、循环链表,单链表是只有一个前进方向,只能从一个节点链接到下一个节点,而双向链表既可以链接到下一个节点,也可以链接到上一个节点。循环列表则是链表首尾也是链接的。这里只实现单向链表。
IMG_0507

性能

链表的元素读取性能是O(n),在最坏的情况下,需要遍历所有的元素,才能访问到需要的元素。
插入和删除性能是O(1),每次只需要常数的时间就能插入和删除元素。

Swift实现

根据上面的定义,我们可以知道,链表里的元素除了自身的值外,还需要指向下一个元素,所以我们可以定义Node类如下:

1
2
3
4
5
6
7
8
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
}
}

同时为了方便打印数据,我们为Node实现CustomStringConvertible协议

1
2
3
4
5
6
7
8
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}

接下来我们实现一个LinkedList类,这个类有head、trail、count三个属性,为了保护数据安全,这三个属性不允许外界直接设置,同样为其实现`CustomStringConvertible``协议:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LinkedList<Value> {

public private(set) var head: Node<Value>?
public private(set) var tail: Node<Value>?
public private(set) var count: Int = 0

public init(value: Value? = nil) {
if let value = value {
head = Node(value: value)
tail = head
count = 1
}
}

public var isEmpty: Bool {
return count == 0
}
}

extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}

如此,一个链表就定义好了,但现在只有初始化init方法,还没有查找、插入、删除等操作的方法,接下来我们来一一添加这些方法。

查找:

为了后续操作的方便,我们先添加一个查找方法,通过位置查找对应的节点。上面概念部分已经讲到,链表的存储位置和逻辑秩序是没有对应关系的,要查找某个位置的节点,只能通过前驱节点一步步找下一个节点。因此耗时是O(n),在最坏的情况下需要查找n次。具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public func node(at index: Int) -> Node<Value>? {
guard index < count else {
return 0
}

var currentIndex = 0
var currentNode = head
while currentIndex < index, currentNode != nil {
currentIndex += 1
currentNode = currentNode?.next
}
return currentNode
}

添加操作:

  1. push:添加一个元素到链表头部
  2. append:添加一个元素到链表尾部
  3. insert(after:):添加一个元素到特定节点后

做这三个操作的时候,需要注意要更新head、tail和count。
以上三个添加操作的性能都是O(1)。

IMG_0508

push

添加元素到头部,有两种情况:
一是此时链表还没有头部,还是空链表,那么就需要同时设置head和tail;
二是链表已经有头部了,就需要先把原来的头部作为新节点的下一个节点,然后在把这个节点设为head。

最后count加1。

1
2
3
4
5
6
7
8
public func push(_ value: Value) {
let newNode = Node(value: value, next: head)
head = newNode
if tail == nil {
tail = head
}
count += 1
}

append

添加元素到尾部,也是有两种情况:
一是此时链表为空,没有头部尾部,那么和push操作相同;
二是链表不为空,有尾部,那就需要把新节点设为旧尾部的下一个节点,并把新节点设为tail。
最后count加1.

1
2
3
4
5
6
7
8
9
10
11
public func append(_ value: Value) {
if isEmpty {
push(value)
return
}

let newNode = Node(value: value)
tail?.next = newNode
tail = newNode
count += 1
}

insert(after:)

添加元素到某个节点后面,需要先把该节点的next设置为新节点的next,再把新节点设为该节点的next。此时链表不为空,head不需要更新,但是要考虑是否需要更新tail,如果是添加在tail后面,那就和append操作一样,可以直接调用append方法,具体实现如下:

1
2
3
4
5
6
7
8
9
public func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
if node === tail {
append(value)
return tail!
}

node.next = Node(value: value, next: node.next)
return node.next!
}

insert(at:)

此外还可以添加节点到某个位置index,利用我们上面的查找方法,先找出index-1位置的节点,再调用上面的insert方法。此时就需要注意index == 0的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

@discardableResult
public func insert(_ value: Value, at index: Int) -> Node<Value>? {
guard count > 0 else {
push(value)
return head!
}

guard index > 0 else {
insert(value, after: head!)
return head!.next!
}

if let node = node(at: index - 1) {
return insert(value, after: node)
}

return nil
}

删除操作:

删除操作也主要是有三个:

  1. pop:删除头部节点,即head
  2. removeLast:删除尾部节点:即tail
  3. remove(after:):删除某个节点的下一个节点
  4. remove(at:):删除某个位置的节点

删除操作也需要考虑是否需要更新head和tail,同时需要给count做减1操作

以上三个删除操作中1、3的性能是O(1),2的性能是O(n)。

pop

删除头部节点,删除后,需要把head.next设置为新head,实际只需要重新设置head即可。另外需要注意tail是否需要更新,当只有一个节点时,删除一个后,tail也需要设置为nil。

1
2
3
4
5
6
7
8
9
10
11
@discardableResult
public func pop() -> Value? {
guard !isEmpty else { return nil }
let oldHead = head
head = oldHead?.next
count -= 1
if tail === oldHead {
tail = nil
}
return oldHead?.value
}

removeLast

删除最后一个节点,其实是要做两件事,一是把tail的前驱节点的next设为nil,再tail设置为前驱节点。因此这里就涉及到要找tail的前驱节点,这个查找操作就需要O(n)的时间。我们上面已经实现了一个查找方法,这里可以直接使用了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

@discardableResult
public func removeLast() -> Value? {
guard count > 1 else {
return pop()
}

let removedNode = tail
let pre = node(at: count - 2)
pre?.next = nil
tail = pre
count -= 1
return removedNode?.value
}

remove(after:)

删除一个节点的下一个节点,同样需要考虑删除的是否是尾节点,如果是,需要更新tail:

1
2
3
4
5
6
7
8
9
10
11
12
13
@discardableResult
public func remove(after node: Node<Value>) -> Value? {
defer {
if node.next === tail {
tail = node
}
node.next = node.next?.next
}
if node.next != nil {
count -= 1
}
return node.next?.value
}

remove(at:)

删除特定位置的节点,这个可以利用查找方法,找到前一个位置的node,再调用上面的remove(after:)方法即可,这里需要注意第0个位置时,需要特殊处理:

1
2
3
4
5
6
7
8
9
10
11
@discardableResult
public func remove(at index: Int) -> Value? {
guard index >= 0, index < count - 1 else { return nil }
if index == 0 {
return pop()
}
if let node = node(at: index - 1) {
return remove(after: node)
}
return nil
}