Python单向单端链表

image.png

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None

    def __str__(self):
        return str(self.item)


# 单向链表
class LinkedList(object):
    def __init__(self):
        self.head: Node = None

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

    def length(self):
        """
        O(n) 此处可以存储为一个长度变量
        :return:
        """
        length = 0
        cur = self.head
        while cur is not None:
            cur = cur.next
            length += 1
        return length

    def append(self, value: object):
        """
        O(n) 将元素添加到最后 如果这里是双端链表,那么会有tail指向最后一个,能够提高到O(1)
        :param value:
        :return:
        """
        node = Node(value)
        cur = self.head
        if cur is None:
            self.head = node
        else:
            while cur.next is not None:  # 只有当前节点有下一个节点, 才进行赋值
                cur = cur.next
            cur.next = node

    def add(self, value: object):
        """
        O(1) 将元素添加到头部
        :param value:
        :return:
        """
        node = Node(value)
        node.next = self.head  # 将新节点的下一节点指向当前链表头部第一个节点
        self.head = node  # 更新当前链表的节点

    def insert(self, index, value):
        """
        O(1) or O(n)
        :param index:
        :param value:
        :return:
        """
        # index = index - 1
        if index <= 0 or self.is_empty():
            self.add(value)  # 在头部插入
        elif index >= self.length():
            self.append(value)  # 在尾部插入
        else:
            node = Node(value)
            count = 0
            cur = self.head
            while cur is not None:
                if index - 1 == count:  # 判断是否是需要插入的位置
                    node.next = cur.next  # 将新节点的下一节点指向当前节点(当前cur节点)的下一节点
                    cur.next = node  # 将当前遍历节点的下一节点指向新节点
                    break
                cur = cur.next
                count += 1

    def insert2(self, index, value):
        """
        O(1) or O(n)
        :param index:
        :param value:
        :return:
        """
        if index <= 0 or self.is_empty():
            self.add(value)  # 在头部插入
        elif index >= self.length():
            self.append(value)  # 在尾部插入
        else:
            node = Node(value)
            count = 0
            cur = self.head
            while count < (index - 1):
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node

    def reverse(self):
        """
        反转链表: 顺序遍历每个节点, 将每个节点的next指针指向上一个节点
        """
        cur = self.head  # 当前节点指向头部
        prev_node = None  # 上一个节点

        while cur is not None:
            next_node = cur.next  # 当前节点的下一个节点 必须第一步
            cur.next = prev_node  # 设置当前节点的下一个节点为上一节点(反转指向)

            prev_node = cur  # 更新变量 设置上一个节点为当前节点(下一次循环使用)
            cur = next_node  # 更新变量 设置当前节点为下一节点(下一次循环使用)

            if cur is not None:  # 最后一个节点的next必定为None, 所以这里要判断 设置head指针指向最后一个节点
                self.head = cur

    def remove(self, item):
        cur = self.head  # 双指针-当前
        prev_node: Node = None  # 上一个

        while cur is not None:
            if cur.item == item:
                if prev_node is None:  # 上一个节点
                    self.head = cur.next
                else:
                    prev_node.next = cur.next  # 删除中间元素
                return True
            else:
                prev_node = cur
                cur = cur.next

        return False

    def get(self, index):
        cur = self.head
        count = 0
        while cur is not None:  # 遍历节点
            if count == index:  # 如果次数一样
                return cur.item  # 返回元素
            cur = cur.next
            count += 1
        return None

    def find(self, item):
        cur = self.head
        count = 0
        while cur is not None:
            if cur.item == item:
                return count
            cur = cur.next
            count += 1
        return -1

    def __iter__(self):
        """遍历"""
        cur = self.head
        while cur is not None:
            yield cur.item
            cur = cur.next


if __name__ == '__main__':
    linked = LinkedList()
    assert linked.is_empty() is True

    linked.append(1)
    linked.append(2)
    linked.append(3)
    linked.add(99)

    # 链表长度
    li = [i for i in linked]
    assert li == [99, 1, 2, 3]
    assert linked.length() == len(li)

    # 链表反转
    linked.reverse()
    li = [i for i in linked]
    assert li == [3, 2, 1, 99]
    assert linked.length() == len(li)

    # 链表插入
    linked.insert(1, 100)
    li = [i for i in linked]
    assert li[1] == 100

    # 链表删除
    linked.remove(100)
    li = [x for x in linked]
    assert li == [3, 2, 1, 99]

    # 获取元素
    assert linked.get(3) == 99
    assert linked.get(4) is None

    # 查找位置
    assert linked.find(99) == 3
    assert linked.find(3) == 0

    print(li)