一、无序链表
书中的链表，是由两个类组成的，一个是节点类，一个是链表类。
-
节点类：节点类又包含初始化， 获得data和next，更改data和next的方法。（一般在编程题中， 只会给初始化，包含data和next属性）
其中，getNext()就是获得下一个节点，比如
current = current.getNext()
的意思，就是current此时被赋值为当前节点的下一个节点
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
- 列表类：列表类初始化头结点为none，对应的也有几种常用的方法。isEmpty，add，search，size等。
1.1、链表方法---添加节点add
添加节点方法。其中temp是node类的实例。因为无序链表最容易增加新节点的地方是在头部，或者说在了列表的开始。于是我们把新节点作为列表的第一个节点，就可以构建一个链表了。
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
在add方法中，temp是从节点类Node中得到的一个实例，这个实例有两个属性，一个是data，一个是next。
第二行，类初始化时把temp的data设置为item，next为None。
第三行，实例方法把节点temp的next指向了旧链表的head。
第四行，把链表mylist的头结点设置为当前节点temp。
在下图中可以看到这个步骤，
- 本来原链表head是节点93（虚线）
- 新建立一个节点
节点data为26，next指向None（虚线） - 设置新节点temp的next指向head，也就是节点93。
- 把新节点temp赋值给head。
- 完成一次添加节点的操作。
################################################################
链表方法--求元素个数（size），查找（search），移除（remove）
这些方法，都是基于一个叫做链表的遍历的操作，
访问完一个节点，将外部引用移动到下一个节点的操作可以简单理解为：
current = current.getNext()
即，将current 赋值为下一个 节点。直到current为None为止。
################################################################
1.2、size方法
- 建立外部引用，让current为链表头结点，并设置count为0
- 只要current不为None，就把count加1，然后让当前节点current指向下一节点（循环此步，知道current为None，即不再有节点为止）
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
1.3、search方法
- 建立一个外部引用current，并设置一个变量found初始化为False
- 只要current不为None并且没有找到target（即found==False），就先进行data比对，然后用current = current.getNext()来获得下一个节点。直到循环结束。
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
1.4、remove方法
移除一个节点分两步：
- 1、查找数据，找到要remove的节点
- 2、是移除节点，并将链表再次链接起来
上述步骤涉及到对节点的操作，需要引入两个外部引用。current和previous。
current代表要被移除的节点，移除以后，将previous节点的next指向下一个节点即可。
previous初始化为None，所以涉及到previous的操作时，要考虑两种情况：1、previous仍然是None ----2、previous是一般的节点
在此处代码中，也就是，当第一步完成found=True时，要对previous进行判断，根据情况更改指针。
此处我们假设，一定能找到要删除的节点，因此只用bool来控制循环就行了。
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
#当找到需要移除的节点时，才进行移除操作
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
else:
previous = current
current = current.getNext()
二、有序链表
相对于无序链表，有序链表仍然有add，remove，search等类方法。
在实现上，size，remove的方法操作是一样的，但是因为有序，add，search的方法就要有些许改变了。
同样，此时我们有两个类，一个节点类Node，跟上面的一样，一个有序链表类
class OrderedList:
def __init__(self):
self.head = None
2.1 、search方法
因为有序，所以我们不需要一下搜索到底了，因此，当我们搜索到一个节点发现data比target要大时，还没有搜索到target，那我们就可以结束搜索了。所以，相对于无序链表的search方法， 我们额外加了一个stop变量，来控制循环。
- 找到了target，就把found变为True。
- 发现了一个data比target大，没找到target，把stop变为True
- 没找到target，data比target小，就接着向右搜索
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
2.2 、add方法
不同于无序链表，只需要在头部添加新节点就行了。要考虑添加节点以后链表仍是有序的。
分为两步
第一步，找到需要添加节点的位置。
为此也增加一个控制循环的变量stop。找到新节点位置的两种情况：
1、当找到data大于target的节点时，stop变为True，此时执行添加节点的操作。
2、当循环遍历完整个链表是，停止循环，添加节点。第二步，根据位置，添加节点。
又因为在链表内部进行增加节点的操作，所以也需要两个外部引用变量previous和current。
另外，previous同样需要有两种情况需要考虑。
def add(self,item):
#设置外部引用， 用于节点操作
current = self.head
previous = None
#设置stop变量用于控制循环
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
#循环结束，第一步完成，找到了需要添加节点的位置
#第二步，添加节点，位置不同，操作也不同，分为头结点，中间节点
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
