链表

链表结构

class Node:
    def __init__(self, item, next_):
        self.item = item     # 数据域
        self.next_ = next_   # 指针域（指向下一个节点）

class LinkList:
    # 初始化
    def __init__(self):
        # 初始化头结点
        self.head: Node = Node(None, None)
        # 初始化链表长度
        self.length: int = 0

    # 清空链表
    def clear(self):
        self.head.next_ = None
        self.length = 0

    # 获取长度
    def get_length(self) -> int:
        return self.length

    # 判断链表是否为空
    def is_empty(self):
        return self.length == 0

    # 获取指定位置的元素
    def get_item(self, index):
        node_t: Node = self.head.next_  # 从头结点开始
        for i in range(index):
            node_t = node_t.next_ # 依次向后跳index次即可

        return node_t.item

    # 追加元素
    def append(self, item):
        # 找到最后一个节点
        node_t: Node = self.head
        while node_t.next_ is not None: # 循环查找直到指针域为空为最后节点
            node_t = node_t.next_
        # 创建新节点，保存元素
        node_new: Node = Node(item, None)
        # 最后一个节点指向新节点
        node_t.next_ = node_new
        # 长度+1
        self.length += 1

    # 任意位置插入元素
    def insert(self, item, index):
        node_pre: Node = self.head.next_
        # 找到插入位置的前一个节点
        for i in range(index - 1): # 向后跳index-1次即可
            node_pre = node_pre.next_
        # 找到插入位置的节点
        node_curr = node_pre.next_
        # 创建新节点，指向插入位置的节点
        node_new: Node = Node(item, node_curr)
        # 插入位置的前一个节点指向新节点
        node_pre.next_ = node_new
        # 长度+1
        self.length += 1

    # 删除指定位置的元素，返回该元素
    def delete(self, index):
        # 找到当前位置的前一个节点
        node_pre: Node = self.head
        for i in range(index - 1):
            node_pre = node_pre.next_
        # 找到当前位置的节点
        node_curr: Node = node_pre.next_
        # 找到当前位置的后一个节点
        node_next: Node = node_curr.next_
        # 将前一个节点的指针指向后一个节点
        node_pre.next_ = node_next
        # 长度-1
        self.length -= 1
        return node_curr.item

    # 查找元素的位置
    def get_index(self, item):
        # 从头节点开始遍历每一个节点，比较item
        node_t: Node = self.head
        # 记录位置
        index = 0
        while node_t.next_ is not None:
            node_t = node_t.next_ # 节点后跳
            if node_t.item == item:
                return index
            index += 1 # 计数+1

        return -1

    # 遍历打印链表
    def show_items(self):
        node_t: Node = self.head
        if self.length > 0:
            while node_t.next_ is not None:
                node_t = node_t.next_
                print(node_t.item, end=' ')
            print()
        else:
            print('empty')

    # 反转全部节点
    def reverse(self):
        # 判断是否为空链表
        if self.is_empty():
            return
        else:
            self.reverse_node(self.head.next_) # 从头节点的下一个节点开始反转

    # 反转单个节点
    def reverse_node(self, curr: Node):
        # 递归出口, 遍历到最后一个节点时，不需要继续反转curr的下一个节点
        if curr.next_ is None:  # 如果递归遍历到最后一个节点
            self.head.next_ = curr  # 头节点指向最后一个节点
            return curr # 返回反转后的节点
        # 需要将当前节点的下一个节点反转
        # 递归反转curr的下一个节并返回
        pre = self.reverse_node(curr.next_)
        # 反转后的节点指向当前节点，反转后的节点在前，当前节点在后
        pre.next_ = curr
        # 当前节点在后，指针域为空
        curr.next_ = None
        # 返回反转后的节点
        return curr

	
if __name__ == '__main__':
    link = LinkList()
    link.append('node1')
    link.append('node2')
    link.append('node3')
    link.show_items()

    link.insert('insert item', 2)
    link.show_items()
    
    print(link.get_index('node3'))
    print(link.get_item(2))

    print(link.delete(1))
    link.show_items()

	link.reverse()
    link.show_items()

    print(link.is_empty())
    link.clear()
    print(link.is_empty())