常用数据结构

电玩女神 2022-05-17 10:06 244阅读 0赞

版权归作者所有，任何形式转载请联系作者。  
作者：鑫鱻（来自豆瓣）  
来源：[https://www.douban.com/note/616274789/][https_www.douban.com_note_616274789]

数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。

Java工具包提供了强大的数据结构，在开发中一般都离不开Java集合框架，主要包括Collection和Map两个主要接口，而程序中最终使用的数据结构是继承自这两个接口的数据结构类。

Java集合框架

从上面的Java集合框架图可以看到，主要分为Set、 List、Queue和Map四大体系，然而有很多开发者理不清他们之间的区别和联系，特别是对于一些小白来说如意混淆。这也是Java习惯工作面试时经常被考的知识点，那么我们今天来一起温习一下。

List接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为ArrayList和LinkedList，另外还有不常用的Vector。同时LinkedList还是实现了Queue接口，因此也可以作为队列使用。

List接口

Set接口通常表示一个集合，其中的元素不允许重复（通过hashcode和equals方法保证），常用实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap实现的，而TreeSet是通过Map中的TreeMap实现的。另外，TreeSet还实现了SortedSet接口，因此是有序的集合。

Set接口

Queue接口通常表示一个队列，是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

Map是一个映射接口，其中的每个元素都是一个key-value键值对。

Map接口

小编一般都是这样来理解记忆其大致区别的：

Set代表无序、不可重复的集合，

List代表有序、重复的集合，

Map代表具有映射关系的集合，

Queue代表一种队列集合。

关于集合框架的内容特别多，这里就不一一进行说明，后续再逐一分解，今天先来一起温习一下有关Java集合框架有关的面试题。

ArrayList和LinkedList的区别？  
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

4.查找操作indexOf,lastIndexOf,contains等，两者差不多。

5.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

ArrayList的扩容机制如何？  
如果在初始化ArrayList的时候没有指定初始化长度的话，默认的长度为10。在增加新元素的时候如果超过了原始的容量的话，新容量=原始容量\*3/2+1。

这个问题非常简单，稍微看一下源码就知道了。

public voidensureCapacity(intminCapacity)\{  
modCount++;  
intoldCapacity=elementData.length;  
if(minCapacity>oldCapacity)\{  
ObjectoldData\[\]=elementData;  
intnewCapacity=(oldCapacity\*3)/2+1;  
if(newCapacity

[https_www.douban.com_note_616274789]: https://www.douban.com/note/616274789/