数组和链表

1. 介绍

数组（Array） 用于存储固定数量的相同类型的元素。元素在内存中是连续存储的，通过索引访问，提供了高效的随机访问能力和简单的实现，适用于需要快速访问且不需要频繁动态调整大小的场景。

链表（Linked List） 每个节点包含数据和指向下一个节点的指针（在双链表中，还包含指向前一个节点的指针）。节点在内存中不一定是连续的，提供了灵活的大小调整和高效的插入删除操作，适用于动态数据集合和需要频繁插入删除的情况，但访问速度较慢且内存开销较大。

1.1 内存结构

数组：内存连续性，数组的元素在内存中是连续存储的，地址计算简单且快速；固定大小，数组的大小在创建时定义，之后无法调整（动态数组可以在运行过程中动态扩容）。
链表：内存分散，链表的节点在内存中可能是非连续的，每个节点包含指向其他节点的指针；动态大小，链表的大小可以动态调整，可以随时增加或删除节点。

1.2 访问时间

数组：随机访问，支持常数时间复杂度 O(1) 的随机访问。可以通过索引直接访问任何元素，效率高。
链表：顺序访问，访问某个元素时需要从头节点开始逐个遍历，时间复杂度为 O(n)。不支持直接随机访问。

1.3 插入和删除

数组：插入，在数组的中间或开头插入元素时，需要移动后续的元素，时间复杂度为 O(n)。在数组末尾插入元素通常为 O(1)，但前提是数组有足够的空间。删除，在数组的中间或开头删除元素时，需要移动后续的元素，时间复杂度为 O(n)。在末尾删除元素通常为 O(1)。
链表：插入，在链表中插入元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下），在链表的末尾插入元素也可以在常数时间内完成（假设已知末尾）。删除，在链表中删除元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下）。

1.4 内存使用

数组：空间效率，数组的内存使用是连续的，额外内存开销较少。每个元素占用固定的内存空间。
链表：空间开销，每个节点需要额外的内存来存储指针（在双链表中，还需要存储前驱指针），因此内存开销较大。

1.5 性能

数组：优点，在随机访问和遍历方面表现优异，因为元素存储在连续内存中，访问速度快。缺点，插入和删除操作效率较低，尤其是在数组中间部分。
链表：优点，插入和删除操作效率较高，尤其在链表的开头或中间部分。大小动态调整灵活。缺点，访问操作较慢，需要顺序遍历节点，额外内存开销较大。

1.6 适用场景

数组：适合需要频繁随机访问的应用，如静态数据集合、缓存数据、固定大小的数据集合。
链表：适合需要频繁插入和删除的应用，如动态数据集合、栈和队列的实现、数据量动态变化的情况。

1.7 数组 vs 链表

特性	数组	链表
存储结构	连续内存空间	不连续的内存空间，每个元素都有指针指向下一个元素
访问速度	支持快速随机访问，时间复杂度为 O(1)	随机访问较慢，时间复杂度为 O(n)
插入和删除	插入和删除操作较慢，时间复杂度为 O(n)	插入和删除操作较快，时间复杂度为 O(1)（在已知位置时）
内存分配	需要在创建时指定大小，大小不可动态调整	动态分配内存，大小可以在运行时调整
空间效率	可能浪费内存（如果未使用的空间较多）	只使用实际存储的数据，没有预留空间
遍历效率	遍历速度快，缓存友好	遍历速度较慢，可能导致缓存不友好
实现复杂性	实现简单	实现复杂，需要管理指针
使用场景	适合需要快速访问和较少插入删除的场景	适合频繁插入和删除的场景

2. 代码案例

2.1 数组实现

# ======================数组==========================
class Array:
    def __init__(self, size):
        """
        初始化一个指定大小的数组。
        :param size: 数组的大小
        """
        self.size = size
        self.array = [None] * size  # 初始化一个大小为 `size` 的数组，元素均为 None

    def set(self, index, value):
        """
        设置数组指定索引位置的值。
        :param index: 要设置的索引位置
        :param value: 要设置的值
        :raises IndexError: 如果索引超出范围，则抛出异常
        """
        if 0 <= index < self.size:
            self.array[index] = value
        else:
            raise IndexError("索引超出范围")

    def get(self, index):
        """
        获取数组指定索引位置的值。
        :param index: 要获取的索引位置
        :return: 索引位置的值
        :raises IndexError: 如果索引超出范围，则抛出异常
        """
        if 0 <= index < self.size:
            return self.array[index]
        else:
            raise IndexError("索引超出范围")

    def delete(self, index):
        """
        删除数组指定索引位置的值，并将该位置设置为 None。
        :param index: 要删除的索引位置
        :raises IndexError: 如果索引超出范围，则抛出异常
        """
        if 0 <= index < self.size:
            self.array[index] = None
        else:
            raise IndexError("索引超出范围")

    def __repr__(self):
        """
        返回数组的字符串表示。
        :return: 数组的字符串表示
        """
        return repr(self.array)

2.2 单链表实现

# ======================单链表==========================
class Node:
    def __init__(self, data):
        """
        节点类，用于链表的节点。
        :param data: 节点存储的数据
        """
        self.data = data  # 节点的数据
        self.next = None  # 指向下一个节点的指针

class SinglyLinkedList:
    def __init__(self):
        """
        初始化一个单链表。
        """
        self.head = None  # 链表的头节点初始化为空

    def append(self, data):
        """
        向链表的末尾添加一个新节点。
        :param data: 新节点的数据
        """
        new_node = Node(data)  # 创建一个新节点
        if not self.head:
            # 如果链表为空，新节点成为头节点
            self.head = new_node
            return
        last = self.head
        # 遍历到链表的最后一个节点
        while last.next:
            last = last.next
        last.next = new_node  # 将新节点链接到链表的末尾

    def delete(self, data):
        """
        删除链表中第一个匹配指定数据的节点。
        :param data: 要删除的节点的数据
        """
        current = self.head
        if not current:
            return

        # 如果要删除的是头节点
        if current.data == data:
            self.head = current.next
            return

        # 遍历链表，寻找要删除的节点
        prev = None
        while current and current.data != data:
            prev = current
            current = current.next

        if current:
            prev.next = current.next  # 跳过要删除的节点

    def get(self, data):
        """
        查找链表中第一个匹配指定数据的节点，并返回节点数据。
        :param data: 要查找的节点的数据
        :return: 节点的数据，如果未找到则返回 None
        """
        current = self.head
        while current:
            if current.data == data:
                return current.data
            current = current.next
        return None

    def print_list(self):
        """
        打印链表的所有节点。
        """
        current = self.head
        if not current:
            print("链表为空")
            return
        result = []
        while current:
            result.append(current.data)
            current = current.next
        print(" -> ".join(map(str, result)) + " -> None")  # 打印链表内容

2.3 双向链表实现

# ======================双链表==========================
class DoublyNode:
    def __init__(self, data):
        """
        双向链表的节点类。
        :param data: 节点存储的数据
        """
        self.data = data  # 节点的数据
        self.next = None  # 指向下一个节点的指针
        self.prev = None  # 指向前一个节点的指针

class DoublyLinkedList:
    def __init__(self):
        """
        初始化一个双向链表。
        """
        self.head = None  # 链表的头节点初始化为空

    def append(self, data):
        """
        向双向链表的末尾添加一个新节点。
        :param data: 新节点的数据
        """
        new_node = DoublyNode(data)  # 创建一个新节点
        if not self.head:
            # 如果链表为空，新节点成为头节点
            self.head = new_node
            new_node.prev = new_node  # 指向自己
            new_node.next = new_node  # 指向自己
            return

        # 找到链表的最后一个节点
        last = self.head.prev
        last.next = new_node
        new_node.prev = last
        new_node.next = self.head
        self.head.prev = new_node

    def delete(self, data):
        """
        删除双向链表中第一个匹配指定数据的节点。
        :param data: 要删除的节点的数据
        """
        current = self.head
        if not current:
            return

        while True:
            if current.data == data:
                if current == self.head:  # 如果要删除的是头节点
                    if current.next == current:  # 只有一个节点
                        self.head = None
                    else:
                        self.head = current.next
                        self.head.prev = current.prev
                        current.prev.next = self.head
                else:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                return

            current = current.next
            if current == self.head:
                break

    def get(self, data):
        """
        查找双向链表中第一个匹配指定数据的节点，并返回节点数据。
        :param data: 要查找的节点的数据
        :return: 节点的数据，如果未找到则返回 None
        """
        if not self.head:
            return None

        current = self.head
        while True:
            if current.data == data:
                return current.data
            current = current.next
            if current == self.head:
                break
        return None

    def print_list(self):
        """
        打印双向链表的所有节点。
        """
        if not self.head:
            print("链表为空")
            return

        current = self.head
        result = []
        while True:
            result.append(current.data)
            current = current.next
            if current == self.head:
                break
        print(" <-> ".join(map(str, result)) + " <-> (head)")  # 打印链表内容

2.4 动态数组实现

# ======================动态数组==========================
class DynamicArray:
    def __init__(self):
        """
        初始化一个动态数组。
        """
        self.array = []  # 初始为空的动态数组

    def append(self, value):
        """
        向动态数组的末尾添加一个新元素。
        :param value: 要添加的元素
        """
        self.array.append(value)

    def get(self, index):
        """
        获取动态数组指定索引位置的值。
        :param index: 要获取的索引位置
        :return: 索引位置的值
        :raises IndexError: 如果索引超出范围，则抛出异常
        """
        if 0 <= index < len(self.array):
            return self.array[index]
        else:
            raise IndexError("索引超出范围")

    def delete(self, index):
        """
        删除动态数组指定索引位置的元素。
        :param index: 要删除的索引位置
        :raises IndexError: 如果索引超出范围，则抛出异常
        """
        if 0 <= index < len(self.array):
            self.array.pop(index)
        else:
            raise IndexError("索引超出范围")

    def __repr__(self):
        """
        返回动态数组的字符串表示。
        :return: 动态数组的字符串表示
        """
        return repr(self.array)

2.5 示例使用

# 示例使用
if __name__ == "__main__":
    # 数组示例
    arr = Array(5)  # 创建一个大小为 5 的数组
    arr.set(0, 10)  # 设置索引 0 处的值为 10
    arr.set(1, 20)  # 设置索引 1 处的值为 20
    print("数组:", arr)  # 输出数组的内容
    print("索引 1 处的值:", arr.get(1))  # 查找索引 1 处的值
    arr.delete(1)  # 删除索引 1 处的值
    print("删除后的数组:", arr)  # 输出数组的内容

    # 单链表示例
    sll = SinglyLinkedList()  # 创建一个单链表
    sll.append(1)  # 向链表添加值为 1 的节点
    sll.append(2)  # 向链表添加值为 2 的节点
    sll.append(3)  # 向链表添加值为 3 的节点
    print("单链表:")
    sll.print_list()  # 打印链表的内容
    print("查找值为 2 的节点:", sll.get(2))  # 查找值为 2 的节点
    sll.delete(2)  # 删除值为 2 的节点
    print("删除后的单链表:")
    sll.print_list()  # 打印链表的内容

    # 双向循环链表示例
    dcll = DoublyLinkedList()  # 创建一个双向链表
    dcll.append(10)  # 向链表添加值为 10 的节点
    dcll.append(20)  # 向链表添加值为 20 的节点
    dcll.append(30)  # 向链表添加值为 30 的节点
    print("双向链表:")
    dcll.print_list()  # 打印链表的内容
    print("查找值为 20 的节点:", dcll.get(20))  # 查找值为 20 的节点
    dcll.delete(20)  # 删除值为 20 的节点
    print("删除后的双向链表:")
    dcll.print_list()  # 打印链表的内容

    # 动态数组示例
    da = DynamicArray()  # 创建一个动态数组
    da.append(5)  # 向数组添加值为 5 的元素
    da.append(15)  # 向数组添加值为 15 的元素
    da.append(25)  # 向数组添加值为 25 的元素
    print("动态数组:")
    print(da)  # 打印动态数组的内容
    print("索引 1 处的值:", da.get(1))  # 查找索引 1 处的值
    da.delete(1)  # 删除索引 1 处的值
    print("删除后的动态数组:")
    print(da)  # 打印动态数组的内容

去1:1私密咨询