线性表

数组

数组是内存里一组有序的集合. 数组最大的优点是支持随机访问, 这是和链表最大的区别, 访问做任意一个结点总是 O(1), 缺点是在插入和删除元素时是 O(n)

  • 假设我们在任意位置 k 插入一个新的元素, 那么后面第 n - k 个元素都要往后移动, 所以时间是 O(n)
  • 假设我们删除任意位置 k 一个新的元素, 那么后面第 n - k 个元素都要往前移动一位, 所以时间也是 O(n)

删除和插入的最好情况是 O(1)

插入和删除的一种优化方法

这种优化的前提是我们并不需要数据的有序续性, 可以使用插入和删除达到 O(1).

在某个位置 k 插入数据的时, 只需要把这个位置的数称到最末尾, 然后插入新的数据

在某个位置 k 删除时, 只需要把这个位置做一个标记为已删除即可

稀疏数组

在我们使用多维数组保存一些数据的时候, 会遇到一些数组内的大量数据是一样的, 比如

1
2
3
4
5
6
7
8
9
[
	[0, 1, 2, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 1],
	[0, 0, 2, 0, 0, 0, 0],
	[0, 1, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 1, 0, 0],
	[0, 0, 0, 0, 0, 1, 0],
]

这样我们会保存了大量重复数据, 使用了更大的空间, 这时候可以改成另一种数据组织方式, 记录成第几行第几列有某个数据即可, 这样可以使用更少的空间

1
2
3
4
5
type Node struct {
 	row int	// 第几行
    col int // 第几列
    val interface{} // 保存的数据
}

链表

单链表

单链表
单链表

  1. 单链表的插入删除特别需要注意的点是顺序, 因为是单向的, 假如在 p 后面插入一个数据 q, 则需要
1
2
p.next = q.next
q.next = p

如果颠倒顺序, 则原先结点 p 后顺的结点都丢失了

  1. 我们可以使用一个头结点指头部, 这样插入新结点在头部操作

双向链表

双向链表
双向链表

  • 双向循环链表

双向循环链表
双向循环链表

  1. 虽然这个叫链表, 但我们经常使用一个数组来实现, 而不是真使用指针
  2. 双向循环链表有一个头指针, 一个尾指针, 这样我们可以使用 tail.next == head 来判断链表是否已满
  3. 使用数组的话可以, head 和 tail 就可以是一个简单的下标, 使用 (head + 1) mod maxSize 便可以容易的拿到下一个插入位置. 如果下一个位置 == tail, 那数组已满
  4. 很多时候, 我们会申请一个空位, 也就是 maxSize + 1 大小的数组

栈是一个先进后出的数据结构, 我们可以使用

  1. 数组实现, 在数组末尾添加(push)和删除(pop)元素即可, 时间复杂度都为 O(1)
  2. 单向链表实现, 在头结点处实现 push 和 pop 操作

队列

普通队列是一个先进先出的数据结构, 我们可以使用一个单向链表, 在链表末尾添加一个 tail 指针, 在头结点删除结点, 在尾结点添加新的结点

 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
// 链表队列
type Queue struct {
	head *QueueNode // 队列头
	tail *QueueNode // 队列尾
}

// 链表结点
type QueueNode struct {
	data *Node
	next *QueueNode
}

// 添加到队首
func (q *Queue) offer(node *QueueNode) {
	if q.tail == nil {
		q.head = node
		q.tail = node
	} else {
		q.tail.next = node
		q.tail = node
	}
}

// 从队列中取出
func (q *Queue) poll() *QueueNode {
	if q.head == nil {
		return nil
	}

	node := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return node
}

双端队列

双端队列指的是可以在两端都进行插入和删除的队列, 使用一个双向链表, 同样添加一个尾指针即可

代码地址: https://github.com/ivicel/zju-data-structure