java——顺序表ArrayList与链表LinkedList-开发者社区

一.引言

通过本篇博客，学者将深刻认识到顺序表ArrayList与链表LinkedList的区别和使用方法，文章将通过对概念的深度解析，用通俗易懂的白话讲清了两者的关系和使用场景。

二.目录

1,线性表

2.顺序表

3.何为ArrayList？

4.ArrayList的使用

5.ArrayList的缺陷

6.链表

7.何为LinkedList?

8.LinkedList的使用

9.ArrayList和LinkedList的区别

三.线性表

线性表，顾名思义就是在某种意义上是具有相同特征的元素的有限排列。常见的线性表有：顺序表。链表，栈，队列等（在后面会出相应的博客，可以蹲）。

四.顺序表

顺序表，顾名思义就是有顺序的，是用一段物理地址连续的存储单元一次存储数据元素的线性结构，比如数组。

五.何为ArrayList？

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体的关系如下图所示，图中的关系只是集合中的冰山一角，在后面会渐渐拓展。

注意事项：

Arraylist是以泛型方式实现的，使用时必须要先实例化

六.ArrayList的使用

6.1 ArrayList与几个常用接口的联系

既然实现了部分接口，那就代表了有着相应的功能，如下图。

ArrayList实现了RandomAccess接口，表面支持了随机访问。

ArrayList实现了Cloneable接口，表面可以clone。

ArrayList实现了Serializable接口，表面支持序列化。

ArrayList的底层是一段连续的空间，可以动态扩容，是一个动态类型的顺序表。

6.2 构造ArrayList

void main(String[] args) { //构造空列表 List<Integer> list1=new ArrayList<>(); list1.add(1); list1.add(2); list1.add(3); for (int i = 0; i < list1.size(); i++) { System.out.print(list1.get(i)); }//1 2 3 //构造含有限个元素容量的列表 List<Integer> list2=new ArrayList<>(10); list2.add(4); list2.add(5); list2.add(6); //3 4 5 //若没有指定泛型,非常不推荐，不利于后续操作 List list3=new ArrayList(); list3.add(111); list3.add("abc"); System.out.println(list3); // [111, abc] }

6.3 ArrayList常见的方法

方法	解释
boolean add(E a)	尾插
void add(int index,E element)	将elemen插入到index位置
boolean addAll(Collection<?exteands E>c)	尾插c中元素
boolean remove(Object o)	删除第一个出现的o
E get(int index)	获取下标index位置的元素
E set(int index,E element)	将下标index位置元素设置为element
void clear()	清空
boolean contains(Object o)	判断o是否出现在线性表中
int indexOf(Object o)	返回第一个o所在的下标
E remove(int index)	删除index位置元素
int lastIndexOf(Object o)	返回最后一个o的下标
List<E> subList（int fromindex,int toIndex)	截取部分list

尤其要注意的是，Arraylist是一个动态类型的顺序表，在插入元素的过程中会自动扩容。

七.ArrayList的缺陷

7.1 效率问题

ArrayList是一段连续的空间，那么如果要进行插入或者删除元素的时候，那么在目标下标的元素开始，后面的元素都要整体移动，这样在元素非常多的时候效率是非常低下的。

7.2 扩容空间问题

一般扩容是按照一定的倍数来扩容的，这就导致在某些情况下会引起空间浪费，比如原来有100个空间，进行了2倍扩容，都是真正的元素只有101个，这样的话就浪费了将近一半的空间。

八.链表

针对ArrayList的缺陷，在这里引出链表的概念。问题来了，何为链表？

首先，链表也是由很多具有相同特征的元素构成的有限个数的线性表。与ArrayList不同的是，链表并不是物理意义上的连续，而是逻辑上的连续，元素与元素之间通过某些特定的标签来识别，就像通过门牌来区分房间，和C语言的指针地址等的概念类似。

8.1 链表的种类

8.1.1 单向或双向

8.1.2 带头或不带头

8.1.1 循环或非循环

8.1.1 无头单向非循环（最重要，面试常问）

九.何为LinkedList?

LinkedList是Java集合框架中的一个类，位于java.util包中，它实现了List接口和Deque接口，底层采用双向链表结构来存储元素。与ArrayList不同，LinkedList并不是物理地址连续的空间，而是通过节点之间的引用（指针）将各个元素串联起来，每个节点都保存着前一个节点和后一个节点的引用，因此它在头部和尾部插入、删除元素时效率非常高，时间复杂度为O(1)。

由于LinkedList的底层是链表结构，它在按下标随机访问元素时需要从头节点开始逐个遍历，时间复杂度为O(n)，因此在需要频繁按下标访问元素的场景下，其性能不如ArrayList。在实际开发中，如果业务场景以频繁插入、删除为主，推荐使用LinkedList；如果以随机访问为主，则推荐使用ArrayList。

十.LinkedList的使用

10.1 LinkedList与几个常用接口的联系

尤其要注意的是，LinkedList没有实现RandomAcess接口，不支持随机访问，这是与ArrayList不同的.

10.2 构造LinkedList

LinkedList不支持像ArrayList那样通过指定初始容量来构造，因为链表本身是动态的，不需要预先分配连续的内存空间。LinkedList只提供了无参构造和传入一个集合的构造两种方式。

void main(String[] args) { //无参构造 LinkedList<Integer> list1=new LinkedList<>(); list1.add(1); list1.add(2); list1.add(3); for (int i = 0; i < list1.size(); i++) { System.out.print(list1.get(i)); } }

可以看到，LinkedList没有提供类似new LinkedList<>(10)这种指定初始容量的构造方法，因为链表不需要像顺序表那样提前申请一段连续空间，它的节点是随用随建的。

10.3 LinkedList常见的方法

方法	解释
boolean add(E a)	尾插e
void add(int index,E element)	将elemen插入到index位置
boolean addAll(Collection<?exteands E>c)	尾插c中元素
E remove(int index)	删除index位置元素
boolean remove(Object o)	删除第一个出现的o
E get(int index)	获取下标index位置的元素
E set(int index,E element)	将下标index位置元素设置为element
void clear()	清空
boolean contains(Object o)	判断o是否出现在线性表中
int indexOf(Object o)	返回第一个o所在的下标
int lastIndexOf(Object o)	返回最后一个o的下标
List<E> subList（int fromindex,int toIndex)	截取部分list

十一.ArrayList和LinkedList的区别

ArrayList和LinkedList虽然都实现了List接口，但它们的底层结构、性能特点和使用场景有着明显的差异。下面从几个核心维度进行对比。

对比维度	ArrayList	LinkedList
底层结构	动态数组（一段物理地址连续的空间）	双向链表（节点之间通过引用串联）
随机访问	按下标直接定位，时间复杂度O(1)	需要从头节点逐个遍历，时间复杂度O(n)
插入、删除	中间位置插入、删除需要移动后续元素，效率低	只需修改前后节点的引用，头部和尾部插入、删除效率高，时间复杂度O(1)
内存占用	连续空间，扩容时可能造成空间浪费	每个节点额外存储前后引用，占用更多内存
扩容机制	按一定倍数动态扩容，可能浪费空间	无需扩容，节点随用随建
接口实现	实现了RandomAccess接口，支持随机访问	未实现RandomAccess接口，不支持随机访问
适用场景	以随机访问、按下标查询为主	以频繁插入、删除为主