Data Structure(一) Linked List

发表于 | 分类于

代码地址

链表

链表是数据结构中经常会用到的一种数据结构，是指一串数据项，每一个数据项称之为节点（Node）。

链表主要有两种：

单链表，链表中的每个节点只有向后的索引

双链表，链表除了向后的索引之外，还有指向前一个的索引

定义节点

链表是有节点组成的，首先定义节点的数据结构： Node

  1. 首先将节点定义为一个类 - Node
  2. 添加值，并添加一个初始化方法
  3. 要有一个指针 next 指向下一个节点，注意这个指针必须是可选类型，因为链表最后的一个 Node 的 next 指针不指向任何 Node
1
2
3
4
5
6
7
public class Node {
    var val: Int
    var next: Node?
    init(_ val: Int) {
        self.val = val
    }
}

如果是双向链表，还需要定义 previous 指针：

1
2
3
4
5
6
7
8
9
10
public class Node {
    
    var value: Int
    var next: Node?
    weak var previous: Node?
    
    public init(_ value: Int) {
        self.value = value
    }
}

这里 previous 使用 weak 是为了防止循环引用

定义链表

定义链表，有两个节点 head 和 tail

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

//链表
public class LinkedList {
    
    fileprivate var head: Node?
    private var tail: Node?
    
    public var first: Node? {
        return head
    }
    
    public var last: Node? {
        return tail
    }
}

空链表

1
2
3
public var isEmpty: Bool {
    return head == nil
}

添加测试代码：

1
2
3
4
5
6
7
8
9
//测试
testList()

func testLinkedList () {
    let link = LinkedList()
    assert(link.isEmpty, "空链表")
}

testLinkedList()

添加节点

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

public func append(_ value: Int) {
    let newNode = Node(value)
    
    if let tailNode = tail {
        newNode.previous = tailNode
        tailNode.next = newNode
    }
    else {
        head = newNode
    }
    tail = newNode
}

说明：

  • 首先根据传入的 value， 创建一个新的节点
  • 如果 tail 不为 nil，就说明当前的链表内有内容，所以执行插入操作
  • 插入操作：newNode 的 previous 指向 tail，tail 的 next 指针指向 newNode，并且设置 newNode 为新的 tail
  • 如果 tail 为 nil， 就说明当前链表为空链表，直接设置 head 为 newNode 就可以了，然后设置 tail 为 newNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//测试
func testLinkedListAppend() {
    
    let link = LinkedList()
    link.append(10)
    assert(!link.isEmpty, "非空链表")
    
    assert(link.first?.value == 10, "head 节点为 10")
    assert(link.last?.value == 10, "tail 节点为 10")
    link.append(20)
    assert(link.last?.value == 20, "tail 节点为 20")
    link.append(30)
    assert(link.last?.value == 30, "tail 节点为 30")
}

testLinkedListAppend()

输出链表

当我们学会插入节点之后，第一时间就行看看链表中的内容。目前如果只是简单的 print(link) 的话是不能打印出处链表的信息的，为了实现输出链表信息，做如下操作：

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

extension LinkedList: CustomStringConvertible {
    public var description: String {
        
        var text = "["
        var node = head
        
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil { text += " -> " }
        }
        
        return text + "]"
    }
}

说明：

  • 首先为 LinkedList 声明 extension，然后实现 CustomStringConvertible 协议，这个协议要求你实现 computed property description：String
  • 所以在 extension 内部，声明可计算属性 description，类型为 String，并且该属性是只读属性
  • 然后在内容通过对 linkedList 的遍历以及字符串拼接，返回需要输出的链表格式

测试：

1
2
3
4
5
6
7
let link1 = LinkedList()
link1.append(1)
link1.append(2)
link1.append(3)
link1.append(4)

print(link1) // output: [1 -> 2 -> 3 -> 4]

playground 自动显示

查找节点

根据输入链表中 node 的位置返回 node object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public func nodeAt(_ index: Int) -> Node? {

    if index >= 0 {
        
        var node = head
        var i = index
        
        while node != nil {
            if i == 0 {return node}
            i = i - 1
            node = node!.next
        }
    }
    return nil
}

说明：

  • 首先剔除 index 为负数的情况，返回 nil
  • 接着通过 node ！= nil 来进行循环，然后通过 index 自减是否为零来进行判断

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func testNodeAt () {
    let link = LinkedList()
    link.append(0)
    link.append(1)
    link.append(2)
    link.append(3)
    
    assert(link.nodeAt(0)?.value == 0, "node[0] = 0")
    assert(link.nodeAt(1)?.value == 1, "node[1] = 1")
    assert(link.nodeAt(3)?.value == 3, "node[3] = 3")
    assert(link.nodeAt(8) == nil , "找不到")
    assert(link.nodeAt(-1) == nil , "找不到")
}

testNodeAt()

删除所有节点

1
2
3
4
public func removeAll() {
    head = nil
    tail = nil
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func testRemoveAll () {
    
    let link = LinkedList()
    link.append(0)
    link.append(1)
    link.append(2)
    link.append(3)
    
    link.removeAll()
    
    assert(link.isEmpty, "空")
    assert(link.first == nil, "first")
    assert(link.last == nil, "last")
    assert(link.nodeAt(Int(arc4random())) == nil , "anynoe")
    
}

testRemoveAll()

删除指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public func remove(_ node: Node) -> Int {
    let prev = node.previous
    let next = node.next
    
    if let prev = prev {
        prev.next = next
    }else {
        //如果删除的是 first
        head = next
    }
    
    next?.previous = prev
    //如果删除的是 last
    if  next == nil {
        tail = prev
    }
    
    node.previous = nil
    node.next = nil
    
    return node.value
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func testRemove () {
    
    let link = LinkedList()
    link.append(0)
    link.append(1)
    link.append(2)
    link.append(3)
    
    let value = link.remove(link.nodeAt(2)!)
    assert(value == 2,"删除")
    assert(link.last?.value == 3,"删除")
    link.remove(link.last!)
    assert(link.last?.value == 1, "删除最后一个node，最后一个node 变为 1")
    link.remove(link.first!)
    assert(link.last?.value == 1, "删除第一个node，第一个node 变为 1")

}

testRemove()

参考：

  1. Swift Algorithm Club: Swift Linked List Data Structure
-------------本文结束谢谢欣赏-------------
Alice wechat
微信公众号还没弄好，先放上二维码吧！