抽象数据类型
抽象数据类型(abstract data type, ADT)是一些操作的集合。对诸如表、集合、图和它们的操作一起可以看作是抽象数据类型。
表
数组
使用数组实现表结构时，在元素的增删比较麻烦，例如在0位增加一个元素，需要将所有元素后移一位，删除一个元素，需要讲所有元素前移一位，时间复杂度位O(N)。
链表
链表实现表结构时，增删操作的时间复杂度位O(1)。假设链表有5个节点，当需要在2和3之间增加一个节点时，只要创建一个新的节点空间，让2的next指针指向这个新创建的节点，再让新创建节点的指针指向3这个节点，则新增操作完成。删除某个节点时，讲节点的前一个节点的next指针指向当前节点的下个节点，并删除当前节点即可。
双向链表
双向链表与链表的差别在于，双向链表出了有next指针指向下一个元素，还有prev指针指向前一个元素，形成了双向链。
循环链表
循环链表的特别在于，最后一个元素的next指向第一个元素，而第一个元素的prev指向了最后一个元素。在双向链表中，这两个指针指向的都是null。