资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

深入理解数组与链表：数据结构的基础与进阶

创作时间:

作者:

@小白创作中心

深入理解数组与链表：数据结构的基础与进阶

引用

CSDN

https://blog.csdn.net/2301_78858041/article/details/145710044

在编程世界中，数据结构是程序性能和功能的核心决定因素之一。数组和链表作为最基础且最重要的数据结构，广泛应用于各种场景中。本文将详细介绍数组、单向链表、双向链表和循环链表的基本概念、实现方法、优缺点及应用场景。通过本文的学习，你将能够更好地理解这些数据结构的特点，并在实际开发中做出更明智的选择。

数组（Array）

基本概念

数组是一种线性数据结构，由一组相同类型的元素组成，每个元素通过索引访问。数组在内存中是连续存储的，因此支持高效的随机访问。

实现

在 Java 中，数组可以通过以下方式创建：

int[] arr = new int[5];  // 创建一个长度为 5 的整数数组
arr[0] = 10;  // 初始化第一个元素

特点

优点：
随机访问时间复杂度为 O(1)。
内存连续，适合缓存友好型操作。
缺点：
插入和删除操作时间复杂度为 O(n)。
长度固定，无法动态扩展。

适用场景

需要频繁随机访问元素的场景。
数据量较小且不需要频繁插入/删除操作的场景。

单向链表（Singly Linked List）

基本概念

单向链表是一种由节点组成的线性数据结构，每个节点包含一个数据域和一个指向下一个节点的指针。

实现

在 Java 中，单向链表可以通过以下方式实现：

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;

    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
    }

    void display() {
        Node currentNode = head;
        while (currentNode != null) {
            System.out.print(currentNode.data + " -> ");
            currentNode = currentNode.next;
        }
        System.out.println("null");
    }
}

特点

优点：
插入和删除操作时间复杂度为 O(1)（尾部插入）。
动态扩展，无需预先分配内存。
缺点：
随机访问时间复杂度为 O(n)。
需要额外的指针空间。

适用场景

需要频繁插入和删除操作的场景。
内存有限且需要动态扩展的场景。

双向链表（Doubly Linked List）

基本概念

双向链表与单向链表类似，但每个节点包含两个指针：一个指向下一个节点，另一个指向前一个节点。

实现

在 Java 中，双向链表可以通过以下方式实现：

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    Node head;
    Node tail;

    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    void display() {
        Node currentNode = head;
        while (currentNode != null) {
            System.out.print(currentNode.data + " <-> ");
            currentNode = currentNode.next;
        }
        System.out.println("null");
    }
}

特点

优点：
支持双向遍历。
插入和删除操作时间复杂度为 O(1)（尾部插入）。
缺点：
内存开销较大（每个节点需要两个指针）。
实现复杂度较高。

适用场景

需要双向遍历的场景。
需要频繁插入和删除操作的场景。

循环链表（Circular Linked List）

基本概念

循环链表是一种特殊的链表，其最后一个节点的指针指向头节点，形成一个环形结构。

实现

在 Java 中，循环链表可以通过以下方式实现：

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CircularLinkedList {
    Node head;

    void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != head) {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
        newNode.next = head;
    }

    void display() {
        Node currentNode = head;
        do {
            System.out.print(currentNode.data + " -> ");
            currentNode = currentNode.next;
        } while (currentNode != head);
        System.out.println("...");
    }
}

特点

优点：
便于循环遍历。
在某些场景下可以简化代码逻辑。
缺点：
实现复杂度较高。
需要额外处理边界条件。

适用场景

需要循环遍历的场景。
特定领域应用（如音乐播放器的播放列表）。

链表与数组的比较

特性	数组	链表
内存分配	连续内存	分散内存
随机访问	O(1)	O(n)
插入/删除	O(n)	O(1)（尾部插入）
动态扩展	不支持	支持

高级主题：动态数组与链表的结合

在实际应用中，动态数组（如 Java 的 ArrayList）和链表（如 Java 的 LinkedList）各有优劣。动态数组通过内部实现优化（如预分配内存）弥补了固定长度的缺点，而链表则通过牺牲内存效率换取更高的插入/删除性能。

import java.util.ArrayList;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 测试插入性能
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
        }
        System.out.println("ArrayList 插入时间：" + (System.currentTimeMillis() - startTime) + " ms");

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            linkedList.add(i);
        }
        System.out.println("LinkedList 插入时间：" + (System.currentTimeMillis() - startTime) + " ms");
    }
}