从python来看数据结构基础

数组

概念

数组是有限个相同类型的变量所组成的有序集合。在内存中顺序存储，可以实现逻辑上的顺序表。

python中主要使用列表(list)和元组(tuple)两种集合，本质上都是对数组的封装。

基本操作

#初始化列表
my_list = [3,1,2,5,4,9,7,2]
#读取元素
print(my_list[2])
2
#更新元素
my_list[3] = 10
print(my_list[3])
10
#插入元素
#尾部插入
#尾部插入元素
my_list.append(6)
#中间插入元素
my_list.insert(5,11)
print(my_list)
[3, 1, 2, 10, 4, 11, 9, 7, 2, 6]

以数组的方式理解插入操作：

class MyArray:def __init__(self,capacity):self.array = [None] * capacityself.size = 0def insert(self,index,element):#判断访问下标是否超出范围if index < 0 or index > self.size:raise Exception("超出数组实际元素范围！")#从右向左循环，逐个元素向右挪一位for i in range(self.size - 1,-1,-1):self.array[i + 1] = self.array[i]#腾出的位置放入新元素self.array[index] = elementself.size += 1def output(self):for i in range(self.size):print(self.array[i])

输出结果如下：

array = MyArray(4)
array.insert(0,10)
array.insert(0,11)
array.insert(0,15)
array.output()
15
11
10

但是这种方式一旦元素数量超过了数组的最大长度，数组就会被认为是非法输入，因此我们需要使用超范围插入。

class MyArray:def __init__(self,capacity):self.array = [None] * capacityself.size = 0def insert_v2(self,index,element):#判断访问下标是否超出范围if index < 0 or index > self.size:raise Exception("超出数组实际元素范围！")#如果实际元素达到数组容量上限，数组扩容if self.size >= len(self.array):self.resize()#从右向左循环，逐个元素向右挪一位for i in range(self.size - 1,-1,-1):self.array[i + 1] = self.array[i]#腾出的位置放入新元素self.array[index] = elementself.size += 1def resize(self):array_new = [None] * len(self.array) * 2#从旧数组复制到新数组for i in range(self.size):array_new[i] = self.array[i]self.array = array_newdef output(self):for i in range(self.size):print(self.array[i])

array = MyArray(4)
array.insert_v2(0,10)
array.insert_v2(0,11)
array.insert_v2(0,12)
array.insert_v2(0,14)
array.insert_v2(0,15)
array.insert_v2(0,16)
array.output()
16
15
14
12
11
10

删除操作也是如下方法实现：

def remove(self,index):#判断访问下表是否超出范围if index < 0 or index >= self.size:raise Exception("超出数组实际元素范围!")#从左到右，所有元素依次挪动一位for i in range(index,self.size):self.array[i] = self.array[i + 1]self.size -= 1

这种操作的方式时间复杂度为$O(n)$，但是如果我们将最后一个元素给复制到需要删除元素的位置，再删除最后一个元素，则无需进行大量元素移动，时间复杂度将变为$O(1)$。

数组适用于读操作多、写操作少的场景。

链表

概念

链表是一种在物理上非连续、非顺序的数据结构，由若干节点所组成。

• 单向链表：存放数据的变量data和指向下一个节点的指针next组成
• 双向链表：还拥有指向前置节点的prev指针

链表在内存中存储的方式是随机存储。

基本操作

class Node:def __init__(self,data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.size = 0self.head = Noneself.last = Nonedef get(self,index):if index < 0 or index > self.size:raise Exception("超出链表节点范围！")p = self.headfor i in range(index):p = p.nextreturn pdef insert(self,data,index):if index < 0 or index > self.size:raise Exception("超出链表节点范围!")node = Node(data)if self.size == 0:#空链表self.head = nodeself.last = nodeelif index == 0:#插入头部node.next = self.headself.head = nodeelif self.size == index:#插入尾部self.last.next == nodeself.last = nodeelse:#插入中间prev_node = self.get(index - 1)node.next = prev_node.nextprev_node.next = nodeself.size += 1def remove(self,index):if index < 0 or index >= self.size:raise Exception("超出链表节点范围！")#暂存被删除的节点，用于返回if index == 0:#删除头节点removed_node = self.headself.head = self.head.nextelif index == self.size - 1:#删除尾节点prev_node = self.get(index - 1)removed_node = prev_node.nextprev_node.next = Noneself.last = prev_nodeelse:#删除中间节点prev_node = self.get(index - 1)next_node = prev_node.next.nextremoved_node = prev_node.nextprev_node.next = next_nodeself.size -= 1return removed_nodedef output(self):p = self.headwhile p is not None:print(p.data)p = p.next

linkedList = LinkedList()
linkedList.insert(3,0)
linkedList.insert(4,0)
linkedList.insert(5,0)
linkedList.insert(9,2)
linkedList.insert(5,3)
linkedList.insert(6,1)
linkedList.output()
5
6
4
9
5
3
linkedList.remove(0)
linkedList.output()
6
4
9
5
3

• 数组和链表的性能对比

	查找	更新	插入	删除
数组	$O(1)$	$O(1)$	$O(n)$	$O(n)$
链表	$O(n)$	$O(1)$	$O(1)$	$O(1)$

如果需要频繁插入和删除元素，链表更适合。

栈和队列

数组和链表是存储结构，而逻辑结构依赖于物理结构而存在。

逻辑结构分为线性结构和非线性结构

线性结构：例如顺序表、栈、队列等

非线性结构：例如树、图等。

栈

栈是一种线性数据结构，栈中的元素只能先入后出（FILO）。最早进入的是栈底，最后进入的是栈顶。

栈的基本操作有入栈（push）和出栈（pop）

python中列表已经很好地实现了栈的功能，append相当于入栈，pop相当于出栈。

队列

队列是一种线性数据结构，队列的元素只能先入先出（FIFO）。队列的出口端为队头，入口端为队尾。

用数组实现时，为了入队操作的方便，将队尾位置规定为入队元素的下一个位置。

队列的基本操作有入队（enqueue）和出队（dequeue）。

用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。直到（队尾下标+1）%数组长度=对头下标时，则代表队列满了。由于队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

python中提供了多种队列工具，比如collections.deque，queue.Queue等。

我们尝试自己实现一个队列：

class MyQueue:def __init__(self,capacity):self.list = [None] * capacityself.front = 0self.rear = 0def enqueue(self,element):if (self.rear + 1) % len(self.list) == self.front:raise Exception("队列已满！")self.list[self.rear] = elementself.rear = (self.rear + 1) % len(self.list)def dequeue(self):if self.rear == self.front:raise Exception("队列已满！")dequeue_element = self.list[self.front]self.front = (self.front + 1) % len(self.list)return dequeue_elementdef output(self):i = self.frontwhile i != self.rear:print(self.list[i])i = (i + 1) % len(self.list)

myqueue = MyQueue(6)
myqueue.enqueue(3)
myqueue.enqueue(5)
myqueue.enqueue(6)
myqueue.dequeue()
myqueue.dequeue()
myqueue.output()
6

栈和队列的应用

栈可以用于实现递归的逻辑，还有面包屑导航（用户在浏览过程中回溯上一级的页面）。

队列可以运用于多线程中争夺公平锁的等待队列，网络爬虫也可以将URL存入队列中。

双端队列综合了栈和队列的优点，从队头可以入队和出队，队尾一端也可以入队和出队。

优先队列遵循谁的优先级高谁先出队，但是是基于二叉堆实现的。

哈希表

哈希表也称为散列表，这个数据结构提供了键（key）和值（value）的映射关系。

在python中，哈希表对应的集合是字典。通过哈希函数，可以将key和数组下标进行转换。

哈希表的读写操作

写操作就是在哈希标中插入新的键值对（Entry）。

当写的过程中发生了哈希冲突，我们可以通过开放寻址法或链表法解决。

• 开放寻址法：寻找被占用的数组下标的下一个位置。
• 链表法：哈希表数组的每一个元素还是一个链表的头节点，只需要插入对应的链表中即可。

读操作就是通过给定的key在哈希表中查找对应的value。

有些语言采用了链表法：Java中的HashMap；而python中的dict采用的是开放寻址法。