数组和链表在数据结构上的区别

基本定义

• 数组：数组是一种线性数据结构，由相同类型的元素按顺序组成，在内存中是连续存储的。数组中的每个元素可以通过索引（下标）直接访问。
• 链表：链表也是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表在内存中是非连续存储的。

内存存储方式

• 数组：

  • 在内存中占据一块连续的存储空间
  • 元素紧密排列，每个元素占用相同的内存空间
  • 可以通过首地址和索引计算出任意元素的内存地址

• 链表：

  • 在内存中是离散存储的
  • 每个节点（包含数据和指针）可以分布在内存的任意位置
  • 节点之间通过指针相互连接

时间复杂度对比

空间复杂度

• 数组：

  • 存储密度高，只需要存储元素本身
  • 可能会有空间浪费（如预分配的空间未被使用）

• 链表：

  • 存储密度较低，每个节点需要额外存储指针信息
  • 空间利用更灵活，按需分配

优缺点对比

数组的优点

1. 随机访问高效：通过索引可以直接访问任意元素，时间复杂度为O(1)
2. 内存局部性好：由于元素连续存储，有利于CPU缓存
3. 空间效率高：不需要额外的指针空间

数组的缺点

1. 大小固定：静态数组在创建时大小固定，动态数组扩容需要复制所有元素
2. 插入和删除效率低：在中间位置插入或删除元素需要移动大量元素
3. 内存利用率可能不高：预分配的空间可能未被充分利用

链表的优点

1. 动态大小：可以灵活地增加或减少元素
2. 插入和删除高效：在已知位置插入或删除元素的时间复杂度为O(1)
3. 内存利用灵活：按需分配，不会浪费空间

链表的缺点

1. 随机访问低效：访问第i个元素需要从头遍历，时间复杂度为O(n)
2. 额外空间开销：每个节点需要存储指针信息
3. 缓存不友好：节点在内存中不连续，可能导致缓存命中率低

应用场景

数组适合的场景

1. 需要频繁随机访问：如二分查找、快速排序等算法
2. 元素数量固定：如存储一周的天数、矩阵运算等
3. 需要内存局部性：如处理大量连续数据的多媒体应用

链表适合的场景

1. 频繁插入和删除：如实现队列、栈等数据结构
2. 元素数量不确定：如动态增长的列表
3. 内存碎片化严重：当没有足够大的连续内存空间时

代码示例

数组示例（JavaScript）

// 创建数组
let array = [1, 2, 3, 4, 5];

// 访问元素 - O(1)
console.log(array[2]); // 输出: 3

// 在末尾添加元素 - O(1)
array.push(6); // [1, 2, 3, 4, 5, 6]

// 在中间插入元素 - O(n)
array.splice(2, 0, 10); // [1, 2, 10, 3, 4, 5, 6]

// 删除元素 - O(n)
array.splice(3, 1); // [1, 2, 10, 4, 5, 6]

链表示例（JavaScript）

// 链表节点类
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 链表类
class LinkedList {
  constructor() {
    this.head = null;
  }
  
  // 在头部添加节点 - O(1)
  addAtHead(val) {
    this.head = new ListNode(val, this.head);
  }
  
  // 在尾部添加节点 - O(n)
  addAtTail(val) {
    if (!this.head) {
      this.head = new ListNode(val);
      return;
    }
    
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = new ListNode(val);
  }
  
  // 查找节点 - O(n)
  find(val) {
    let current = this.head;
    while (current) {
      if (current.val === val) {
        return current;
      }
      current = current.next;
    }
    return null;
  }
  
  // 删除节点 - O(n)
  delete(val) {
    if (!this.head) return;
    
    if (this.head.val === val) {
      this.head = this.head.next;
      return;
    }
    
    let current = this.head;
    while (current.next) {
      if (current.next.val === val) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }
}

// 使用链表
let list = new LinkedList();
list.addAtHead(1);
list.addAtTail(2);
list.addAtTail(3);
list.addAtHead(0);

可视化表示

总结

数组和链表是两种基础的线性数据结构，它们在内存存储方式、访问效率、插入删除操作等方面有显著差异。数组适合需要频繁随机访问的场景，而链表适合需要频繁插入和删除的场景。在实际开发中，应根据具体需求选择合适的数据结构。

参考资源

1. MDN Web Docs - Array: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
2. GeeksforGeeks - Array vs Linked List: https://www.geeksforgeeks.org/array-vs-linked-list/
3. 《算法导论》- 第10章：基本数据结构
4. 《JavaScript数据结构与算法》- 第3章：数组、第5章：链表