线性表
线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序，可写成\([a,b,c,…]\)的形式，方括号中的内容既表示线性表中的全部元素，也表示这些元素的排序。对于线性表中任意前后相邻的\(x_i\)与\(x_{i+1}\)元素，通常称\(x_i\)的后继为\(x_{i+1}\)，\(x_{i+1}\)的前驱为\(x_i\)，首个元素的前驱为空，最后一个元素的后继为空。需注意到线性表本身是个逻辑概念，其不限制也不依赖于具体实现，就类似于集合这样的概念，在讨论算法时经常会遇到这种类型的概念。
在算法领域人们更关心线性表的实现，因为线性表本身十分简答。
实际的计算机硬件基本都采用相同的“内存模型”，其包括由确定的\(K\)个连续整数构成的\(K\)个内存地址，每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存，一段时间后内存返回该地址中的数据，写入内存的流程大致是同时提供地址和数据给内存，一段时间后内存完成写入。在这种“内存模型”下，线性表的实现方案通常是数组或链表，这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”，也有一定的可能会用其他方案来实现线性表。
数组(Array)
数组需将所有元素依次存储于同一段连续内存地址，元素次序可规定为内存地址的升序。数组必须提供按索引(index)操作元素的能力，索引即元素序号，通常从0计起，比如“索引为2的元素”指“第3个元素”。下面给出一种数组的实现：
1) \(init(n,m)\)：以\(n\)为元素数上限、\(m\)为元素占据的内存地址数创建1个数组。步骤是将连续的\(nm\)个地址作为数组；
2) \(get(i)\)：得到索引为\(i\)的元素。步骤是返回\(mi…mi+(m-1)\)这\(m\)个地址的数据；
3) \(set(i,x)\)：将索引为\(i\)的元素替换为\(x\)元素。步骤是将\(mi…mi+(m-1)\)这\(m\)个地址的数据替换为\(x\)；
4) \(remove(i)\)：删除索引为\(i\)的元素。步骤是把\(m(i+1)…mn\)地址的数据依次拷贝到\(mi…m(n-1)\)地址；
5) \(insert(i,x)\)：在索引为\(i\)的元素前插入元素\(x\)。步骤是把\(mi…m(n-1)\)地址的数据依次拷贝到\(m(i+1)…mn\)地址，然后再将元素\(x\)写入\(mi…m(n-1)\)地址；
注意上述步骤中
数组有很好的按索引访问性能。但对于插入和删除，由于元素数变化，为保证索引从0开始连续递增，不得不逐个调整部分元素。大多时候需要调整的元素数在\(O(n)\)规模，这是数组的最大劣势。通常在程序语言中无法自己实现数组，因为不允许直接操作内存地址，数组的“能力”由程序语言本身提供，比如C和Java直接提供数组，Java还提供ArrayList这种“以数组为底层实现”的数据类型，Python则根本没提供数组，但其提供的list数据类型是“以数组为底层实现”的，list支持数组运算(名称和形式不同)，且代价几乎和数组相同。这里有个问题，比如对于当前有10个元素且长度为100的数组，以20为索引来查找会发生什么，这种情况与数组的具体实现细节有关，比如C语言会在创建数组时用默认值填满所有位置。
上图第2张是Python的list数据类型支持的运算以及各运算的代价，如果要在Python中实现“使用数组的算法”，可直接用list代替数组，因为几乎不影响代价，而且list还支持更丰富的运算。虽然list和数组的真实代价存在较大差异，但如果只是为了学习算法，真实代价是不需要关心的。下面是数组运算在Python的list中的表现形式，注意到创建list时并未指定长度，list的各元素也可以是不同长度的。这是因为list在数组基础上进一步实现了直接寻址表和动态表，这两种结构之后会继续讨论。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # 初始化list的各种方式 arr = list() arr = [] arr = [10,20,30,40] # 索引 i = 2 # 按索引查找并返回这个元素 arr[i] # 按索引替换 arr[i] = 200 arr[i] = "hello, world" # 按索引删除元素并返回这个元素 arr.pop(i) # 在指定索引的元素前插入元素 arr.insert(i,199) |
链表(Linked List)
链表是“在元素上加入额外数据，直接记录其后继位置”的。链表比数组有更灵活的内存分配方式，各元素本身通常仍需要占用连续地址，但元素间的地址不一定连续。对于元素占用的空间，前一部分存元素本身(称为\(data\)域)，后一部分存其后继元素地址(称为\(next\)域)，这2部分加起来就不是元素本身了，而是称为链表节点的复合结构。链表除了包含所有链表节点，还要在内存额外记录当前链表的首节点(表头)地址。因为只有从首节点出发，才能按正确的前驱后继次序依次的找到所有链表节点，否则会遗漏部分节点，当然这里不考虑“额外记录所有节点地址”这种浪费内存的做法。
链表也能实现类似数组的按索引访问，只需从表头出发，通过各节点的\(next\)域即可到达，最坏代价是\(O(n)\)，弱于数组(当然这里不考虑把所有链表节点放在数组里这种操作，所以一开始只有表头地址而没有其他节点的地址)。但如果知道某链表节点地址，并想删其后继或在其后插入元素时，链表则比数组方便的多。比如删除节点后继时，只需把该节点\(next\)域内容改为其后继的\(next\)域内容，由于只需常数次的访问和修改，故代价是\(O(1)\)，无需像数组那样调整其他元素的索引。
很多程序语言提供“基于链表”的数据类型，比如Java的LinkedList和Python的deque。不过在程序语言中，一般很容易自己去实现链表，尤其对于面向对象(OOP)的程序语言，通常会用“链表”和“链表节点”两个类(Class)实现链表，这种面向对象方式实现的链表，其内存结构和上面描述的会有点区别，但这并不重要，因为访问修改对象属性、初始化对象等一般都是\(O(1)\)的，所以各操作的代价和上面讨论的一致。下面是Python面向对象语法的链表实现，为方便把运算和表头地址(\(head\))都放入LinkedList类。为了对比数组，这里也实现了“数组运算”，实际应用中链表要实现什么运算是根据需求确定的。
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | class Node: def __init__(self, key): self.key = key self.next = None class LinkedList: def __init__(self): self.head = None self.size = 0 def _find(self, i): if i >= self.size: return node, j = self.head, 0 while node: if j == i: return node else: node = node.next j += 1 def get(self, i): if i >= self.size: raise Exception("链表为空或序号越界") return self._find(i).key def set(self, i, x): if i >= self.size: return False self._find(i).key = x return True def remove(self, i): if i >= self.size: return False if i == 0: self.head = self.head.next else: pNode = self._find(i - 1) pNode.next = pNode.next.next self.size -= 1 return True def insert(self, i, x): newNode = Node(x) if not self.head: self.head = newNode elif i >= self.size: pNode = self._find(self.size - 1) pNode.next = newNode elif i == 0: newNode.next = self.head self.head = newNode else: pNode = self._find(i - 1) newNode.next = pNode.next pNode.next = newNode self.size += 1 |
双向链表(Double Linked List)
上图所示的结构称为双向链表，普通链表也称为单向链表。双向链表节点多1个指向前驱节点地址的\(prev\)域，且除了需要额外记录首个链表节点(\(head\))，还要额外记录最末链表节点(\(tail\))。当需要从表尾出发操作前面的节点时，这种结构比单向链表方便的多，因为单向链表总要先从\(head\)出发先确定表尾在哪，即使在单向链表维护\(tail\)记录也没用。下面是Python实现的双向链表，其运算和运算实现基本和上面的单向链表一样，只是多了一些维护\(prev,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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | class Node: def __init__(self, key): self.key = key self.next = None self.prev = None class DoubleLinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def _find(self, i): if i >= self.size: return node, j = self.head, 0 while node: if j == i: return node else: node = node.next j += 1 def get(self, i): if i >= self.size: raise Exception("链表为空或序号越界") return self._find(i).key def set(self, i, x): if i >= self.size: return False self._find(i).key = x return True def remove(self, i): if i >= self.size: return False if i == 0: self.head = self.head.next if self.head: self.head.prev = None else: self.tail = self.head else: pNode = self._find(i - 1) pNode.next = pNode.next.next if pNode.next: pNode.next.prev = pNode self.size -= 1 return True def insert(self, i, x): newNode = Node(x) if not self.head: self.head = self.tail = newNode elif i == 0: newNode.next = self.head newNode.next.prev = newNode self.head = newNode elif i >= self.size: pNode = self._find(self.size - 1) pNode.next = newNode pNode.next.prev = pNode self.tail = newNode else: pNode = self._find(i - 1) newNode.next = pNode.next newNode.next.prev = newNode newNode.prev = pNode pNode.next = newNode self.size += 1 |