python的链表基础知识点

Python的链表基础知识点

链表的定义

链表是一种常见的数据结构，它的节点包含两个部分：数据和指向下一个节点的指针。链表的最后一个节点指向None。

Python中链表的定义可以使用class来实现。例如定义一个链表节点的类：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

每个链表节点的数据存储在val中，指向下一个节点的指针保存在next中。

链表的基本操作

链表的基本操作包括：

1. 根据值查找节点
2. 在指定节点之后插入新节点
3. 删除指定节点

以下是详细的实现方法：

根据值查找节点

以下代码展示了如何查找给定链表中第一个值为x的节点：

def find_node(head, x):
    curr = head
    while curr and curr.val != x:
        curr = curr.next
    return curr

参数head代表链表的头节点，参数x为需要查找的值。从头节点开始，遍历链表中的每个节点，直到找到值为x的节点或遍历到链表的末尾。如果找到值为x的节点，返回该节点；如果找不到值为x的节点，返回None。

在指定节点之后插入新节点

以下代码展示了如何在链表中指定的节点p之后插入一个新节点：

def insert_after(p, new_node):
    new_node.next = p.next
    p.next = new_node

参数p代表要在其之后插入新节点的节点，参数new_node为要插入的新节点。将新节点的next属性指向p的下一个节点（也就是p原本指向的节点），再将p的next属性指向新节点，即可完成插入新节点的操作。

删除指定节点

以下代码展示了如何删除链表中指定的节点p：

def delete_node(head, p):
    if not head:
        return None
    if head == p:
        return head.next
    curr = head
    while curr.next and curr.next != p:
        curr = curr.next
    if curr.next:
        curr.next = curr.next.next
    return head

参数head代表链表的头节点，参数p为要删除的节点。如果链表为空，直接返回None。如果要删除的节点就是头节点，将头节点指向下一个节点即可完成删除操作。如果不是头节点，需要遍历整个链表，找到节点p的前驱节点，然后将前驱节点的next属性指向p的下一个节点，即可完成删除操作。

示例说明

示例1

以下代码展示了如何使用链表来实现LRU（最近最少使用）算法：

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_tail(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = self.tail.prev
        self.tail.prev.next = node
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            node = self.hashmap[key]
            self.move_to_tail(node)
            return node.val[1]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = (key, value)
            self.move_to_tail(node)
        else:
            if len(self.hashmap) == self.capacity:
                node = self.head.next
                del self.hashmap[node.val[0]]
                node.val = (key, value)
                self.hashmap[key] = node
                self.move_to_tail(node)
            else:
                node = ListNode((key, value))
                self.hashmap[key] = node
                node.prev = self.tail.prev
                self.tail.prev.next = node
                node.next = self.tail
                self.tail.prev = node

这是一个LRUCache的实现，使用了链表来维护访问顺序。具体实现方法是，使用一个哈希表来存储key-value的键值对，使用一个双向链表来维护访问顺序。每次访问或添加一个元素时，将其移动到链表的末尾。如果缓存已满，则删除链表头部的元素。

示例2

以下代码展示了如何使用链表来实现一个栈：

class StackNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class MyStack:

    def __init__(self):
        self.head = None

    def push(self, x: int) -> None:
        node = StackNode(x)
        node.next = self.head
        self.head = node

    def pop(self) -> int:
        if self.head:
            x = self.head.val
            self.head = self.head.next
            return x

    def top(self) -> int:
        if self.head:
            return self.head.val

这是一个栈的实现，使用了链表来存储栈中的元素。入栈操作时，将新元素插入到链表头部。出栈操作时，返回链表头部的元素，并将头节点指向下一个元素。获取栈顶元素的操作同样是返回链表头部的元素。