?
一、无序表的原理和应用
?
前面几章我们介绍了栈、队列、双端队列等，都是通过Python的列表结构来实现的。但是并不是所有的编程语言都提供了List数据类型，有时候需要自己来实现。
列表是基于顺序存储来实现的，是按照相对位置来存放的，被称为“无序表unorderedlist”。
无序表的操作如下：List()：创建一个空列表
add(item)：添加一个数据项到列表中，假设item原先不存在于列表中
remove(item)：从列表中移除item，列表被修改，item原先应存在于列表中
search(item)：在列表中查找item，返回布尔类型值
isEmpty()：返回列表是否为空
size()：返回列表包含了多少数据项
-----------------------------------------------------------------------------------------------
append(item)：添加一个数据项到表末尾，假设item原先不存在于列表中
index(item)：返回数据项在表中的位置
insert(pos,item)：将数据项插入到位置pos，假设item原先不在列表中，同时原列表具有足够多个数据项，能让item占据位置pos
pop()：从列表末尾移除数据项，假设原列表至少有1个数据项
pop(pos)：移除位置为pos的数据项，假设原列表存在位置pos
采用链表实现无序表：为了实现无序表数据结构，可以采用链接表的方案。虽然列表数据结构要求数据项的前后相对位置，但这种前后位置的保持，并不要求数据项依次存放在连续的存储空间。
数据项存放位置并没有规则，但如果在数据项之间建立链接指向，就可以保持其前后相对位置。第一个和最后一个数据项需要显式标记出来，一个是队首，一个是队尾，后面再无数据了。
1、链表实现：节点Node链表实现的最基本元素是节点Node，每个节点至少要包含2个信息：数据项本身，以及指向下一个节点的引用信息，注意next为Node的意义是没有下一个节点了，这个很重要。
classNode:def__init__(self,initdata):self.data=initdataself.next=NonedefgetData(self):returnself.datadefgetNext(self):returnself.nextdefsetData(self,newdata):self.data=newdatadefsetNext(self,newnext):self.next=newnext2、链表实现：无序表UnorderedList
可以采用链接节点的方式构建数据集来实现无序表，链表的第一个和最后一个节点最重要，如果想访问到链表中的所有节点，就必须从第一个节点开始沿着链接遍历下去。
所以无序表必须要有对第一个节点的引用信息，设立一个属性head，保存对第一个节点的引用，空表的head为None。
classUnorderedList:def__init__(self):self.head=None
随着数据项的加入，无序表的head始终指向链条中的第一个节点。需要注意的是，无序表mylist对象本身并不包含数据项（数据项在节点中），其中包含的head只是对首个节点None的引用，判断空表的isEmpty()很容易实现。
returnself.head==None
3、代码实现无序表
（1）add方法
由于无序表并没有限定数据项之间的顺序，新数据项可以加到原表的任何位置，按照性能的考虑，应添加到最容易加入的位置上，也就是表头。
defadd(self,item):temp=Node(item)temp.setNext(self.head)self.head=temp
（2）size方法
从链条头head开始遍历到表尾同时用变量累加经过的节点个数
defsize(self):current=self.headcount=0whilecurrent!=None:count+=1current=current.getNext()returncount（3）search方法
从链表头head开始遍历到表尾，同时判断当前节点的数据项是否目标
defsearch(self,item):current=self.headfound=Falsewhilecurrent!=Noneandnotfound:ifcurrent.getData()==item:found=Trueelse:current=current.getNext()returnfound
（4）remove方法
首先要找到item，这个过程跟search一样，但在删除时需要特别的技巧。current指向的是当前匹配数据项的节点，而删除需要把前一个节点的next指向current的下一个节点，所以在searchcurrent的同时，还需要维护前一个（previous）节点的引用。
找到item之后，current指向item节点，previous指向前一个节点，开始执行删除操作，需要区分两种情况：current是首个节点；或者是位于链条中间的节点。
defremove(self,item):current=self.headprevious=Nonefound=Falsewhilenotfound:ifcurrent.getData()==item:found=Trueelse:previous=currentcurrent=current.getNext()ifprevious==None:#判断是否为首个节点self.head=current.getNext()else:previous.setNext(current.getNext())二、有序表的原理和应用
有序表当中很多内容都是跟无序表保持一致的。有序表是一种数据项依照其某可比性质（如整数大小、字母表先后顺序）来决定在列表中的位置。越“小”的数据项越靠近列表的头，越靠“前”。
有序表的操作如下：OrderedList()：创建一个空的有序表
add(item)：添加一个数据项，并保持整体顺序，假设item原先不存在
remove(item)：从有序表中移除item，有序表被修改，item原先应存在
search(item)：在有序表中查找item，返回布尔类型值
isEmpty()：返回是否为空
size()：返回包含了多少数据项
index(item)：返回数据项在表中的位置
pop()：从有序表末尾移除数据项并返回该数据项，假设原有序表至少有1个数据项
pop(pos)：移除位置为pos的数据项并返回该数据项，假设原有序表存在位置pos
有序表OrderedList实现：在实现有序表的时候，需要记住的是，数据项的相对位置，取决于他们之间的“大小”比较。由于Python的扩展性，下面对数据项的讨论并不仅适用于整数，可适用所有定义了__gt__方法（即“”操作符）的数据类型。
节点Node链表实现的最基本元素是节点Node，每个节点至少要包含2个信息：数据项本身，以及指向下一个节点的引用信息，注意next为Node的意义是没有下一个节点了，这个很重要。
有序表也必须要有对第一个节点的引用信息，设立一个属性head，保存对第一个节点的引用，空表的head为None。
classOrderedList:def__init__(self):self.head=None
对于isEmpty/size/remove这些方法，与节点的次序无关，所以实现还是跟UnorderList是一样的。search和add方法需要修改。
（1）search方法
在无序表的search中，如果需要查找的数据项不存在，则会搜遍整个链表，知道表尾。但是，对于有序表来说，可以利用链表节点有序排列的特性，来为search节省不存在数据项的查找时间。一旦当前节点的数据项已经大于所要找的数据项，则说明链表后面已经不可能再有要查找的数据项，可以直接返回False。
defsearch(self,item):current=self.headfound=Falsestop=Falsewhilecurrent!=Noneandnotfoundandnotstop:ifcurrent.getData()==item:found=Trueelse:ifcurrent.getData()item:stop=Trueelse:current=current.getNext()returnfound
（2）add方法
相比于无序表，改变最大的就是add方法，因为add方法必须保证加入的数据项添加在合适的位置，以维护整个链表的有序性。
defadd(self,item):current=self.headprevious=Nonestop=Falsewhilecurrent!=Noneandnotstop:#发现插入位置ifcurrent.getData()item:stop=Trueelse:previous=currentcurrent=current.getNext()temp=Node(item)ifprevious==None:#插入在表头temp.setNext(self.head)self.head=tempelse:#插入在表中temp.setNext(current)previous.setNext(temp)链表实现的算法分析
对于链表复杂度的分析，主要是看相应的方法是否涉及到链表的遍历，对于一个包含节点数为n的链表：
isEmpty是O(1)，因为仅需要检查head是否为None
size是O(n)，因为除了遍历到表尾，没有其他办法得知节点的数量
search、remove以及有序表的add方法，则是O(n)，因为涉及到链表的遍历，按照概率其平均操作次数是n/2
无序表的add方法是O(1)，因为仅需要插入到表头
链表实现的list，跟Python内置的列表数据类型，在有些相同方法的实现上的时间复杂度不同，主要是因为Python内置的列表数据类型是基于顺序存储来实现的，并且进行了优化，我们使用的都是链表的链式存储，两者还是有差异的。
江苏吴彦祖