【数据结构】详细讲解常见的数据结构（通俗易懂）

 

人不走���

                                                                      

      个人主页：人不走空      

系列专栏：算法专题

⏰诗词歌赋：斯是陋室，惟吾德馨

 

前言

数据结构是计算机存储、组织数据的方式。在工作中，我们通常会直接使用已经封装好的集合API，这样可以更高效地完成任务。但是作为一名程序员，掌握数据结构是非常重要的，因为它可以帮助我们更好地理解和设计算法，从而提高程序的效率和可靠性。本文将对常见的几种数据结构进行介绍，通过了解这些数据结构的特点和优势，可以更好地在不同场景下选择合适的数据结构。

数据结构介绍

常见的数据结构大体分为两种类型：线性和非线性。

线性数据结构见名思义，整体结构的图像是一条直线。包括数组、链表、栈、队列等。非线性数据结构包括，树、堆、图等。

数组

数组是由多个元素组成的一个集合，表现形式如下图

 

数组

在内存中存储数组的空间是连续的，每个元素占据一定的内存空间，这也是为什么在声明数组时要指定长度，不然不知道要占用多少空间。以 Java 语言为例，当声明一个数组后，数组变量会指向数组对象的起始地址，也就是第一个元素的位置，如下图

 

数组在内存的表现

以此看来，当查询数组中的某个元素时，通过下标就可以计算出这个元素的内存地址，比如想查找下标为2的元素，那么arr[2]的内存地址 = arr的内存地址 + 2 * 元素大小，也就可以直接通过内存地址访问元素，时间复杂度为O(1)。

但是，数组也会带来一个问题：由于数组长度是固定的，所以在添加或删除元素时会涉及到创建新的数组来替换原数组，导致复杂度较高。例如，下面的代码演示了如何在数组末尾添加一个元素：

int[] arr = {1, 2, 3, 4, 5};    arr[arr.length] = 6; // 将要添加的元素放到数组的最后一个位置    int[] newArr = new int[arr.length + 1]; // 创建一个新的数组，长度加1    for (int i = 0; i