抽象数据类型(ADT):
是带有一组操作的一些对象的集合,是数学的抽象
表ADT:
将大小为0的表称为空表(empty list);
称Ai为Ai-1的后继元,Ai为Ai+1的前驱元;
Ai的位置为i+1;
第一个元为A0,最后一个元为An+1;
A0无前驱元,An+1无后继元;
表的数组实现:
printList/find-->>线性时间;
findIndex-->>常数时间;
插入/删除需要大量时间:最坏与平均都需要O(N)时间,最好的情况需要O(1);
因此如果以少量在高端(及其靠近数组末尾)插入,其后均为访问则数组的表实现是比较合理的;但是如果有大量在前端的插入删除操作,那么数组的表实现就不那么合理了
链表表实现:
思路:为了避免数组形式的插入删除的线性开销(操作过程中需要整体移动元),那么将元设计为可以不连续存储的形式,链表就是这样的实现.
链表由一系列的节点组成,这些节点在内存中并不一定是连续的,每一个节点均包含一个表元素以及到该元素的后继元节点的链,此链称为next链,最后一个节点的next链引用为null(单链表).
printList-->>线性时间;
find-->>线性时间(需要从链表的第一个节点开始遍历);
findIndex(i)-->>O(i)
remove操作需要修改一个next引用实现,添加需要一个新的节点然后进行两次next修改,但是删除最后一项比较复杂,因为需要修改最后节点的前驱节点的next链的引用为null,因此一般节点持有本节点元素以及后继元的next链,此外还有前驱元的引用链previous(双链表).