数据结构与算法python版本之线性结构之无序表抽象数据类型有序链表抽象数据类型和总结

我们知道，列表List是一种简单强大的数据集结构，提供了丰富的操作接口；但是并不是所有的编程语言都提供了List数据类型，有时候需要程序员自己实现。

那么什么是列表呐？

列表是一种数据项按照相对位置存放的数据集；特别的，被称为“无序表unordered list” 其中数据项只按照存放位置来索引，如第1个，第2个。。。。。。最后一个等。
所以无序列表的操作有如下：


采用链表实现无序表，为了实现无序表数据结构，可以采用链接表的方案；虽然列表数据结构要求保持数据项的前后相对位置，但这种前后位置的保持，并不要求数据项一次存放在连续的存储空间；如果在数据项之间建立链接指向，就可以保持其前后相对位置。

链表实现：节点Node

链表实现的最基本元素是节点Node
每个节点至少要包含两个信息：数据项本身，以及指向下一个节点的引用信息；注意，next为None的意义是没有下一个节点了，这个很重要。

链表实现：无序表UnorderedList

可以采用链接节点的方式构建数据集来实现无序表；链表的第一个和最后一个节点最重要，如果想访问到链表中的所有节点，就必须从第一个节点开始沿着链接遍历下去
所以无序表必须要有对第一个节点的引用信息
随着数据项的加入，无序表的head始终指向链条中的第一个节点。

无序表的链表实现

接下来，我们考虑如何实现向无序表中添加数据项，实现add方法
由于无序表并没有限定数据项之间的顺序
新数据项可以加入到原表的任何位置
按照实现的性能考虑，应添加到最容易加入的位置上
由链表结构我们知道：要访问到整条链上的所有数据项，都必须从表头head开始沿着next链接逐个向后查找，所以添加新数据项最快捷的位置是表头，整个链表的首位置。
链表实现：可以使用add方法实现
链表实现：Size，size指的是从链条头head开始遍历到表尾同时用变量累加经过的节点个数
链表实现：search，从链表头head开始遍历到表尾，同时判断当前节点的数据项是否目标
链表实现：remove(item)方法，首先要找到这个item，这个过程跟search一样，但在删除节点时，需要特别的技巧；
current指向的时当前匹配数据项的节点，而删除需要把前一个节点的next指向current的下一个节点，所以我们在search current的同时，还要维护前一个(previous)节点的引用；
找到item之后，current指向item节点，previous指向前一个节点，开始执行删除，需要区分两种情况：current是首个节点，或者是位于链条中间的节点。

抽象数据类型：有序表OrderedList

有序表是一种数据项依照其某可比性质（如整数大小、字母表先后）来决定在列表中的位置，越小的数据项越靠近列表的头，越靠前。

在实现有序表的时候，需要记住的是，数据项的相对位置，取决于他们之间的大小比较。

在无序表的search方法中，如果需要查找的数据项不存在，则会搜遍整个链表，直到表尾；对于有序表来说，则可以利用链表节点有序排列的特性，来为search节省不存在数据项的查找时间。

相比无序表，改变最大的方法是add，因为add方法必须保证加入的数据项添加在合适的位置，以维护整个链表的有序性。比如在（17，26，54，77，93）的有序表中，加入数据项31，我们需要沿着链表，找到第一个比31大的数据项54，将31插入到54的前面。

总结

1. 线性数据结构Linear DS将数据项以某种线性的次序组织起来
2. 栈Stack维持了数据项后进先出LIFO的次序，stack的基本操作包括push pop isEmpty
3. 队列Quene维持了数据项先进先出FIFO的次序，quene的本机操作包括enqueue dequeue isEmpty
4. 书写表达式的方法有前缀prefix、中缀infix和后缀postfix三种，由于栈具有次序反转的特性，所以栈结构适合用于开发表达式求值和转换的算法
5. 模拟系统可以通过一个对现实世界问题进行抽象建模，并且加入随机数动态运行，为复杂问题的决策提供各种情况的参考，队列quene可以用来进行模拟系统的开发
6. 双端队列Deque可以同时具备栈和队列的功能，deque的主要操作包括addFront addRear removeFront removeRear isEmpty
7. 列表List是数据项能够维持相对位置的数据集
8. 链表的实现，可以保持列表维持相对位置的特点，而不需要连续的存储空间
9. 链表实现时，其各种方法，对链表头部head需要特别的处理