一、无序表
可以采用链接节点的方式构建数据集来实现无序表，链表的第一个和最后一个节点最重要，如果想访问链表中的所有节点，就必须从第一个节点开始沿着链接遍历下去。
所以无序表必须要对第一个节点的引用信息设立一个属性head，保存对第一个节点的引用空表的head为None。
随着数据项的加入，无序表的head始终指向链条中的第一个节点。无序表mylist对象本身不包含数据项（数据项在节点中），其中包含的head只是对首个节点Node的引用，判断空表的isEmpty（）很容易实现。
接下来，考虑如何实现向无序表中添加数据项实现add方法。由于无序表并没用限定数据项之间的顺序，新数据项可以加入到原表的任何位置。按照实现的性能考虑，应添加到最容易添加的位置。链表结构我们都知道，要想访问链表所有数据项，必须从表头head开始沿着next链逐个向后查找，所以添加新的数据项最快捷的位置是表头，整个链表的首位置。
add方法：
链表实现：size链表实现：search
链表实现：remove（item）方法
首先要找到item，这个过程跟search一样，但在删除节点时需要特别的技巧。current指向的是当前匹配数据项的节点，而删除需要把前一个节点的next指向current的下一个节点，所以我们在searchcurrent的同时，还要维护前一个节点的引用。
找到item之后，current指向item节点，previous指向前一个节点，开始执行删除。需要区分两种情况：
current是首个节点或是位于链条中间的节点。
remove方法：
二、有序表有序表是一种数据项依照可比性质（如整数大小、字母表先后）来决定在列表中的位置，越小的数据项越靠近列表的头，越靠前。
有序表的操作：
有序表的实现：
同样采用链表方法实现，Node定义相同，有序表也设置一个head来保存链表表头的引用。
对于isEmpty、size、remove这些方法与节点的次序无关，所以跟无序链表是一样的，search、add方法则需要修改。
search方法
在无序表的search中，如果需要查找的数据项不存在，则会搜遍整个链表，直到表尾；对于有序表来说，可以利用链表节点有序排列特性，来为search节省不存在数据项的查找时间，一旦当前节点的数据项大于所要查找的数据项，则说明链表后边已经不可能有要查找的数据项，可以直接返回False。
我们在下图查找数据项45。
search方法的实现
add方法
想必无序表，改变最大的方法是add，因为add方法必须保证加入的数据项添加在合适的位置，以维护整个链表的有序性。
由于涉及到的插入位置是当前节点之前，而链表无法得到“前驱”节点的引用，所以要跟remove方法类似，引入一个previous的引用，跟随当前结点current。一旦找到首个比31大的数据项，previous就派上用场了。
add方法的实现
链表实现的算法分析
对于链表复杂度的分析，主要是看相应的方法是否涉及到链表的遍历。
链表实现的list跟Python内置的列表数据类型在有些相同方法的实现上时间复杂度不同，主要是因为Python内置的列表数据类型是基于顺序存储来实现的，并进行了优化。
图文来源：王雨图文编辑：张学进责任编辑：郭佳责任审核：肖佳依预览时标签不可点收录于话题#个上一篇下一篇