数据结构学习：线性表(链式存储)

Posted on In

链表是实现线性表的链式存储结构的一种数据结构，链表根据结定义不同也有几个种类，分别为：

  • 静态链表：用于没有指针类型的语言中。
  • 单链表：链表的结点中只有指向直接后继结点的指针域。
  • 循环链表：表中最后一个结点的指针指向头结点，整个链表形成一个环。
  • 双向链表：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

以下的实例代码，都是以单链表为例的。

这篇文章的主要内容

  • 链表的一些概念
  • 链表的基本结构
  • 链表的一些操作

概念

  • 链表

    用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的。数据元素间的逻辑顺序是通过结点中的指针域来实现。

  • 结点

    存储数据元素信息的域称为数据域，把存储后继位置或前驱结点的域称为指针域。这两部分就是链表中的一个节点。

基本结构

结点的基本结构：

1
2
3
4
5
6
7
8
9
10
/// Linked List's Node Class Declaration
class LinkedListNode {
    var value: Int
    var next: LinkedListNode?
    
    public init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

链表的接本结构：

1
2
3
4
class LinkedList {
    var head: LinkedListNode?    // 头结点
    var tail: LinkedListNode?    // 尾结点
}

常用操作

先在已经定义好了链表及结点的基本结构了，下面我们可以对链表做一些常见的操作。

增加

尾插法
1
2
3
4
5
6
7
8
9
10
func appendToTail(_ value: Int) {
    let newNode = LinkedListNode(value)
    if let last = tail {
        last.next = newNode
        tail = last.next
    } else {
        head = newNode
        tail = head
    }
}
头插法
1
2
3
4
5
6
7
8
9
10
func appendToHead(_ value: Int) {
    let newNode = LinkedListNode(value)
    if let first = head {
        newNode.next = first
        head = newNode
    } else {
        head = newNode
        tail = head
    }
}
中间插入
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
28
29
30
31
32
33
34
35
36
37
38
39
40
// 给链表增加了一个长度属性
var length: Int {
    get {
        var num = 0
        var temp: LinkedListNode? = head
        while let node = temp {
            num += 1
            temp = node.next
        }
        
        return num
    }
}


func appned(_ value: Int, _ index: Int) {
    if length == 0 {
        // 链表本身为空，直接添加
        appendToHead(value)
    } else if index == 0 {
    	 // 插入到头结点位置
        let newNode = LinkedListNode(value)
        newNode.next = head
        head = newNode
    } else if index < length && index > 0 {
        // 找到需要插入位置的前一个结点
        let newNode = LinkedListNode(value)
        var temp = 1
        var tempNode: LinkedListNode? = head
        while let node = tempNode {
            if temp == index {
                newNode.next = node.next
                node.next = newNode
                break
            }
            tempNode = tempNode?.next
            temp += 1
        }
    }
}

创建

利用尾插法直接将数组元素插入到链表末端

1
2
3
init(array: [Int]) {
    array.forEach { appendToTail($0) }
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func remove(at index: Int) {
    // 链表为空
    if length == 0 {
        return
    } else if index == 0 {
        head = head?.next
    } else if index < length && index > 0 {
        var tempNode: LinkedListNode?
        var j = 0
        var tempList: LinkedListNode? = head
        while tempList?.next != nil && j < index-1 {
            tempList = tempList?.next
            j += 1
        }
        
        tempNode = tempList?.next
        tempList?.next = tempNode?.next
    }
}

查找

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
28
29
30
31
// 查找某个结点
func node(at index: Int) -> LinkedListNode? {
    if length == 0 {
        return nil
    } else if index >= 0 && index < length {
        var tempNode = head
        var j = 0
        while tempNode?.next != nil && j < index {
            tempNode = tempNode?.next
            j += 1
        }
        
        return tempNode
    }
    return nil
}

// 根据值查找
func nodes(_ value: Int) -> [LinkedListNode] {
    var result: [LinkedListNode] = []
    
    var tempNode = head
    
    while let node = tempNode {
        if node.value == value {
            result.append(node)
        }
        tempNode = node.next
    }
    return result
}

反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func reverse(_ head: LinkedListNode?) -> LinkedListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    
    // 递归找到最后一个结点
    let newHead = reverse(head?.next)
    
    // 将最后一个结点前一个结点反转
    head?.next?.next = head
    
    // 断开最后一个结点
    head?.next = nil
    
    self.head = newHead
    return newHead
}

过程说明：

为链表扩展一些操作函数

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
28
29
30
31
32
33
34
// 打印链表
func printSelf() {
    var tempNode = head
    while let node = tempNode {
        print(node.value)
        tempNode = tempNode?.next
    }
}


func map(transform: (Int) -> Int) -> LinkedList {
    let result = LinkedList()
    
    var tempNode = head
    while let node = tempNode {
        result.appendToTail(transform(node.value))
        tempNode = node.next
    }
    
    return result
}
    
func filter(predicate: (Int) -> Bool) -> LinkedList {
    let result = LinkedList()
    
    var tempNode = head
    while let node = tempNode {
        if predicate(node.value) {
            result.appendToTail(node.value)
        }
        tempNode = node.next
    }
    return result
}

总结

结合上篇线性表的顺序存储结构与单链表结构进行对比：

  • 存储方式

    • 顺序存储用一段连续的存储单元依次存储线性表的数据元素。
    • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

  • 时间性能

    • 查找
      • 顺序存储结构 O(1)
      • 单链表结构 O(n)
    • 插入和删除
      • 顺序存储结构平均需要移动表长一半的元素 O(n)
      • 单链表结构在找出某位置的指针后，插入和删除时间为O(1)

  • 空间性能

    • 顺序存储结构需要预分配存储空间，分配大了浪费空间，分配小了易造成溢出。
    • 单链表结构不需要预分配存储空间，只要有就可以分配，元素个数不受限制。