链表是一种基础且重要的线性数据结构。与传统数组在内存中连续存储元素不同，链表通过节点间的指针（或引用）将分散的内存块串联起来。每个节点通常包含两部分：实际存储的数据元素，以及指向下一个节点的链接。这种结构赋予了链表动态伸缩的能力，插入或删除元素时仅需调整指针，无需像数组一样移动大量数据。

链表的类型多样，主要包括单向链表、双向链表和循环链表。单向链表每个节点仅有指向下一个节点的指针，遍历方向单一。双向链表为每个节点增加了指向前一个节点的指针，支持双向遍历。循环链表则将最后一个节点的指针指向头节点，形成一个逻辑上的环，可以从任意节点出发遍历整个链表。

链表的优势在于高效的插入和删除操作，特别适合元素数量频繁变化的场景。然而，其缺点也很明显：随机访问效率低，必须从头节点开始顺序查找指定位置的元素；同时，由于存储指针需要额外内存，空间开销大于数组。

单向链表

单向链表是最基本的链表形式，每一个节点只包含数据和指向下一个节点的引用。头节点是链表的入口，通常指向第一个有效节点；尾节点的指针为None，标志着链表的结束。

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

class SinglyLinkedList:
    def __init__(self):
        self._head = None

    def insert_front(self, val):
        new_node = ListNode(val)
        new_node.next = self._head
        self._head = new_node

    def insert_back(self, val):
        new_node = ListNode(val)
        if not self._head:
            self._head = new_node
            return
        current = self._head
        while current.next:
            current = current.next
        current.next = new_node

    def delete(self, val):
        if not self._head:
            return
        if self._head.val == val:
            self._head = self._head.next
            return
        current = self._head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next

    def search(self, val):
        current = self._head
        while current:
            if current.val == val:
                return current
            current = current.next
        return None

    def traverse(self):
        result = []
        current = self._head
        while current:
            result.append(current.val)
            current = current.next
        return result

    @property
    def is_empty(self):
        return self._head is None

    @property
    def length(self):
        count = 0
        current = self._head
        while current:
            count += 1
            current = current.next
        return count

循环链表

循环链表是单向链表的一种变体，其尾节点不再指向None，而是指向头节点，构成闭环。这种结构常用于需要无限循环访问的场景，如操作系统的进程调度。操作循环链表时，判断遍历结束的条件不再是节点指针为None，而是指针回到了头节点。

class CircularLinkedList:
    def __init__(self):
        self._head = None

    def insert_front(self, val):
        new_node = ListNode(val)
        if not self._head:
            self._head = new_node
            new_node.next = new_node
        else:
            new_node.next = self._head.next
            self._head.next = new_node
            self._head = new_node

    def insert_back(self, val):
        new_node = ListNode(val)
        if not self._head:
            self._head = new_node
            new_node.next = new_node
        else:
            new_node.next = self._head.next
            self._head.next = new_node
            self._head = new_node

    def delete(self, val):
        if not self._head:
            return
        if self._head.val == val:
            if self._head.next == self._head:
                self._head = None
            else:
                current = self._head
                while current.next != self._head:
                    current = current.next
                current.next = self._head.next
                self._head = current.next
            return
        current = self._head
        while current.next != self._head:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next

    def search(self, val):
        if not self._head:
            return None
        current = self._head.next
        while current != self._head:
            if current.val == val:
                return current
            current = current.next
        if self._head.val == val:
            return self._head
        return None

    def traverse(self):
        if not self._head:
            return []
        result = []
        current = self._head.next
        while current != self._head:
            result.append(current.val)
            current = current.next
        result.append(self._head.val)
        return result

    @property
    def length(self):
        if not self._head:
            return 0
        count = 0
        current = self._head
        while True:
            count += 1
            current = current.next
            if current == self._head:
                break
        return count

双向链表

双向链表在每个节点中增加了指向前驱节点的指针，从而支持双向遍历。这使得插入和删除操作更加灵活，因为可以直接获取前后节点的引用。代价是每个节点需要额外存储一个指针，内存占用更高。

class DoublyListNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self._head = None

    def insert_front(self, val):
        new_node = DoublyListNode(val)
        if self._head:
            self._head.prev = new_node
            new_node.next = self._head
        self._head = new_node

    def insert_back(self, val):
        new_node = DoublyListNode(val)
        if not self._head:
            self._head = new_node
            return
        current = self._head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    def delete(self, val):
        if not self._head:
            return
        if self._head.val == val:
            self._head = self._head.next
            if self._head:
                self._head.prev = None
            return
        current = self._head
        while current:
            if current.val == val:
                if current.next:
                    current.next.prev = current.prev
                current.prev.next = current.next
                return
            current = current.next

    def search(self, val):
        current = self._head
        while current:
            if current.val == val:
                return current
            current = current.next
        return None

    def traverse_forward(self):
        result = []
        current = self._head
        while current:
            result.append(current.val)
            current = current.next
        return result

    @property
    def length(self):
        count = 0
        current = self._head
        while current:
            count += 1
            current = current.next
        return count

跳表（Skip List）

跳表是一种概率性的数据结构，旨在解决有序链表查询效率低的问题。它通过在链表之上建立多层索引，使查找、插入和删除操作的平均复杂度降至 O(log n)。每个节点包含多个前进指针（forward），指向不同层级的下一个节点。新节点的层级由随机函数决定，以维持结构的平衡。

跳表的查找从最高层开始，逐层向下，每次跳过多个节点，类似于二分查找的过程。插入和删除操作则需要更新所有受影响的层级指针。跳表的实现相对简单，广泛应用在 Redis 等内存数据库中。

import random

class SkipNode:
    def __init__(self, key=None, value=None, level=0):
        self.key = key
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self):
        self._head = SkipNode()
        self._level = 0
        self._max_level = 16

    def _random_level(self):
        level = 0
        while random.random() < 0.5 and level < self._max_level:
            level += 1
        return level

    def search(self, key):
        current = self._head
        for i in range(self._level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        if current and current.key == key:
            return current.value
        return None

    def insert(self, key, value):
        update = [None] * (self._level + 1)
        current = self._head
        for i in range(self._level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]

        if current and current.key == key:
            current.value = value
        else:
            new_level = self._random_level()
            if new_level > self._level:
                for i in range(self._level + 1, new_level + 1):
                    update.append(self._head)
                self._level = new_level
                self._head.forward.extend([None] * (new_level - len(self._head.forward) + 1))
            new_node = SkipNode(key, value, new_level)
            for i in range(new_level + 1):
                new_node.forward[i] = update[i].forward[i] if i < len(update) else None
                if i < len(update):
                    update[i].forward[i] = new_node

    def delete(self, key):
        update = [None] * (self._level + 1)
        current = self._head
        for i in range(self._level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current
        current = current.forward[0]

        if current and current.key == key:
            for i in range(self._level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
            while self._level > 0 and not self._head.forward[self._level]:
                self._level -= 1

    def display(self):
        result = []
        current = self._head.forward[0]
        while current:
            result.append({current.key: current.value})
            current = current.forward[0]
        return result