算法-01-单链表

# 首先定义一个结点类
class Node(object):
    def __init__(self, elem):
        # 生成结点的数据区
        self.elem = elem
        # 生成结点的指针域
        self.next = None

# 其次定义出链表类
class SingleLinkList(object):
    # 用__init__方法实现,当创建链表时,同时创建一个头结点.如果没有头结点,那它无法实现指针与Node类生成的结点之间的链接.
    def __init__(self, node=None): # 用node=None是为了默认头结点为空,这也是为了使你在创建SingleLinkList对象时,不传头结点的情况下,也能正常输出
        self.__head = node

    # 判空同理,也不需要传其他参数进来
    def is_empty(self):
        return self.__head == None

    # 求链表长度,求的也是该链表类的对象,因此不需要再传其他参数进来
    def length(self):
        count = 0
        cur = self.__head # 使指针指向头结点
        while cur != None:
            count += 1
            cur = cur.next
        return count

    # 遍历的是链表,也即是链表类的对象.而self就是链表类对象,因此不需要再传其他参数进来
    def travel(self):
        cur = self.__head
        while cur.next != None:
            print(cur.elem)
            cur = cur.next

    # 在头部添加结点,需要把该结点给传进来,因此需要传个item(结点)
    def add(self, item):
        node = Node(item)
        node.next = self.__head # 使新结点先指向原头结点
        self.__head = node # 再使头结点指向新结点,这个顺序不能改变,因为若是先让头结点指向新结点的话,就会使头结点与其后的其他结点断开连接,致使数据丢失.

    # 同add类似,尾部添加结点时,需要把该结点的数据域作为参数传进来
    def append(self, item):
        node = Node(item) # 创建想要添加的结点
        if self.is_empty(): # 判断链表是否为空,因为空链表是没有next域的,也即空链表会在while循环处出错
            self.__head = node # 当链表为空时,则添加的链表就会成为该链表的头结点
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node # 把结点添加进链表

    # 插入需要给三个参数,一个是要插入的链表,一个是插入的位置,另一个是要插入的结点
    def insert(self, pos, item):
        node = Node(item)
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1): # 不能有等于,因为等于的话表示在尾结点之前插入新结点了.注意了pos等于几,就表示在下标几之前添加,
            self.append(item)         # eg: pos=2,表示在链表下标为2的结点前插入新结点.也即是在链表下标1-2之间插入新结点,而非2后
        else:
            count = 0
            pre = self.__head
            while count < pos-1:
                count += 1
                pre = pre.next
            node.next = pre.next
            pre.next = node

    # 删除指定结点,因此需要把你想要删除的结点传进来
    def remove(self, item):
        cur = self.__head # 先使cur游标指向首结点
        pre = None # 使pre游标指向为None.是为下面pre指向cur做铺垫
        while cur != None:
            if cur.elem == item:
                # 先判断此结点是否为头结点
                if cur == self.__head:
                    self.__head = cur.next # 实现对头结点的删除
                    break # 当找到想要删除的值时,需要退出循环
                else:
                    pre.next = cur.next # 实现对结点的删除
                    break
            else:
                pre = cur  # 使pre游标指向cur游标的位置
                cur = cur.next  # 实现cur游标向后移一步的操作,这一句代码必须要放在pre指向cur之后,才能保证俩游标之间总会隔着一个结点
                break

    # 查找结点是否存在,也需要你传进来你想要查的结点
    def search(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

# 创建一个结点,数据域为100,指针域默认为空
node = Node(100)
# 把创建的结点传进链表中作为头结点
single_obj = SingleLinkList(node)
single_obj.travel()