链表

简介

链表（Linked List）在内存中并不连续，更适合插入、删除等操作。

链表的基本元素如下：

链表节点：每个节点分为两个部分，即数据域和指针域。数据域存储的一般是数字类型，指针域存储的是下一个节点所在的内存空间地址。
头节点：指向链表的第一个节点
尾节点：指向链表的最后一个节点。
None：链表最后一个节点的指针域，为空。

常见链表类型

单向链表，即普通链表，每个节点的指针域只指向下一个节点，整个链表是无环的。
环形链表，如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表，与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

链表的常见操作

Python

Python没有标准的链表结构。

声明链表并初始化。数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以下代码中的链表可记作链表 n0 。

class ListNode:
    """链表节点类"""
    def __init__(self, val: int):
        self.val: int = val               # 节点值
        self.next: ListNode | None = None # 指向下一节点的引用
        
# 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

插入节点。在链表中插入节点非常容易，假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为 O(1) 。

def insert(n0: ListNode, P: ListNode):
    """在链表的节点 n0 之后插入节点 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

删除节点。在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

def remove(n0: ListNode):
    """删除链表的节点 n0 之后的首个节点"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

访问节点。不同于数组支持随机访问，链表只能顺序访问。程序需要从头节点出发，逐个向后遍历。也就是说，访问链表的第 i 个节点需要循环 i−1 轮，时间复杂度为 O(n) 。

def access(head: ListNode, index: int) -> ListNode | None:
    """访问链表中索引为 index 的节点"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

查找节点。遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。

def find(head: ListNode, target: int) -> int:
    """在链表中查找值为 target 的首个节点"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

Go

声明链表并初始化

/* 链表节点结构体 */
type ListNode struct {
    Val  int       // 节点值
    Next *ListNode // 指向下一节点的指针
}

// NewListNode 构造函数，创建一个新的链表
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// 构建节点之间的引用
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

简介​

常见链表类型​

链表的常见操作​

Python​

Go​

简介

常见链表类型

链表的常见操作

Python

Go