网站建设 数据库网站建设 东营远见网络公司

我们知道，列表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需要特别的处理