Python链表之单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

• 表元素域elem用来存放具体的数据。
• 链接域next用来存放下一个节点的位置（python中的标识）
• 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

class Node(object):
    """单链表的节点"""
    def __init__(self, item):
        # item存放数据元素
        self.elem = item
        # next是下一个节点的标识
        self.next = None


class SingleLinkList(object):
    """单链表"""
    def __init__(self):  # 初始化一个空链表，变量_head指向None
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head is None  # 使用该语句也行，不过会提示不符合PEP8规范：self._head == None

    def length(self):
        """链表长度"""
        # cur游标，用来移动遍历节点
        cur = self._head
        # count记录数量，为什么初始count=0，因为当链表时空时，即cur=self._head=None，这是不会进入while循环，直接返回0，如果初始count为1的话就不行了
        count = 0
        # 当遍历完链表时，尾节点是指向None的，当未到达尾部时
        while cur is not None:  # 使用该语句也行，不过会提示不符合PEP8规范：cur != None
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        # cur游标，用来移动遍历节点
        cur = self._head
        if self.is_empty():
            print("链表为空")
        else:
            while cur is not None:  # 使用该语句也行，不过会提示不符合PEP8规范：cur != None
                print(cur.elem, end=" ")  # cur不指向None，打印节点的数据元素，end=“”表示不换行
                # 将cur后移一个节点
                cur = cur.next
            print("")  # 最后换一次行

    def add(self, item):
        """头部添加元素，头插法"""
        # 创建一个保存item值的节点
        node = Node(item)
        # 以下两行当链表为空或不为空时均满足，_head指向None,node.next指向_head指向的位置，即None,然后_head又指向node
        # 将新节点的链接域next指向头节点，即_head指向的位置
        node.next = self._head
        # 将链表的头_head指向新节点
        self._head = node

    def append(self, item):
        """尾部添加元素，尾插法"""
        # 创建一个保存item值的节点
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将_head指向新节点
        if self.is_empty():
            self._head = node
        # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            # cur游标，用来移动遍历节点
            cur = self._head
            while cur.next is not None:   # 使用该语句也行，不过会提示不符合PEP8规范：cur.next != None
                cur = cur.next
            # 当循环结束时，cur正好指向尾节点。因为在单链表中，尾节点的next指向的是None，跳出循环时刚好cur指向尾节点
            # 尾节点的next指向新节点
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
        :param pos：从0开始
        :param item：需要插入的元素
        """
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾部插入
        elif pos > self.length() - 1:
            self.append(item)
        # 中间位置
        else:
            # 创建一个保存item值的节点
            node = Node(item)
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self._head
            count = 0
            while count < (pos - 1):  # 例：链表长为5（位置为0，1，2，3，4），指定位置pos为2，则是在位置2插入一个新节点，位置2及之后的节点往后移
                count += 1
                pre = pre.next
            # 跳出循环时，pre刚好是指向位置为1的节点
            # 先将新节点node的next指向插入位置的节点，即位置2的节点
            node.next = pre.next
            # 将插入位置的前一个节点，即位置1的节点的next指向新节点
            pre.next = node

    def remove(self, item):
        """删除节点，使用两个游标，pre在cur的前一个位置"""
        cur = self._head
        pre = None  # 初始pre指向None
        while cur is not None:  # 使用该语句也行，不过会提示不符合PEP8规范：cur != None
            # 当节点的数据元素等于item时则表示找到了该元素
            if cur.elem == item:
                # 先判断此节点是否是头节点
                if cur == self._head:  # 也可以使用if not pre：来进行判断
                    # 将头指针指向头节点的后一个节点
                    self._head = cur.next
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点，例如需要删除的是位置2的节点，则将位置1的next指向位置3（位置3就是位置2的next）
                    pre.next = cur.next
                break
            else:
                # 如果没有找到元素item，则继续按链表后移节点
                pre = cur
                cur = cur.next

    def search(self, item):
        """链表查找节点是否存在，并返回True或者False"""
        cur = self._head
        # 从前往后遍历
        while cur is not None:  # 使用该语句也行，不过会提示不符合PEP8规范：cur != None
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.travel()
    ll.add(1)
    ll.travel()
    ll.remove(1)
    ll.travel()
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    print(ll.length())
    ll.travel()
    ll.remove(3)
    ll.travel()