【博学谷学习记录】超强总结，用心分享|Java基础分享-数据结构（数组、链表）

标签：位置 Java 元素 链表 数组 2.2 分享 数据

目录

1. 数组

2. 链表

2.1. 链表简介

2.2. 链表分类

2.2.1. 单链表

2.2.2. 循环链表

2.2.3. 双向链表

2.2.4. 双向循环链表

1. 数组

数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。

数组的特点是：提供随机访问 并且容量有限。

假如数组的长度为 n。
访问：O（1）//访问特定位置的元素
插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

 

假如链表中有n个元素。
访问：O（n）//访问特定位置的元素
插入删除：O（1）//必须要要知道插入元素的位置

 

2. 链表

2.1. 链表简介

链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。

链表的插入和删除操作的复杂度为 O(1) ，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。

2.2. 链表分类

常见链表分类：

1. 单链表
2. 双向链表
3. 循环链表
4. 双向循环链表

 

假如链表中有n个元素。
访问：O（n）//访问特定位置的元素
插入删除：O（1）//必须要要知道插入元素的位置

2.2.1. 单链表

单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。

 

2.2.2. 循环链表

循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。

 

2.2.3. 双向链表

双向链表 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

 

2.2.4. 双向循环链表

双向循环链表 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

2.3. 应用场景

• 如果需要支持随机访问的话，链表没办法做到。
• 如果需要存储的数据元素的个数不确定，并且需要经常添加和删除数据的话，使用链表比较合适。
• 如果需要存储的数据元素的个数确定，并且不需要经常添加和删除数据的话，使用数组比较合适。

2.4. 数组 vs 链表

数组的特点
在内存中，数组是一块连续的区域。 拿上面的看电影来说，这几个人在电影院必须坐在一起。
数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。 比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。
插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。
随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
并且不利于扩展，数组定义的空间不够时要重新定义数组。
链表的特点
在内存中可以存在任何地方，不要求连续。 在电影院几个人可以随便坐。
每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
不指定大小，扩展方便。链表大小不用定义，数据随意增删。
各自的优缺点
数组的优点

• 随机访问性强
• 查找速度快

数组的缺点

• 插入和删除效率低
• 可能浪费内存
• 内存空间要求高，必须有足够的连续内存空间。
• 数组大小固定，不能动态拓展

链表的优点

• 插入删除速度快
• 内存利用率高，不会浪费内存
• 大小没有固定，拓展很灵活。

链表的缺点

• 不能随机查找，必须从第一个开始遍历，查找效率低

 

标签：位置,Java,元素,链表,数组,2.2,分享,数据
From： https://www.cnblogs.com/elon-l/p/16771115.html