本文共 1480 字，大约阅读时间需要 4 分钟。

线性数据结构之数组与链表

在线性数据结构中，数组和链表是最常见的两种类型，它们在数据存储和操作上各有优劣之处。

数组

数组的核心特点是固定长度，存储空间必须是连续的，这使得数组在内存中占用较为紧凑。然而，数组的长度无法随意更改，这也是数组性能优越的原因之一。

延伸思考：为什么数组不能直接向后扩容？这是因为操作系统分配内存时通常会分配一个较大的连续块，当数组长度不足时，系统需要通过重新分配一个更大的存储空间，并将原数组数据复制到新位置。这种操作虽然效率不高，但由于被优化了，作为开发者，我们不需要手动管理数组长度。

数组的优点

数组的缺点

链表

与数组不同，链表以动态链接的方式存储数据，其节点通常包含数据值和指向下一个节点的引用。链表的关键特点是柔性，高度灵活。

链表的特点

链表的优点

链表的缺点

链表的使用场景

链表特别适合需要频繁插入、删除操作且数据规模不大或无法预先确定大小的场景。

链表操作示例

// 创建链表节点function Node(value) {    this.value = value;    this.next = null;}// 例子:var a = new Node(1);var b = new Node(2);var c = new Node(3);var d = new Node(4);a.next = b;b.next = c;c.next = d;// 遍历链表function loopLink(root) {    var temp = root;    while (temp != null) {        console.log(temp.value);        temp = temp.next;    }}// 递归遍历function loopLink1(root) {    if (root == null) {        return;    }    console.log(root.value);    loopLink1(root.next);}// 链表逆置function nizhi(root) {    if (root.next == null) {        return root;    }    var lastNode = nizhi(root.next);    root.next = null;    // 上结点的前一个指向当前上结点的前一个    if (root.next != null) {        root.lastNode = root;    }    return lastNode;}

链表在实际应用中的表现取决于具体需求，两者各有优劣，选择时需要综合考虑数据规模和操作频率。

转载地址：http://hzjhz.baihongyu.com/