python单向链表实例详解

# Functions  函数声明
class Node():
    """
    存放节点类
    每次调用该类，实例化一个节点
    默认每个节点中有数据区，next区。
    数据区为该数据，next区为空
    """
    def __init__(self, item,next=None):
        self.item = item
        self.next = next
        pass

class Linklist():
    """
    存放数据类
    将所有的节点存放起来的容器
    首先，默认链表为空，在这里需要有一个头节点，默认头节点为空

    """
    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        return self.head == None

    def append(self, item):
        """
        往链表尾部添加数据
        1、实例化游标：使用游标指向每一个数据，检索数据和判断数据next是否为空
        2、移动游标，从头节点开始，每次使用self.next移动，以为next指向的就是下一个数据
        3、添加数据，首先判断链表是否为空，为空的情况下，直接将头节点等于node数据
        4、如果不为空，需要从头节点开始，移动游标，判断游标指向的next是否为空
        5、使用循环不停的移动节点，当遇到节点中的next为空的情况下停止移动
        6、循环条件： 当 条件 != None, 进入循环获取，当cur为空时就不会进入循环，所以在这里要使用 cur != None
        """
        # 首先要实例化一个节点
        node = Node(item)
        # 如果链表为空
        if self.is_empty():
            # 直接将头节点的next添加node
            self.head = node
        else:
            # 实例化一个游标
            cur = self.head
            while cur.next != None:
                # 移动游标，得到最后一个游标的数据
                cur = cur.next
            # 将移动后的数据的下一个next添加上 node
            cur.next=node
            pass

    def travel(self):
        """遍历数据"""
        # 实例化一个游标
        cur = self.head
        # 数据链为空的情况
        if self.is_empty():
            print('')
        else:
            # 获取每个数据区中的数据
            # 移动游标，每移动一次，输出一次数据区内的数据
            while cur != None:
                print(cur.item, end=' ')
                cur = cur.next
            print()

    def length(self):
        """返回链表的长度"""
        # 实例化游标
        cur = self.head
        # 计数，这里对空链表进行判断，如果是链表，则不会进入循环，直接输出 0
        count = 0
        # 移动游标，获取下一个数据，然后让count +=1
        while cur != None:
            # 计数
            count+=1
            # 移动游标
            cur = cur.next
        return count

    def add(self, item):
        """
        头部添加数据
        分析： 将数据添加到第一个节点当中
        1、 需要先将node的next指向 原第一个节点，这原第一个节点就是self.head
        2、 再讲self.head指向node进行连接
        """
        # 先实例化节点
        node = Node(item)
        # 将数据添加到头部当中
        node.next=self.head
        self.head=node

    def insert(self, index, item):
        """
        指定位置添加数据
        分析：
        1、首先要找到，该位置的数据
        2、将要添加的数据next等于 原位置的next数据
        3、原数据的 next等于node新数据
        """
        if index<=0:
            # 如果输入的索引小于或者等于O，默认使用头插发
            self.add(item)
        elif index>self.length():
            # 如果输入的索引大于链表的长度,使用尾插法
            self.append(item)
        else:
            # 实例化数据节点
            node = Node(item)
            # 找到该数据的位置
            # 实例化一个游标
            cur = self.head
            # 计数
            conent = 0
            while conent<(index-1):
                conent+=1
                cur = cur.next

            node.next=cur.next
            cur.next=node

    def search(self, item):
        """
        查询指定的数据是否存在
        分析： 查询指定的数据，需要对整个链表扫描，判断这个数据是否等的该节点中的数据
        """
        # 实例化一个游标
        cur = self.head
        # 进行判断是否相等
        while cur != None:
            # 判断
            if cur.item == item:
                return True
            else:
                cur = cur.next
            pass
        # 否则返回False
        return False

    def remove(self, item):
        """
        移除指定的数据
        分析：
        1、删除数据，需要首先判断数据是否存在
        2、找到该数据所在的位置，将该数据的上一个数据的next指向自己的next
        3、如何获取该数据的指向，和上一个数据的指向
        4、需要定义两个指针
        5、先将两个指针相等，再讲一个指针先移动一次，再同时移动

        """
        # 先找到该数据
        cur = self.head
        por = None

        while cur != None:
            if cur.item==item:
                # 要判断是否为第一个节点
                if cur == self.head:
                    self.head = cur.next
                else:
                    por.next = cur.next
                break
            else:
                # 如果在当前节点中没有相等的，将节点进行移动
                # 移动要注意，现将两个游标相等，再讲另一个游标移动一次
                por = cur
                cur = cur.next

# 程序的入口
if __name__ == "__main__":
    s = Linklist()
    s.append(100)
    s.append(200)
    s.append(300)
    s.add(1)
    s.add(12)
    s.insert(-1,6)
    
    s.travel()       #  6 12 1 100 200 300 
    print(s.length())  # 6
    print(s.search(11)) # False
    s.remove(12)
    s.travel()       # 6 1 100 200 300 
    print(s.length())  # 5
    print(s.search(11)) # False
    pass