数组和链表

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 数组实现 (Array)

// ======================数组==========================
class Array {
    private int size;          // 数组的大小
    private Integer[] array;   // 数组本身

    // 构造函数：初始化数组
    public Array(int size) {
        this.size = size;
        this.array = new Integer[size];  // 初始化一个大小为 `size` 的数组，元素均为 null
    }

    // 设置数组指定索引位置的值
    public void set(int index, int value) throws IndexOutOfBoundsException {
        if (index >= 0 && index < size) {
            array[index] = value;
        } else {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
    }

    // 获取数组指定索引位置的值
    public int get(int index) throws IndexOutOfBoundsException {
        if (index >= 0 && index < size) {
            return array[index];
        } else {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
    }

    // 删除数组指定索引位置的值，并将该位置设置为 null
    public void delete(int index) throws IndexOutOfBoundsException {
        if (index >= 0 && index < size) {
            array[index] = null;
        } else {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
    }

    // 返回数组的字符串表示
    @Override
    public String toString() {
        return java.util.Arrays.toString(array);
    }
}

2.2 单链表实现 (Singly Linked List)

// ======================单链表==========================
class Node {
    int data;      // 节点的数据
    Node next;     // 指向下一个节点的指针

    // 构造函数：创建节点
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    private Node head;  // 链表的头节点

    // 构造函数：初始化空链表
    public SinglyLinkedList() {
        this.head = null;
    }

    // 向链表的末尾添加一个新节点
    public void append(int data) {
        Node newNode = new Node(data);  // 创建新节点
        if (head == null) {
            head = newNode;  // 如果链表为空，新节点成为头节点
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;  // 遍历到链表的最后一个节点
            }
            last.next = newNode;  // 将新节点链接到链表的末尾
        }
    }

    // 删除链表中第一个匹配指定数据的节点
    public void delete(int data) {
        Node current = head;
        if (current == null) return;

        // 如果要删除的是头节点
        if (current.data == data) {
            head = current.next;
            return;
        }

        Node prev = null;
        while (current != null && current.data != data) {
            prev = current;
            current = current.next;
        }

        // 如果找到要删除的节点
        if (current != null) {
            prev.next = current.next;  // 跳过要删除的节点
        }
    }

    // 查找链表中第一个匹配指定数据的节点，并返回节点数据
    public Integer get(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return current.data;
            }
            current = current.next;
        }
        return null;  // 未找到数据
    }

    // 打印链表的所有节点
    public void printList() {
        Node current = head;
        if (current == null) {
            System.out.println("链表为空");
            return;
        }
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.data).append(" -> ");
            current = current.next;
        }
        sb.append("None");
        System.out.println(sb.toString());
    }
}

2.3 双向链表实现 (Doubly Linked List)

// ======================双链表==========================
class DoublyNode {
    int data;        // 节点的数据
    DoublyNode next; // 指向下一个节点的指针
    DoublyNode prev; // 指向前一个节点的指针

    // 构造函数：创建双向节点
    public DoublyNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    private DoublyNode head; // 链表的头节点

    // 构造函数：初始化空双向链表
    public DoublyLinkedList() {
        this.head = null;
    }

    // 向双向链表的末尾添加一个新节点
    public void append(int data) {
        DoublyNode newNode = new DoublyNode(data);  // 创建新节点
        if (head == null) {
            head = newNode;  // 如果链表为空，新节点成为头节点
            head.prev = head;  // 指向自己
            head.next = head;  // 指向自己
        } else {
            DoublyNode last = head.prev;  // 获取链表的最后一个节点
            last.next = newNode;
            newNode.prev = last;
            newNode.next = head;
            head.prev = newNode;
        }
    }

    // 删除双向链表中第一个匹配指定数据的节点
    public void delete(int data) {
        if (head == null) return;

        DoublyNode current = head;
        while (true) {
            if (current.data == data) {
                if (current == head) {  // 删除头节点
                    if (current.next == current) {  // 只有一个节点
                        head = null;
                    } else {
                        head = current.next;
                        head.prev = current.prev;
                        current.prev.next = head;
                    }
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                return;
            }
            current = current.next;
            if (current == head) break;  // 遍历一圈后返回
        }
    }

    // 查找双向链表中第一个匹配指定数据的节点，并返回节点数据
    public Integer get(int data) {
        if (head == null) return null;

        DoublyNode current = head;
        while (true) {
            if (current.data == data) {
                return current.data;
            }
            current = current.next;
            if (current == head) break;
        }
        return null;
    }

    // 打印双向链表的所有节点
    public void printList() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }

        DoublyNode current = head;
        StringBuilder sb = new StringBuilder();
        while (true) {
            sb.append(current.data).append(" <-> ");
            current = current.next;
            if (current == head) break;
        }
        sb.append("(head)"); // 指示循环链表的头节点
        System.out.println(sb.toString());
    }
}

2.4 动态数组实现 (Dynamic Array)

// ======================动态数组==========================
import java.util.ArrayList;

class DynamicArray {
    private ArrayList<Integer> array;

    // 构造函数：初始化空的动态数组
    public DynamicArray() {
        this.array = new ArrayList<>();
    }

    // 向动态数组的末尾添加一个新元素
    public void append(int value) {
        array.add(value);
    }

    // 获取动态数组指定索引位置的值
    public int get(int index) throws IndexOutOfBoundsException {
        if (index >= 0 && index < array.size()) {
            return array.get(index);
        } else {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
    }

    // 删除动态数组指定索引位置的元素
    public void delete(int index) throws IndexOutOfBoundsException {
        if (index >= 0 && index < array.size()) {
            array.remove(index);
        } else {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
    }

    // 返回动态数组的字符串表示
    @Override
    public String toString() {
        return array.toString();
    }
}

2.5 示例使用 (Main)

public class Main {
    public static void main(String[] args) {
        // 数组示例
        Array arr = new Array(5);
        arr.set(0, 10);
        arr.set(1, 20);
        System.out.println("数组: " + arr);
        System.out.println("索引 1 处的值: " + arr.get(1));
        arr.delete(1);
        System.out.println("删除后的数组: " + arr);

        // 单链表示例
        SinglyLinkedList sll = new SinglyLinkedList();
        sll.append(1);
        sll.append(2);
        sll.append(3);
        System.out.println("单链表:");
        sll.printList();
        System.out.println("查找值为 2 的节点: " + sll.get(2));
        sll.delete(2);
        System.out.println("删除后的单链表:");
        sll.printList();

        // 双向链表示例
        DoublyLinkedList dcll = new DoublyLinkedList();
        dcll.append(10);
        dcll.append(20);
        dcll.append(30);
        System.out.println("双向链表:");
        dcll.printList();
        System.out.println("查找值为 20 的节点: " + dcll.get(20));
        dcll.delete(20);
        System.out.println("删除后的双向链表:");
        dcll.printList();

        // 动态数组示例
        DynamicArray da = new DynamicArray();
        da.append(5);
        da.append(15);
        da.append(25);
        System.out.println("动态数组: " + da);
        System.out.println("索引 1 处的值: " + da.get(1));
        da.delete(1);
        System.out.println("删除后的动态数组: " + da);
    }
}

去1:1私密咨询