一、无序链表

书中的链表，是由两个类组成的，一个是节点类，一个是链表类。

• 节点类：节点类又包含初始化， 获得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)