一、数组

物理大小和逻辑大小

物理大小：创建时的大小
逻辑大小：可使用的大小

  • 如果逻辑大小>=物理大小，代表数组被填满了。

增加（插入，替换）、删除静态数组策略

  • 增加： 当逻辑大小已经等于物理大小时，再添加元素数组需要扩容。每增加一个元素就扩容，添加N项的话会带来O(n^2)算法消耗，可以在达到这个条件时，直接为数组扩容两倍。
  • 插入：从数组尾部往后移一位，执行到插入点位置为止，制造一个空洞为新元素
  • 删除： 当逻辑大小已经小于或等于物理大小四分之一时，将数组容量砍半。
    删除元素，将此元素索引后一位往前移一位。与插入相反。

复杂度分析

第i个位置插入，删除： O(n) 平均情况
增加减少容量： O(n) 平均情况
第i个位置访问，替换：O(1)

二、链表

单链表， 双链表。

  • 末尾删除： 找出倒数第二个结点，将其next指针指为none即可。
  • 表头删除：找出第一个结点，将next指给head

复杂度分析：

  • 访问第i个元素：O(n) 平均情况
  • 在第i个元素替换：O(n) 平均情况
  • 在开始入插入：O(1) all
  • 在结束处删除：O(1) all
  • 在第i个位置插入，删除：O(n) 平均情况

链表的优势在于内存性能，虽然存储指向指针会占用大小，但相对数组还是有优势．另外优势在于对首尾元素的删除插入处理时的效率更快．

优化：哑头节点的循环列表

head = Node(None, None)
head.next = head

方便处理插入遍历，只需判断条件为probe.next != head即不是最后一个元素