java——顺序表ArrayList与链表LinkedList

一.引言通过本篇博客学者将深刻认识到顺序表ArrayList与链表LinkedList的区别和使用方法文章将通过对概念的深度解析用通俗易懂的白话讲清了两者的关系和使用场景。二.目录1,线性表2.顺序表3.何为ArrayList4.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 构造ArrayListvoid main(String[] args) { //构造空列表 ListInteger list1new 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 //构造含有限个元素容量的列表 ListInteger list2new ArrayList(10); list2.add(4); list2.add(5); list2.add(6); //3 4 5 //若没有指定泛型,非常不推荐不利于后续操作 List list3new 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 Ec)尾插c中元素boolean remove(Object o)删除第一个出现的oE get(int index)获取下标index位置的元素E set(int index,E element)将下标index位置元素设置为elementvoid clear()清空boolean contains(Object o)判断o是否出现在线性表中int indexOf(Object o)返回第一个o所在的下标E remove(int index)删除index位置元素int lastIndexOf(Object o)返回最后一个o的下标ListE subListint 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 构造LinkedListLinkedList不支持像ArrayList那样通过指定初始容量来构造因为链表本身是动态的不需要预先分配连续的内存空间。LinkedList只提供了无参构造和传入一个集合的构造两种方式。void main(String[] args) { //无参构造 LinkedListInteger list1new 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)尾插evoid add(int index,E element)将elemen插入到index位置boolean addAll(Collection?exteands Ec)尾插c中元素E remove(int index)删除index位置元素boolean remove(Object o)删除第一个出现的oE get(int index)获取下标index位置的元素E set(int index,E element)将下标index位置元素设置为elementvoid clear()清空boolean contains(Object o)判断o是否出现在线性表中int indexOf(Object o)返回第一个o所在的下标int lastIndexOf(Object o)返回最后一个o的下标ListE subListint fromindex,int toIndex)截取部分list十一.ArrayList和LinkedList的区别ArrayList和LinkedList虽然都实现了List接口但它们的底层结构、性能特点和使用场景有着明显的差异。下面从几个核心维度进行对比。对比维度ArrayListLinkedList底层结构动态数组一段物理地址连续的空间双向链表节点之间通过引用串联随机访问按下标直接定位时间复杂度O(1)需要从头节点逐个遍历时间复杂度O(n)插入、删除中间位置插入、删除需要移动后续元素效率低只需修改前后节点的引用头部和尾部插入、删除效率高时间复杂度O(1)内存占用连续空间扩容时可能造成空间浪费每个节点额外存储前后引用占用更多内存扩容机制按一定倍数动态扩容可能浪费空间无需扩容节点随用随建接口实现实现了RandomAccess接口支持随机访问未实现RandomAccess接口不支持随机访问适用场景以随机访问、按下标查询为主以频繁插入、删除为主总结来说ArrayList适合读多写少、按下标频繁访问的场景LinkedList适合频繁在头部或中间插入、删除元素的场景。在实际开发中应根据业务需求选择合适的数据结构才能获得更好的性能。