数组与链表对决：Java 中两种基础数据结构的全面对比

数组与链表对决：Java 中两种基础数据结构的全面对比

• • 1. 核心区别速览
  • 2. 内存结构对比
  • • 2.1 数组：连续内存
    • 2.2 链表：非连续内存
  • 3. 操作效率详解
  • • 3.1 随机访问
    • 3.2 插入和删除
  • 4. Java 中的实现
  • • 4.1 数组的使用
    • 4.2 ArrayList：动态数组
    • 4.3 链表的使用
    • • LinkedList（双向链表）
      • 自定义单向链表
  • 5. 性能测试对比
  • • 5.1 测试代码
    • 5.2 测试结果
  • 6. 实战场景选择
  • • 6.1 决策树
    • 6.2 典型场景推荐
    • 6.3 实际项目中的选择
  • 7. 常见面试追问
  • • Q1：数组和 ArrayList 有什么区别？
    • Q2：LinkedList 和 ArrayList 在实际项目中如何选择？
    • Q3：为什么说 `ArrayList` 的插入不一定是 O(n)？
    • Q4：Java 中为什么没有内置的纯数组的增删方法？
    • Q5：数组和链表哪个更占用内存？
  • 8. 总结

数组和链表是计算机科学中最基础的两种数据结构，也是面试中最高频的问题之一。理解它们的本质区别，是写出高性能代码的基础。

本文从内存结构、操作效率、Java 实现、适用场景四个维度，彻底讲透数组和链表的区别。

1. 核心区别速览

2. 内存结构对比

2.1 数组：连续内存

#mermaid-svg-zuiBujw3rswnyeY8{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-zuiBujw3rswnyeY8 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-zuiBujw3rswnyeY8 .error-icon{fill:#552222;}#mermaid-svg-zuiBujw3rswnyeY8 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zuiBujw3rswnyeY8 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zuiBujw3rswnyeY8 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zuiBujw3rswnyeY8 .marker.cross{stroke:#333333;}#mermaid-svg-zuiBujw3rswnyeY8 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zuiBujw3rswnyeY8 p{margin:0;}#mermaid-svg-zuiBujw3rswnyeY8 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-zuiBujw3rswnyeY8 .cluster-label text{fill:#333;}#mermaid-svg-zuiBujw3rswnyeY8 .cluster-label span{color:#333;}#mermaid-svg-zuiBujw3rswnyeY8 .cluster-label span p{background-color:transparent;}#mermaid-svg-zuiBujw3rswnyeY8 .label text,#mermaid-svg-zuiBujw3rswnyeY8 span{fill:#333;color:#333;}#mermaid-svg-zuiBujw3rswnyeY8 .node rect,#mermaid-svg-zuiBujw3rswnyeY8 .node circle,#mermaid-svg-zuiBujw3rswnyeY8 .node ellipse,#mermaid-svg-zuiBujw3rswnyeY8 .node polygon,#mermaid-svg-zuiBujw3rswnyeY8 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zuiBujw3rswnyeY8 .rough-node .label text,#mermaid-svg-zuiBujw3rswnyeY8 .node .label text,#mermaid-svg-zuiBujw3rswnyeY8 .image-shape .label,#mermaid-svg-zuiBujw3rswnyeY8 .icon-shape .label{text-anchor:middle;}#mermaid-svg-zuiBujw3rswnyeY8 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-zuiBujw3rswnyeY8 .rough-node .label,#mermaid-svg-zuiBujw3rswnyeY8 .node .label,#mermaid-svg-zuiBujw3rswnyeY8 .image-shape .label,#mermaid-svg-zuiBujw3rswnyeY8 .icon-shape .label{text-align:center;}#mermaid-svg-zuiBujw3rswnyeY8 .node.clickable{cursor:pointer;}#mermaid-svg-zuiBujw3rswnyeY8 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-zuiBujw3rswnyeY8 .arrowheadPath{fill:#333333;}#mermaid-svg-zuiBujw3rswnyeY8 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zuiBujw3rswnyeY8 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zuiBujw3rswnyeY8 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-zuiBujw3rswnyeY8 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-zuiBujw3rswnyeY8 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-zuiBujw3rswnyeY8 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-zuiBujw3rswnyeY8 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zuiBujw3rswnyeY8 .cluster text{fill:#333;}#mermaid-svg-zuiBujw3rswnyeY8 .cluster span{color:#333;}#mermaid-svg-zuiBujw3rswnyeY8 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zuiBujw3rswnyeY8 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-zuiBujw3rswnyeY8 rect.text{fill:none;stroke-width:0;}#mermaid-svg-zuiBujw3rswnyeY8 .icon-shape,#mermaid-svg-zuiBujw3rswnyeY8 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-zuiBujw3rswnyeY8 .icon-shape p,#mermaid-svg-zuiBujw3rswnyeY8 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-zuiBujw3rswnyeY8 .icon-shape .label rect,#mermaid-svg-zuiBujw3rswnyeY8 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-zuiBujw3rswnyeY8 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-zuiBujw3rswnyeY8 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-zuiBujw3rswnyeY8 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

地址计算

arr[i] = 起始地址 + i × 元素大小

数组内存布局

0x1000arr[0]

0x1004arr[1]

0x1008arr[2]

0x100Carr[3]

特点：

• 元素在内存中物理连续
• 通过起始地址 + 偏移量 O(1) 访问
• CPU 缓存预读取效率极高

2.2 链表：非连续内存

#mermaid-svg-h5AcynyAnRNhVbza{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-h5AcynyAnRNhVbza .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-h5AcynyAnRNhVbza .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-h5AcynyAnRNhVbza .error-icon{fill:#552222;}#mermaid-svg-h5AcynyAnRNhVbza .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-h5AcynyAnRNhVbza .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-h5AcynyAnRNhVbza .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-h5AcynyAnRNhVbza .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-h5AcynyAnRNhVbza .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-h5AcynyAnRNhVbza .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-h5AcynyAnRNhVbza .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-h5AcynyAnRNhVbza .marker{fill:#333333;stroke:#333333;}#mermaid-svg-h5AcynyAnRNhVbza .marker.cross{stroke:#333333;}#mermaid-svg-h5AcynyAnRNhVbza svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-h5AcynyAnRNhVbza p{margin:0;}#mermaid-svg-h5AcynyAnRNhVbza .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-h5AcynyAnRNhVbza .cluster-label text{fill:#333;}#mermaid-svg-h5AcynyAnRNhVbza .cluster-label span{color:#333;}#mermaid-svg-h5AcynyAnRNhVbza .cluster-label span p{background-color:transparent;}#mermaid-svg-h5AcynyAnRNhVbza .label text,#mermaid-svg-h5AcynyAnRNhVbza span{fill:#333;color:#333;}#mermaid-svg-h5AcynyAnRNhVbza .node rect,#mermaid-svg-h5AcynyAnRNhVbza .node circle,#mermaid-svg-h5AcynyAnRNhVbza .node ellipse,#mermaid-svg-h5AcynyAnRNhVbza .node polygon,#mermaid-svg-h5AcynyAnRNhVbza .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-h5AcynyAnRNhVbza .rough-node .label text,#mermaid-svg-h5AcynyAnRNhVbza .node .label text,#mermaid-svg-h5AcynyAnRNhVbza .image-shape .label,#mermaid-svg-h5AcynyAnRNhVbza .icon-shape .label{text-anchor:middle;}#mermaid-svg-h5AcynyAnRNhVbza .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-h5AcynyAnRNhVbza .rough-node .label,#mermaid-svg-h5AcynyAnRNhVbza .node .label,#mermaid-svg-h5AcynyAnRNhVbza .image-shape .label,#mermaid-svg-h5AcynyAnRNhVbza .icon-shape .label{text-align:center;}#mermaid-svg-h5AcynyAnRNhVbza .node.clickable{cursor:pointer;}#mermaid-svg-h5AcynyAnRNhVbza .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-h5AcynyAnRNhVbza .arrowheadPath{fill:#333333;}#mermaid-svg-h5AcynyAnRNhVbza .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-h5AcynyAnRNhVbza .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-h5AcynyAnRNhVbza .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-h5AcynyAnRNhVbza .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-h5AcynyAnRNhVbza .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-h5AcynyAnRNhVbza .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-h5AcynyAnRNhVbza .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-h5AcynyAnRNhVbza .cluster text{fill:#333;}#mermaid-svg-h5AcynyAnRNhVbza .cluster span{color:#333;}#mermaid-svg-h5AcynyAnRNhVbza div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-h5AcynyAnRNhVbza .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-h5AcynyAnRNhVbza rect.text{fill:none;stroke-width:0;}#mermaid-svg-h5AcynyAnRNhVbza .icon-shape,#mermaid-svg-h5AcynyAnRNhVbza .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-h5AcynyAnRNhVbza .icon-shape p,#mermaid-svg-h5AcynyAnRNhVbza .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-h5AcynyAnRNhVbza .icon-shape .label rect,#mermaid-svg-h5AcynyAnRNhVbza .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-h5AcynyAnRNhVbza .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-h5AcynyAnRNhVbza .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-h5AcynyAnRNhVbza :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

链表内存布局

next

next

节点00×1000

节点10×2048

节点20×3096

值: 10next: 0x2048prev: null

值: 20next: 0x3096prev: 0x1000

值: 30next: nullprev: 0x2048

特点：

• 节点分散在内存各处
• 通过指针（引用）串联
• 每个节点有额外指针开销

3. 操作效率详解

3.1 随机访问

#mermaid-svg-DYApj8Xr6KK4hDsW{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-DYApj8Xr6KK4hDsW .error-icon{fill:#552222;}#mermaid-svg-DYApj8Xr6KK4hDsW .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DYApj8Xr6KK4hDsW .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DYApj8Xr6KK4hDsW .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DYApj8Xr6KK4hDsW .marker.cross{stroke:#333333;}#mermaid-svg-DYApj8Xr6KK4hDsW svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DYApj8Xr6KK4hDsW p{margin:0;}#mermaid-svg-DYApj8Xr6KK4hDsW .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster-label text{fill:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster-label span{color:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster-label span p{background-color:transparent;}#mermaid-svg-DYApj8Xr6KK4hDsW .label text,#mermaid-svg-DYApj8Xr6KK4hDsW span{fill:#333;color:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW .node rect,#mermaid-svg-DYApj8Xr6KK4hDsW .node circle,#mermaid-svg-DYApj8Xr6KK4hDsW .node ellipse,#mermaid-svg-DYApj8Xr6KK4hDsW .node polygon,#mermaid-svg-DYApj8Xr6KK4hDsW .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DYApj8Xr6KK4hDsW .rough-node .label text,#mermaid-svg-DYApj8Xr6KK4hDsW .node .label text,#mermaid-svg-DYApj8Xr6KK4hDsW .image-shape .label,#mermaid-svg-DYApj8Xr6KK4hDsW .icon-shape .label{text-anchor:middle;}#mermaid-svg-DYApj8Xr6KK4hDsW .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-DYApj8Xr6KK4hDsW .rough-node .label,#mermaid-svg-DYApj8Xr6KK4hDsW .node .label,#mermaid-svg-DYApj8Xr6KK4hDsW .image-shape .label,#mermaid-svg-DYApj8Xr6KK4hDsW .icon-shape .label{text-align:center;}#mermaid-svg-DYApj8Xr6KK4hDsW .node.clickable{cursor:pointer;}#mermaid-svg-DYApj8Xr6KK4hDsW .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-DYApj8Xr6KK4hDsW .arrowheadPath{fill:#333333;}#mermaid-svg-DYApj8Xr6KK4hDsW .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DYApj8Xr6KK4hDsW .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DYApj8Xr6KK4hDsW .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-DYApj8Xr6KK4hDsW .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-DYApj8Xr6KK4hDsW .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-DYApj8Xr6KK4hDsW .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster text{fill:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW .cluster span{color:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DYApj8Xr6KK4hDsW .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-DYApj8Xr6KK4hDsW rect.text{fill:none;stroke-width:0;}#mermaid-svg-DYApj8Xr6KK4hDsW .icon-shape,#mermaid-svg-DYApj8Xr6KK4hDsW .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-DYApj8Xr6KK4hDsW .icon-shape p,#mermaid-svg-DYApj8Xr6KK4hDsW .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-DYApj8Xr6KK4hDsW .icon-shape .label rect,#mermaid-svg-DYApj8Xr6KK4hDsW .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-DYApj8Xr6KK4hDsW .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-DYApj8Xr6KK4hDsW .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-DYApj8Xr6KK4hDsW :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

链表访问

get(5)

从头节点开始

节点0 → 节点1 → …

遍历 5 次

❌ O(n)

数组访问

arr[5]

计算: 0x1000 + 5×4

直接读取 0x1014

✅ O(1)

3.2 插入和删除

#mermaid-svg-EnOCZRRCQQk0I2fK{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-EnOCZRRCQQk0I2fK .error-icon{fill:#552222;}#mermaid-svg-EnOCZRRCQQk0I2fK .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EnOCZRRCQQk0I2fK .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EnOCZRRCQQk0I2fK .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EnOCZRRCQQk0I2fK .marker.cross{stroke:#333333;}#mermaid-svg-EnOCZRRCQQk0I2fK svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EnOCZRRCQQk0I2fK p{margin:0;}#mermaid-svg-EnOCZRRCQQk0I2fK .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster-label text{fill:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster-label span{color:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster-label span p{background-color:transparent;}#mermaid-svg-EnOCZRRCQQk0I2fK .label text,#mermaid-svg-EnOCZRRCQQk0I2fK span{fill:#333;color:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK .node rect,#mermaid-svg-EnOCZRRCQQk0I2fK .node circle,#mermaid-svg-EnOCZRRCQQk0I2fK .node ellipse,#mermaid-svg-EnOCZRRCQQk0I2fK .node polygon,#mermaid-svg-EnOCZRRCQQk0I2fK .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EnOCZRRCQQk0I2fK .rough-node .label text,#mermaid-svg-EnOCZRRCQQk0I2fK .node .label text,#mermaid-svg-EnOCZRRCQQk0I2fK .image-shape .label,#mermaid-svg-EnOCZRRCQQk0I2fK .icon-shape .label{text-anchor:middle;}#mermaid-svg-EnOCZRRCQQk0I2fK .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-EnOCZRRCQQk0I2fK .rough-node .label,#mermaid-svg-EnOCZRRCQQk0I2fK .node .label,#mermaid-svg-EnOCZRRCQQk0I2fK .image-shape .label,#mermaid-svg-EnOCZRRCQQk0I2fK .icon-shape .label{text-align:center;}#mermaid-svg-EnOCZRRCQQk0I2fK .node.clickable{cursor:pointer;}#mermaid-svg-EnOCZRRCQQk0I2fK .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-EnOCZRRCQQk0I2fK .arrowheadPath{fill:#333333;}#mermaid-svg-EnOCZRRCQQk0I2fK .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EnOCZRRCQQk0I2fK .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EnOCZRRCQQk0I2fK .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-EnOCZRRCQQk0I2fK .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-EnOCZRRCQQk0I2fK .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-EnOCZRRCQQk0I2fK .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster text{fill:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK .cluster span{color:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EnOCZRRCQQk0I2fK .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-EnOCZRRCQQk0I2fK rect.text{fill:none;stroke-width:0;}#mermaid-svg-EnOCZRRCQQk0I2fK .icon-shape,#mermaid-svg-EnOCZRRCQQk0I2fK .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-EnOCZRRCQQk0I2fK .icon-shape p,#mermaid-svg-EnOCZRRCQQk0I2fK .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-EnOCZRRCQQk0I2fK .icon-shape .label rect,#mermaid-svg-EnOCZRRCQQk0I2fK .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-EnOCZRRCQQk0I2fK .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-EnOCZRRCQQk0I2fK .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-EnOCZRRCQQk0I2fK :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

在节点b后插入x

原链表: a → b → c

创建节点x

x.next = b.next

b.next = x

✅ O(1) 指针修改

在索引2插入

原数组: a b c d e

在索引2插入x

c d e 各后移一位

新数组: a b x c d e

❌ O(n) 元素移动

对比表格：

4. Java 中的实现

4.1 数组的使用

// 静态初始化
int[] arr1 = {1, 2, 3, 4, 5};

// 动态初始化
int[] arr2 = new int[10]; // 默认值为 0
arr2[0] = 100;

// 多维数组
int[][] matrix = new int[3][4];

// 遍历
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}

// 增强 for
for (int num : arr1) {
System.out.println(num);
}

// 数组扩容（需复制）
int[] oldArr = {1, 2, 3};
int[] newArr = Arrays.copyOf(oldArr, oldArr.length * 2);

4.2 ArrayList：动态数组

// 底层是数组，动态扩容
List<String> list = new ArrayList<>();
list.add("a"); // 尾部添加 O(1)
list.add(0, "b"); // 头部添加 O(n)
String s = list.get(5); // 随机访问 O(1)
list.remove(2); // 删除 O(n)

ArrayList 扩容机制：

// 默认容量 10，每次扩容 1.5 倍
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity);
}

4.3 链表的使用

LinkedList（双向链表）

LinkedList<String> list = new LinkedList<>();
list.add("a"); // 尾部添加 O(1)
list.addFirst("b"); // 头部添加 O(1)
list.addLast("c"); // 尾部添加 O(1)
String first = list.getFirst(); // O(1)
String last = list.getLast(); // O(1)
String s = list.get(5); // 需要遍历 O(n)
list.removeFirst(); // O(1)
list.removeLast(); // O(1)

自定义单向链表

public class SinglyLinkedList<E> {

private static class Node<E> {
E data;
Node<E> next;
Node(E data) { this.data = data; }
}

private Node<E> head;
private int size;

// 头部插入
public void addFirst(E e) {
Node<E> newNode = new Node<>(e);
newNode.next = head;
head = newNode;
size++;
}

// 尾部插入
public void addLast(E e) {
Node<E> newNode = new Node<>(e);
if (head == null) {
head = newNode;
} else {
Node<E> cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
size++;
}

// 删除指定值
public boolean remove(E e) {
if (head == null) return false;
if (head.data.equals(e)) {
head = head.next;
size—;
return true;
}
Node<E> cur = head;
while (cur.next != null && !cur.next.data.equals(e)) {
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
size—;
return true;
}
return false;
}
}

5. 性能测试对比

5.1 测试代码

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ArrayVsListBenchmark {

private static final int SIZE = 10000;
private static final int[] array = new int[SIZE];
private static final List<Integer> arrayList = new ArrayList<>();
private static final List<Integer> linkedList = new LinkedList<>();

static {
for (int i = 0; i < SIZE; i++) {
array[i] = i;
arrayList.add(i);
linkedList.add(i);
}
}

@Benchmark
public int arrayGet() {
return array[SIZE / 2];
}

@Benchmark
public int arrayListGet() {
return arrayList.get(SIZE / 2);
}

@Benchmark
public int linkedListGet() {
return linkedList.get(SIZE / 2);
}

@Benchmark
public void arrayListInsertHead() {
arrayList.add(0, –1);
}

@Benchmark
public void linkedListInsertHead() {
linkedList.addFirst(–1);
}
}

5.2 测试结果

6. 实战场景选择

6.1 决策树

#mermaid-svg-gaB6KowUajXK35EQ{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-gaB6KowUajXK35EQ .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-gaB6KowUajXK35EQ .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-gaB6KowUajXK35EQ .error-icon{fill:#552222;}#mermaid-svg-gaB6KowUajXK35EQ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-gaB6KowUajXK35EQ .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-gaB6KowUajXK35EQ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-gaB6KowUajXK35EQ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-gaB6KowUajXK35EQ .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-gaB6KowUajXK35EQ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-gaB6KowUajXK35EQ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-gaB6KowUajXK35EQ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-gaB6KowUajXK35EQ .marker.cross{stroke:#333333;}#mermaid-svg-gaB6KowUajXK35EQ svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-gaB6KowUajXK35EQ p{margin:0;}#mermaid-svg-gaB6KowUajXK35EQ .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-gaB6KowUajXK35EQ .cluster-label text{fill:#333;}#mermaid-svg-gaB6KowUajXK35EQ .cluster-label span{color:#333;}#mermaid-svg-gaB6KowUajXK35EQ .cluster-label span p{background-color:transparent;}#mermaid-svg-gaB6KowUajXK35EQ .label text,#mermaid-svg-gaB6KowUajXK35EQ span{fill:#333;color:#333;}#mermaid-svg-gaB6KowUajXK35EQ .node rect,#mermaid-svg-gaB6KowUajXK35EQ .node circle,#mermaid-svg-gaB6KowUajXK35EQ .node ellipse,#mermaid-svg-gaB6KowUajXK35EQ .node polygon,#mermaid-svg-gaB6KowUajXK35EQ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-gaB6KowUajXK35EQ .rough-node .label text,#mermaid-svg-gaB6KowUajXK35EQ .node .label text,#mermaid-svg-gaB6KowUajXK35EQ .image-shape .label,#mermaid-svg-gaB6KowUajXK35EQ .icon-shape .label{text-anchor:middle;}#mermaid-svg-gaB6KowUajXK35EQ .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-gaB6KowUajXK35EQ .rough-node .label,#mermaid-svg-gaB6KowUajXK35EQ .node .label,#mermaid-svg-gaB6KowUajXK35EQ .image-shape .label,#mermaid-svg-gaB6KowUajXK35EQ .icon-shape .label{text-align:center;}#mermaid-svg-gaB6KowUajXK35EQ .node.clickable{cursor:pointer;}#mermaid-svg-gaB6KowUajXK35EQ .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-gaB6KowUajXK35EQ .arrowheadPath{fill:#333333;}#mermaid-svg-gaB6KowUajXK35EQ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-gaB6KowUajXK35EQ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-gaB6KowUajXK35EQ .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-gaB6KowUajXK35EQ .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-gaB6KowUajXK35EQ .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-gaB6KowUajXK35EQ .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-gaB6KowUajXK35EQ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-gaB6KowUajXK35EQ .cluster text{fill:#333;}#mermaid-svg-gaB6KowUajXK35EQ .cluster span{color:#333;}#mermaid-svg-gaB6KowUajXK35EQ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-gaB6KowUajXK35EQ .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-gaB6KowUajXK35EQ rect.text{fill:none;stroke-width:0;}#mermaid-svg-gaB6KowUajXK35EQ .icon-shape,#mermaid-svg-gaB6KowUajXK35EQ .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-gaB6KowUajXK35EQ .icon-shape p,#mermaid-svg-gaB6KowUajXK35EQ .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-gaB6KowUajXK35EQ .icon-shape .label rect,#mermaid-svg-gaB6KowUajXK35EQ .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-gaB6KowUajXK35EQ .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-gaB6KowUajXK35EQ .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-gaB6KowUajXK35EQ :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

选择数据结构

需要随机访问吗?

数组 / ArrayList

操作主要在两端?

LinkedList / ArrayDeque

需要频繁插入删除?

LinkedList（需已知位置）

ArrayList（查找快，修改少）

访问频繁的场景

队列/栈场景

频繁增删且遍历少

通用场景

6.2 典型场景推荐

6.3 实际项目中的选择

// ❌ 不推荐：LinkedList 用于频繁随机访问
List<Integer> list = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
int value = list.get(i); // O(n)，总复杂度 O(n²)
}

// ✅ 推荐：用迭代器
for (int value : list) { // O(n)
// 处理
}

// ✅ 推荐：需要随机访问用 ArrayList
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < arrayList.size(); i++) {
int value = arrayList.get(i); // O(1)
}

// ✅ 推荐：两端操作用 ArrayDeque（比 LinkedList 更快）
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.pollFirst();

7. 常见面试追问

Q1：数组和 ArrayList 有什么区别？

Q2：LinkedList 和 ArrayList 在实际项目中如何选择？

选择 ArrayList 的场景（90% 的情况）：

• 绝大多数 Java 项目
• 随机读多、增删少
• 内存敏感（LinkedList 内存开销大）

选择 LinkedList 的场景（< 10%）：

• 频繁在头部插入/删除
• 实现队列/双端队列（但 ArrayDeque 通常更好）
• 不需要随机访问，且元素数量极大

Q3：为什么说 ArrayList 的插入不一定是 O(n)？

尾部插入且容量充足时是 O(1)，触发扩容时需要复制数组，摊销后仍接近 O(1)。

Q4：Java 中为什么没有内置的纯数组的增删方法？

因为数组长度固定。如果想增删，必须创建新数组并复制——这正是 ArrayList 做的事。

Q5：数组和链表哪个更占用内存？

链表更占内存。一个 LinkedList 节点在 64 位 JVM 中约占用 24 字节（对象头 + data + prev + next），而数组只需连续内存存储数据。

8. 总结

一句话总结：数组是连续内存的「空间换时间」（预分配连续空间换取 O(1) 访问），链表是分散内存的「时间换空间」（用指针开销换取 O(1) 增删）——Java 开发中 90% 的场景 ArrayList 是最佳选择。

欢迎在评论区分享你在项目中关于数组和链表的选择经验！