数据结构--数组链表
数据结构--数组链表
- 1. 数组（顺序存储）
- 2. 链表（链式存储）
- 3. 环形数组技巧
1. 数组（顺序存储）
「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这是数组的原始形态。
「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。
# 创建动态数组
# 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
arr = []
for i in range(10):
# 在末尾追加元素，时间复杂度 O(1)
arr.append(i)
# 在中间插入元素，时间复杂度 O(N)
# 在索引 2 的位置插入元素 666
arr.insert(2, 666)
# 在头部插入元素，时间复杂度 O(N)
arr.insert(0, -1)
# 删除末尾元素，时间复杂度 O(1)
arr.pop()
# 删除中间元素，时间复杂度 O(N)
# 删除索引 2 的元素
arr.pop(2)
# 根据索引查询元素，时间复杂度 O(1)
a = arr[0]
# 根据索引修改元素，时间复杂度 O(1)
arr[0] = 100
# 根据元素值查找索引，时间复杂度 O(N)
index = arr.index(666)
2. 链表（链式存储）
数组最大的优势是支持通过索引快速访问元素，而链表就不支持。
因为元素并不是紧挨着的，所以如果你想要访问第 3 个链表元素，你就只能从头结点开始往顺着 next 指针往后找，直到找到第 3 个节点才行
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Node:
def __init__(self, prev, element, next):
self.val = element
self.next = next
self.prev = prev
双链表记得toDelete 的前后指针都置为 null 是个好习惯
# 创建一条双链表
head = createDoublyLinkedList([1, 2, 3, 4, 5])
# 删除头结点
toDelete = head
head = head.next
head.prev = None
# 清理已删除节点的指针
toDelete.next = None
# 现在链表变成了 2 -> 3 -> 4 -> 5
3. 环形数组技巧
数组可能是环形的么？不可能。数组就是一块线性连续的内存空间，怎么可能有环的概念？
但是，我们可以在「逻辑上」把数组变成环形的，比如下面这段代码
# 长度为 5 的数组
arr = [1, 2, 3, 4, 5]
i = 0
# 模拟环形数组，这个循环永远不会结束
while i < len(arr):
print(arr[i])
i = (i + 1) % len(arr)
环形数组的区间被定义为左闭右开的，即 [start, end) 区间包含数组元素
理论上，你可以随意设计区间的开闭，但一般设计为左闭右开区间是最方便处理的。
因为这样初始化 start = end = 0 时，区间 [0, 0) 中没有元素，但只要让 end 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。
如果你设置为两端都开的区间，那么让 end 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就已经包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦，如果你非要使用的话，需要在代码中做一些特殊处理。
class CycleArray:
def __init__(self, size=1):
self.size = size
# 因为 Python 支持直接创建泛型数组，所以不需要类型转换
self.arr = [None] * size
# start 指向第一个有效元素的索引，闭区间
self.start = 0
# 切记 end 是一个开区间，
# 即 end 指向最后一个有效元素的下一个位置索引
self.end = 0
self.count = 0
# 自动扩缩容辅助函数
def resize(self, newSize):
# 创建新的数组
new_arr = [None] * newSize
# 将旧数组的元素复制到新数组中
for i in range(self.count):
new_arr[i] = self.arr[(self.start + i) % self.size]
self.arr = new_arr
# 重置 start 和 end 指针
self.start = 0
self.end = self.count
self.size = newSize
# 在数组头部添加元素，时间复杂度 O(1)
def add_first(self, val):
# 当数组满时，扩容为原来的两倍
if self.is_full():
self.resize(self.size * 2)
# 因为 start 是闭区间，所以先左移，再赋值
self.start = (self.start - 1 + self.size) % self.size
self.arr[self.start] = val
self.count += 1
# 删除数组头部元素，时间复杂度 O(1)
def remove_first(self):
if self.is_empty():
raise Exception("Array is empty")
# 因为 start 是闭区间，所以先赋值，再右移
self.arr[self.start] = None
self.start = (self.start + 1) % self.size
self.count -= 1
# 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半
if self.count > 0 and self.count == self.size // 4:
self.resize(self.size // 2)
# 在数组尾部添加元素，时间复杂度 O(1)
def add_last(self, val):
if self.is_full():
self.resize(self.size * 2)
# 因为 end 是开区间，所以是先赋值，再右移
self.arr[self.end] = val
self.end = (self.end + 1) % self.size
self.count += 1
# 删除数组尾部元素，时间复杂度 O(1)
def remove_last(self):
if self.is_empty():
raise Exception("Array is empty")
# 因为 end 是开区间，所以先左移，再赋值
self.end = (self.end - 1 + self.size) % self.size
self.arr[self.end] = None
self.count -= 1
# 缩容
if self.count > 0 and self.count == self.size // 4:
self.resize(self.size // 2)
# 获取数组头部元素，时间复杂度 O(1)
def get_first(self):
if self.is_empty():
raise Exception("Array is empty")
return self.arr[self.start]
# 获取数组尾部元素，时间复杂度 O(1)
def get_last(self):
if self.is_empty():
raise Exception("Array is empty")
# end 是开区间，指向的是下一个元素的位置，所以要减 1
return self.arr[(self.end - 1 + self.size) % self.size]
def is_full(self):
return self.count == self.size
def size(self):
return self.count
def is_empty(self):
return self.count == 0
环形数组可以帮助在删除头部数组时不搬移其他元素，时间复杂度变为O(1)
-
环形数组也可以删除指定索引的元素，也要做数据搬移，和普通数组一样，复杂度是 O(N)；
-
环形数组也可以获取指定索引的元素（随机访问），只不过不是直接访问对应索引，而是要通过 start 计算出真实索引，但计算和访问的时间复杂度依然是 O(1)；
-
环形数组也可以在指定索引插入元素，当然也要做数据搬移，和普通数组一样，复杂度是 O(N)。