链表（二）

链表的构造：

class Node():
    '''节点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''单链表'''
    def __init__(self,node=None):
        #内部私有函数，链表头的初始化，可以直接建立空链表
        self.__head = node

    def is_empty(self):
        """判断链表是否为空"""
        pass

    def length(self):
        """返回链表的长度"""
        pass

    def travel(self):
        """遍历链表"""
        pass

    def add(self, item):
        """头部添加节点"""
        pass

    def append(self, item):
        """尾部添加节点"""
        pass

    def insert(self, pos, item):
        """在指定位置添加节点"""
        pass

    def remove(self, item):
        """删除一个节点"""
        pass

    def search(self, item):
        """查找节点是否存在"""
        pass


single_obj = SingleLinkList()
single_obj.travel()

这部分主要是考虑P节点指向的问题，节点类已经有了；

关于这一点，也可以写成：

 def __init__(self,node):
        #内部私有函数，链表头的初始化，可以直接建立空链表
        self.__head = None
node = Node(100)
single_obj = SingleLinkList(node)

这样也可以就是不太高级。

如图，简写单链接表为sll，因为SingleListLink()传入的值为空，故默认node = None，即__head指向为空，也就是P指向为None。node = Node(100)，产生了节点类，节点包括两部分，一部分是elem，一部分是next。下一步就是让__head指向100这个节点。

• 我们先来看看如何实现第一个探空的功能，即判读链表是否为空：

  这么写应该不难理解，链表为空那么__head的指向就为空，利用一下罗即判读，如self.__head ==None则返回True,代表链表为空，else链表不为空。

• 实现第二个功能，判断链表的长度即length()：
  

  我们先模拟几个节点，并建立游标cur： 之所以不采用cur.next == None，是考虑到第三个节点也就是300节点处的cur.next == None,这样一来，记录节点数目的时候就会少一个，cur = cur.next就可以移动游标了。 同时我们还要考虑特殊情况，当这个链表为空链表的时候我们的程序能否实现要求，当链表为空，即self.__head==None，cur == None，count = 0，符合我们的预期要求。
• 实现第三个功能，遍历链表（travel）:

  基本上和判断链表长度一样，进入循环打印出来即可，同样不能采用cur.next == None，否则会丢掉最后一个节点。

• 实现第四个功能，尾部添加节点，也就是append()功能： 比如我们要在尾部添加400这个节点，就是要将300节点的next指向400节点。 我们先建立一个node节点，移动游标cur，移动到cur.next = None，然后将cur所在的节点的next指向我们先建立的node节点即可。这时我们还需要考虑特殊情况，即空链表的情况向下如何实现我们的操作： self.__head已经指向None了怎么还能有next呢，那么我们就要针对性的改一下。 我们这样更改是不是可以；但利用之前探空的功能岂不是更好。 这样一来代码读起来会更流畅。

class Node():
    '''节点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''单链表'''
    def __init__(self,node=None):
        #内部私有函数，链表头的初始化，可以直接建立空链表
        self.__head = node

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None

    def length(self):
        """返回链表的长度"""
        #cur游标，用来移动遍历节点
        #count，用来记录节点数量
        count = 0
        cur = self.__head
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self.__head
        while cur != None:
            print(cur.elem,end=' ')
            cur = cur.next

    def add(self, item):
        """头部添加节点"""
        pass

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """在指定位置添加节点"""
        pass

    def remove(self, item):
        """删除一个节点"""
        pass

    def search(self, item):
        """查找节点是否存在"""
        pass


if __name__ == '__main__':
    li = SingleLinkList()
    print(li.is_empty())
    print(li.length())

    li.append(1)
    li.append(2)
    print(li.is_empty())
    print(li.length())

    li.append(3)
    li.append(4)
    li.travel()

测试结果：

True
0
False
2
1 2 3 4

• 实现第五个功能，即像链表头部添加元素（add）： 假如400节点是我们即将插入的新元素，那么怎么更改指向才能实现呢？ 这样的指向是不是我们想要的结果呢？这样一来就很简单了。 考虑一下特殊情况，如果一上来这个链表就是一个空链表呢？那么node.next = self.__head指向的就是None，因为self.__head在空链表中指向None，self.__head 指向node是没有问题的，测试结果表明一切也OK。
• 实现第六个功能，任意位置插入（insert）：
  比如insert(2,400)如图所示： 要想实现这个操作要如何更改程序呢？
  为了方便大家理解，我们把移动到指定位置的前一个元素的游标叫做pre不再是叫做cur我们要在第二个位置插入400，是不是就要在第一个位置上开始改变指向呢？

    def insert(self, pos, item):
        """在指定位置添加节点"""
        pre = self.__head
        count = 0
        while count < (pos-1):
            count += 1
            pre = pre.next
        node = Node(item)
        node.next = pre.next
        pre.next = node

这么写是不是很OK，但是还需要考虑特殊情况，如果用户输入的pos =< 0怎么办，我们只能默认是0，故采用头插法。如果大于等于链表的总长度，那就是尾插法了。

    def insert(self, pos, item):
        """在指定位置添加节点"""
        pre = self.__head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos >= (self.length()-1):
            self.append(item)
        else:
            while count < (pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

这么一来就很清晰了，测试结果也不存在问题。

• 实现第七个功能，实现查找（research）功能： 比如我们要查找这个400节点是否在链表内，我们需要移动游标遍历每一个节点，然后一个个的去比对，等于我们的item就返回真，不等于我们的item就返回假。 但是还需要考虑特殊情况，也就是当节点为空节点的时候如何处理呢？
  空节点代表cur = self.__head = None，就不用执行while循环而是直接跳到return Flase，这样一来也符合功能的需求，测试结果也不存在问题。
• 实现第八个功能，即实现删除（remove）功能：

  比如我们需要删除400这个节点元素，删除的方法就是讲400节点的前一个节点的next指向400节点的后一个300节点，这样一来就有两个实现方法。

  1. 建立两个游标，一个pre，一个cur，pre游标指向400节点之前的20节点，cur游标指向要删除的400节点，pre.next = cur.next
  2. 建立一个游标，实现同1相同的功能，pre游标指向要删除的400节点之前的20节点，pre.next = pre.next.next
     法二我可以理解，那么我就说说法一吧，如果我们要删除的元素正好在中间： 这样是不是没问题 考虑在两头和空链表的特殊情况如何处理：
     空链表
     意味着cur = self.__head = None，程序不执行while循环，不执行任何操作，这个是没有问题的。
     删除开头的节点 我们还要考虑一种特殊情况，就是这个链表只有一个节点怎么办，也就是cur.next = None，删除后正好self.__head = None，我们的程序可以实现这个特殊情况。
     删除结尾的节点 我们理解一下，如果删除的是最后一个尾节点300，就是讲指向400的pre游标指向位于300节点的cur游标所指向的None，恰好可以完美实现，那么我们的代码就不存在问题。 测试一切正常

完整代码如下：

class Node():
    '''节点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''单链表'''
    def __init__(self,node=None):
        #内部私有函数，链表头的初始化，可以直接建立空链表
        self.__head = node

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None

    def length(self):
        """返回链表的长度"""
        #cur游标，用来移动遍历节点
        #count，用来记录节点数量
        count = 0
        cur = self.__head
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self.__head
        while cur != None:
            print(cur.elem,end=' ')
            cur = cur.next

    def add(self, item):
        """头部添加节点"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """在指定位置添加节点"""
        pre = self.__head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos >= (self.length()-1):
            self.append(item)
        else:
            while count < (pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """删除一个节点"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                #先判断是否为头节点，然后再去处理头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next


    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False



if __name__ == '__main__':
    li = SingleLinkList()
    print(li.is_empty())
    print(li.length())

    li.append(1)
    li.append(2)
    print(li.is_empty())
    print(li.length())

    li.append(3)
    li.append(4)
    li.add(10)
    li.add(20)
    li.insert(2,30)
    li.insert(10,1000)
    li.insert(0,999)
    li.travel()
    print()
    print(li.search(20))
    print(li.search(123))
    li.travel()
    li.remove(999)
    li.travel()
    li.remove(1000)
    li.travel()
    li.remove(30)
    li.travel()