数据结构面试常见问题：数组和链表的区别是什么？

桃扇骨 2024-05-01 05:03 10阅读 0赞

### 数组 ###

![b228d078f4584d04af8e088049d7a889.png][]

在编程的世界里，数组无疑是最基础的数据结构之一，它像一排整齐的房子，每个房子都有自己的门牌号，我们可以通过这个门牌号直接找到这个房子，无需从头至尾的逐一查找。这个门牌号，就是我们所说的索引，而房子则代表了数组中的每一个元素。

public class OneMoreClass {
        
        public static void main(String[] args){
        
            int[] array = new int[5];
            for(int i=0; i<5; i++){
        
                array[i] = i;
            }
            System.out.println(array[2]); //输出2
        }
    }

上述的Java代码示例中，我们创建了一个长度为5的整型数组`array`，并且使用循环语句，将数组的索引值赋给对应的元素。当我们需要访问数组中的某个元素时，只需要通过索引即可直接访问，如`array[2]`，就可以直接访问到元素2。

但是，数组的优点同时也是它的缺点。因为数组元素在内存中是连续存储的，所以当我们需要在数组中插入或者删除元素时，就需要移动大量的元素，这无疑会消耗大量的时间和计算资源。这个问题，也许可以通过另一种数据结构——链表来解决。

### 链表 ###

接着我们来谈谈链表。链表，这个看似普通的名字，却蕴含着深深的智慧。它和数组一样，是一种线性的数据结构，但是它的存储方式却与数组大相径庭。如果说数组是一座严谨的大厦，每个元素都有固定的位置，那么链表就像是一条自由的河流，每个元素都像是水流中的一滴水，它们并不在乎自己的位置，只在乎与前后的关系。

![6f6f4159d61d41e29eddfaa4fe6a681b.png][]

在Java中，我们可以使用内部类来表示链表中的节点，每个节点包含元素值和指向下一个节点的指针。如下是一个简单的链表节点的定义：

public class Node {
        
            int val;
            Node next;
    
            Node(int val) {
        
                this.val = val;
            }
    }

在这个定义中，`val`表示节点的元素值，`next`是指向下一个节点的指针。链表的节点是独立的，它们不需要在内存中连续存储，只需要通过`next`指针与其他节点相连即可。这种存储方式带来的好处是，当我们需要插入或删除节点时，只需要改变相应节点的指针，而不需要像数组那样移动大量的元素。

然而，链表的这种存储方式也有它的缺点，那就是无法实现数组那样的随机访问。如果我们需要访问链表中的某个元素，就需要从头节点开始，逐个节点进行访问，这无疑会降低访问的效率。那么，如何克服这个缺点，或者说，如何在实际应用中避免这个问题呢？这就需要我们去理解数组和链表在操作上的主要差异了。

### 数组和链表的操作差异 ###

在理解了数组和链表的基本概念后，我们来看看它们在操作上的主要差异。首先，我们来看看数组。由于数组是连续的内存空间，所以在访问元素时，可以直接通过元素的索引进行访问，速度非常快。比如，我们有一个名为OneMore的数组，其元素依次为1,2,3,4,5，我们想要访问第四个元素，只需要`OneMore[3]`就可以直接得到结果4，这就是数组访问元素的便捷性。但是，如果我们需要在OneMore数组中插入或删除元素，就需要移动大量的元素，这时候效率就会显得比较低。

而链表则正好相反，由于每个元素都是独立的节点，所以在插入或删除元素时，只需要改变相应节点的指针即可，效率非常高。比如，我们有一个名为OneMore的链表，其元素依次为1,2,3,4,5，如果我们需要在2和3之间插入一个元素6，只需要将2的指针指向6，6的指针指向3，就完成了元素的插入，这就是链表插入元素的高效性。但是，如果我们需要访问OneMore链表中的某个元素，就需要从头节点开始，逐个节点进行访问，这时候效率就会显得比较低。

理解了数组和链表在操作上的差异后，我们就可以根据实际需要，选择使用数组还是链表。接下来，我们将探讨数组和链表各自的适用场景。

### 数组和链表的适用场景 ###

正如我们所见，数组和链表各有其优点和缺点，选择使用哪一种，完全取决于我们的需求。现在，让我们来深入探讨一下数组和链表的适用场景。

假设你正在为一个名为"OneMore"的项目编写代码，该项目需要频繁地访问元素。在这种情况下，数组会是你的最佳选择。因为数组的元素在内存中是连续存储的，所以你可以直接通过索引来访问任何元素，而无需从头开始遍历。这使得数组在访问元素时的速度非常快，可以大大提高"OneMore"项目的效率。

然而，如果"OneMore"项目需要频繁地插入和删除元素，那么链表可能会是更好的选择。链表的每个元素都是独立的节点，这些节点通过指针相连。当你需要插入或删除一个元素时，只需要改变相应节点的指针，而无需像数组那样移动大量的元素。这使得链表在插入和删除元素时的速度非常快，可以大大提高"OneMore"项目的效率。

总的来说，数组和链表各有其适用的场景，选择使用哪一种，取决于你的具体需求。如果你需要频繁访问元素，那么数组可能会是更好的选择。如果你需要频繁插入和删除元素，那么链表可能会是更好的选择。

[b228d078f4584d04af8e088049d7a889.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/d442409a1c1f47c18f4004645f7c04e9.png
[6f6f4159d61d41e29eddfaa4fe6a681b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/62ac84d0b8b942e5939a8e527a749e57.png