java基础 浅解list集合中ArrayList与LinkedList

本文主要是介绍java基础 浅解list集合中ArrayList与LinkedList，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java 中常用的集合有list，set，map三种，而这个其实也就是接口，而各自有其实现的集合类。注：其所在的位置为java.util 包下面，所以不要导入错了。

本章节又要讲解list这个接口

list

有序集合（也称为序列 ）。 该界面的用户可以精确控制列表中每个元素的插入位置。 用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。

而实现list接口的类有AbstractList ， AbstractSequentialList ， ArrayList ， AttributeList ， CopyOnWriteArrayList ， LinkedList ， RoleList ， RoleUnresolvedList ， Stack ， Vector 。

虽然这样多的实现类，但是一般我们用的是ArrayList 和LinkedList 这两个，所以我们讲解一下这两个实现类。

ArrayList

因为list接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。同时其是不同步的，所以数据是不安全的。

如何看是一个数组呢？为什么是一个可变的数组，数组本身不是不可以变吗？

看起构造函数，反向默认了一个属性elementData，以及其默认值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA

可以看出其明显是一个数组，我在前面Java基础–简单讲解数组中提到，数组长度是不可变的。那为什么list明明是数组，但是其长度可以变。难道不矛盾吗？

可变的数组，其实本质就是新建了一个数组，当然如果查看其是如何运用数组对其长度修改的，必然有一个添加数据的判断。因为数组的长度是无法改变的，这个是毋庸置疑的。而list 的添加方法是add，所以从此出开始着手

    /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

解读： 其中的size其实可以理解成add这个数据的索引值，而不是数组的长度。 需要看 ensureCapacityInternal(size + 1);这个方法的。其中 size+1的原因是索引一般都从0开始的，但是长度是从1开始的。

  private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}

解读：ensureCapacityInternal方法体是以 calculateCapacity(elementData, minCapacity)为参数的ensureExplicitCapacity方法。我们先开作为参数的calculateCapacity(elementData, minCapacity)方法：

       private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}

解读：elementData初始化DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个源码中构造函数中可以看到：
DEFAULTCAPACITY_EMPTY_ELEMENTDATA默认为{} 这个在上面截图中也可以看到。DEFAULT_CAPACITY默认值是10.在截图中也可以看到。
Math.max()方法是对比两个变量，那个值大返回那个值。
所以calculateCapacity方法就是如果返回数据长度。

 private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

解读：modCount这个值是记录list被修改的次数，下面就是判断数据应该放在的索引位置比较存储数据的数组长度，如果大于哪呀就会调用grow方法。

 /*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}

解读：其中需要解释的就是newCapacity = oldCapacity + (oldCapacity >> 1); 中>>1是什么意思，这个偏移1位，也就是等于数字除以2.而newCapacity 代表新的数组长度等于旧的数组长度+旧的数组长度的一半。还有就是Arrays.copyOf方法是什么东西，其实这个应该在数组讲解中讲解的，现在补充一下

copyOf(int[] original, int newLength) 复制指定的数组，截取或用 0 填充（如有必要），以使副本具有指定的长度

public class Test {public static void main(String[] args) {int[] k= {1,2,3};int[] s=Arrays.copyOf(k, 5);System.out.print(Arrays.toString(s));}
}
//输出
[1, 2, 3, 0, 0]

可见copyOf方法是如何做了复制原来数组，当然也可以长度大于原来数组，不过缺少数据的部分会补充默认值。

• 注意：
  • ArrayList是一个可变的数组，其实本质不是数组可变，而是通过复制后新建数据而扩展长度的。
  • ArrayList的数据是不安全的，因为在判断旧的数组长度的时候，没有对数组加锁。

现在理解万ArrayList的原理，现在可以看一下其常用的一些方法。

先看起添加元素的方法add ，其中有四个方法，依次演示

public class Test {public static void main(String[] args) {List list=new ArrayList();list.add(1);// add(E e) 将指定的元素添加到此列表的尾部。System.out.println(list);//[1]list.add(2);list.add(3);list.add(1,5);//	add(int index, E element)   将指定的元素插入此列表中的指定位置。System.out.println(list);//[1, 5, 2, 3]int[] arr= {6,7};list.addAll(list);//	addAll(Collection<? extends E> c)    按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。System.out.println(list);//[1, 5, 2, 3, 1, 5, 2, 3]list.addAll(2,list);//	addAll(int index, Collection<? extends E> c)   从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。System.out.println(list);//[1, 5, 1, 5, 2, 3, 1, 5, 2, 3, 2, 3, 1, 5, 2, 3]}
}

看起取出的数据方法get。以及补充了foreach方法，其中有老版和jdk1.8版本

public class Test {public static void main(String[] args) {List<Integer> list=new ArrayList<Integer>();list.add(1);// add(E e) 将指定的元素添加到此列表的尾部。list.add(2);list.add(3);list.add(4);list.add(5);int size= list.size();//可以得到其长度for(int i=0;i<size;i++) {System.out.print(list.get(i)+"\t");//get(index) 可以通过get方法，通过索引中取}System.out.println();System.out.println("===========================");
//    下面是两个写法是补充。//当然也有一些缩写方法，那就是foreach 这个是可以取出迭代的数据。是for循环的一个简化版for(Integer num:list) {System.out.print(num+"\t");}System.out.println();System.out.println("===========================");
//    jdk1.8有了一个foreach方法，其实也是使用了lambda写法。以及最后的简写list.forEach((Integer num)->{System.out.print(num+"\t");});System.out.println();System.out.println("===========================");list.forEach((num)->{System.out.print(num+"\t");});System.out.println();System.out.println("===========================");list.forEach(num->{System.out.print(num+"\t");});System.out.println();System.out.println("===========================");list.forEach(num->System.out.print(num+"\t"));System.out.println();System.out.println("===========================");list.forEach(System.out::print);}
}
//输出
1	2	3	4	5	
===========================
1	2	3	4	5	
===========================
1	2	3	4	5	
===========================
1	2	3	4	5	
===========================
1	2	3	4	5	
===========================
1	2	3	4	5	
===========================
12345

list中的删除元素的常用发方法方法。

public class Test {public static void main(String[] args) {List<String> list=new ArrayList<String>();list.add("A");// add(E e) 将指定的元素添加到此列表的尾部。list.add("B");list.add("C");list.add("D");list.add("E");System.out.println(list);//[A, B, C, D, E]System.out.println(list.remove(2));//C     remove(int index)    移除此列表中指定位置上的元素。 还可以看出其返回删除的数据System.out.println(list);//[A, B, D, E]System.out.println(list.remove("B"));  //true	remove(Object o)  移除此列表中首次出现的指定元素（如果存在）。 存在返回true 不存在返回 falseSystem.out.println(list);//[A, D, E]list.clear();//clear()  移除此列表中的所有元素。System.out.println(list);//[]}
}

如何修改arraylist中的数据，请使用以下方法

public class Test {public static void main(String[] args) {List<String> list=new ArrayList<String>();list.add("A");// add(E e) 将指定的元素添加到此列表的尾部。list.add("B");list.add("C");list.add("D");list.add("E");System.out.println(list);//[A, B, C, D, E]System.out.println(list.set(2,"K"));//C     set(int index, E element)    用指定的元素替代此列表中指定位置上的元素。并返回被替代的数据System.out.println(list);//[A, B, K, D, E]}
}

还有其他的一些方法：

public class Test {public static void main(String[] args) {ArrayList<String> list=new ArrayList<String>();list.add("A");// add(E e) 将指定的元素添加到此列表的尾部。list.add("B");list.add("C");list.add("D");list.add("E");
//	System.out.println(list);//[A, B, C, D, E]System.out.println(list.contains("k"));//false   contains(Object o) 如果此列表中包含指定的元素，则返回 true。否则返回falseSystem.out.println((ArrayList) list.clone());//因为list中没有clone方法，所以在创建的时候要写ArrayList，这个我在对象中讲过，调用方法会看等于号左侧接口，而非右侧的实现类。
//clone()返回此 ArrayList 实例的浅表副本。（不复制这些元素本身。）  Object[] arr= list.toArray();  // toArray()    按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。
//	System.out.println(list1);System.out.println(list.isEmpty());//isEmpty()如果此列表中没有元素，则返回 trueSystem.out.println(list.indexOf("B"));//indexOf(Object o)  返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。}
}

虽然ArrayList是底层是一个数组，但是不同于数组，其数据可以存储不同类型。看下面代码

public class Test {public static void main(String[] args) {List list=new ArrayList();list.add("ab");list.add(2);list.add(2.6);System.out.print(list);}
}
//输出
[ab, 2, 2.6]

其根本原因就是在其add的时候是一个强制转换成object。而object是数据的父类，即总父类，无论基本数据类型还是String等都是其子类。通过get方法即可看出

public class Test {public static void main(String[] args) {List list=new ArrayList();list.add("ab");list.add(2);list.add(2.6);String data1=(String) list.get(0);//在取出第一个数据的时候，明明是字符串但是还需要加（String）进行转换。System.out.print(list);}
}

LinkedList

官方文档中对于LinkedList进行了解释。

• linkedlist是一个双向列表。也就是可以从前后进行操作。
• linkedlist可以提供先进先出的的队列操作，而其是一个链接列表。
• 而其是实现不是同步的，也就是数据无法保证安全。

现在需要从底层来理解一些linkedlist，首先linkedlist是基于链表实现的，这个就是其可以实现双向操作的原因。而什么什么链表？

链表其实是c/c++引入的一个概念，是一种线性的存储结构（数组不是线性结构）。

既然是线性结构，那么我需要看一下线性结构的定义和特征。

• 定义
  • 线性结构是一个有序数据元素的集合
  • 常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)
  • 常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

看说数组不是线性结构，可能有人有疑问了，数组难道不是一条吗，毕竟靠索引就可以取出数据的。下面我们通过其特征进行简单的理解。

• 特征
  • 集合中必存在唯一的一个"第一个元素"；
  • 集合中必存在唯一的一个"最后的元素"；
  • 除最后元素之外，其它数据元素均有唯一的"后继"；
  • 除第一元素之外，其它数据元素均有唯一的"前驱"。

如果看起字面意思感觉很懵逼，其实我第一眼看到的时候也懵逼。我们先看图然后再继续解读。如下图

可以看出线性结构再存储数据的时候，同时会存储下一个数据的地址。这个必然带出一个LinkedList缺点，那就是比ArraysList存储同样的数据，更占内存。

当然画图只是一种形象的表达，方便理解而已。现在开始刨源码，进行

上面是源码中构造函数以及其两个属性。

还是因为LInkedLIst也继承list，所以还是查看其add方法中的源码。

这个是源码，所以之间看起linklast方法。

看见这个可能有点不理解了，因为ArrayList的数组至少还有一个添加数据的的方式，比如：数组[索引]=数据。而这个好像没有，不过我们需要看Node这个类，因为好像添加数据就是对其进行操作的。所以先看Node类。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pn7BJris-1605779303801)(C:\Users\jhfan\AppData\Roaming\Typora\typora-user-images\image-20201118210514097.png)]

进去发现Node类是LinkedList的一个内部类。而其有三个属性item，next，prev。

其中item代表什么，其实就是我存储的数据，因为linkedlist有get方法，所以我们可以看其get方法返回什么值：

    // Positional Access Operations/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {checkElementIndex(index);//这个是判断索引是否在正确范围之内 index >= 0 && index < sizereturn node(index).item;// 可见其返回的是是node中的item值。}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {return index >= 0 && index < size;}/*** Returns the (non-null) Node at the specified element index.*/Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

通过get方法返回return node(index).item;。所以可以看出item就是我们放入linkedlist中的数据。

那么next，prev存储的都是node，但是在jvm中存储的对象，都是其地址或者说是引用。不过按照人家源码来说，称之为节点。

可以看出linkedlist是存储数据的时候将其处理成node，然后进行存储。

现在我看来看一下linkedlist中常用的方法。

首先还是添加元素：

public class Test {public static void main(String[] args) {List list=new LinkedList();list.add("A");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add("C");list.add(1,"B");// add(int index, E element)  在此列表中指定的位置插入指定的元素。当然其中index的范围在0<=index<=lengthSystem.out.println(list);//输出[A, B, C]//		list.addAll(list);//boolean addAll(Collection<? extends E> c)   添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。 
//		System.out.println(list);//[A, B, C, A, B, C]//		list.addAll(1,list);//addAll(int index, Collection<? extends E> c)  将指定 collection 中的所有元素从指定位置开始插入此列表。 
//		System.out.println(list);//[A, A, B, C, B, C]LinkedList Llist=new LinkedList();//多态的时候讲过，其中拥有的方法看左侧，有些是linkedlist拓展的方法也就是实现了list中方法，自己又添加了一些Llist.add("B");// boolean add(E e)  将指定元素添加到此列表的结尾。 Llist.add("C");System.out.println(Llist);Llist.addFirst("A");// addFirst(E e)   将指定元素插入此列表的开头。 System.out.println(Llist);//[A, B, C]Llist.addLast("D");//addLast(E e)           将指定元素添加到此列表的结尾。 System.out.println(Llist);//[A, B, C, D]//		因为linkedlist 也实现了queue类 所以也拥有其的方法LinkedList Qlist=new LinkedList();Qlist.offer("B");//boolean offer(E e)  将指定元素添加到此列表的末尾（最后一个元素）。  返回一个布尔数据Qlist.offer("C");System.out.println(Qlist);//[B, C]Qlist.offerFirst("A");//boolean offerFirst(E e)    在此列表的开头插入指定的元素。 System.out.println(Qlist);//[A, B, C]Qlist.offerLast("D");//boolean offerLast(E e) 在此列表末尾插入指定的元素。 System.out.println(Qlist);//[A, B, C, D]}
}

取出元素的方法

public class Test {public static void main(String[] args) {List list=new LinkedList();list.add("A");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add("B");list.add("C");list.add("D");System.out.println(list.get(2));// C    E get(int index)    返回此列表中指定位置处的元素。 
//		下面两个也是linkedlist 实现list方法后拓展System.out.println(((LinkedList) list).getFirst());// A    E getFirst()    返回此列表的第一个元素。 System.out.println(((LinkedList) list).getLast());// D    E getLast()     返回此列表的最后一个元素。 System.out.println(list);//[A, B, C, D]
//		
//        // 而这个下面是queue实现的方法System.out.println(((LinkedList) list).peek());//A  peek()   获取但不移除此列表的头（第一个元素）。 System.out.println(((LinkedList) list).peekFirst());//A  E peekFirst() 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 System.out.println(((LinkedList) list).peekLast());//D    peek()   peekLast()  获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。System.out.println(list);//[A, B, C, D]//         获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 
//System.out.println(((LinkedList) list).poll());//A   	 E poll() 获取并移除此列表的头（第一个元素） System.out.println(list);//[B, C, D]System.out.println(((LinkedList) list).pollFirst());//B  	 pollFirst()  获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 System.out.println(list);//[C, D]System.out.println(((LinkedList) list).pollLast());//D 	 pollLast()   获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 System.out.println(list);//[C]//		补充栈的 pop和push 方法list.add(0,"B");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add(0,"A");list.add("D");System.out.println(list);//[A, B, C, D]System.out.println(((LinkedList) list).pop());//A   	 E pop() 从此列表所表示的堆栈处弹出一个元素。  System.out.println(list);//[B, C, D]((LinkedList) list).push("E");// 	void push(E e)  将元素推入此列表所表示的堆栈。 System.out.println(list);//[E, B, C, D]
//		这个是栈的存储和取出的两个方法，而栈的特点就是先进后出，后进先出。}
}

看其删除的方法

public class Test {public static void main(String[] args) {List list=new LinkedList();list.add("A");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add("B");list.add("C");list.add("D");System.out.println(list.remove(0));// A      E remove()  获取并移除此列表的头（第一个元素）。 并且返回删除的数据System.out.println(list); //[B, C, D]System.out.println(list.remove("B"));// true   boolean remove(Object o)    从此列表中移除首次出现的指定元素（如果存在）。 System.out.println(list); //[C, D]list.add(0,"B");list.add(0,"A");System.out.println(list); //[A, B, C, D]System.out.println(((LinkedList)list).removeFirst());  //A      E removeFirst() 移除并返回此列表的第一个元素。 System.out.println(list);//[B, C, D]System.out.println(((LinkedList)list).removeLast());  //D       removeLast()   移除并返回此列表的最后一个元素。 System.out.println(list);//[B, C]list.add(0,"A");list.add("D");list.add("A");list.add("B");System.out.println(list);//[A, B, C, D, A, B]System.out.println(((LinkedList)list).removeFirstOccurrence("A")); //true    boolean removeFirstOccurrence(Object o)    从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。 System.out.println(list);//[B, C, D, A, B]System.out.println(((LinkedList)list).removeLastOccurrence("B")); //true    boolean removeLastOccurrence(Object o)   从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。 System.out.println(list);//[B, C, D, A]}
}

看起如何修改数据

public class Test {public static void main(String[] args) {List list=new LinkedList();list.add("A");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add("B");list.add("C");list.add("D");System.out.println(list);//[A, B, C, D]System.out.println(list.set(1, "E")); //B        set(int index, E element)     将此列表中指定位置的元素替换为指定的元素。返回被替代的数据System.out.println(list);//[A, E, C, D]}
}

补充一写方法

public class Test {public static void main(String[] args) {List list=new LinkedList();list.add("A");// boolean add(E e)  将指定元素添加到此列表的结尾。 list.add("B");list.add("C");list.add("D");System.out.println(list.size());//4     size() 返回此列表的元素数。}
}

看了一些arraylist和linkedlist中的方法，虽然有差异，但是其方法有些是一样，那么疑问就来了，两者之间的区别是什么。

区别

既然我们知道arraylist本质是数组，而linkedlist本质是node组成的线性结构。

那么先说两者的区别，也就是先说结果然后找出原因。

• 1：arraylist 占的存储空间比linkedlist更少（前提排除极少数据的特定情况）。
• 2：随机查询或修改拥有同样长以及同样数据的两者arrylist查询速度更快。
• 3：随机插入，删除的话linkedlist的速度更快。
• 补充：两者都是不安全的。

第一个区别，不需要详细再讲了，因为在上面看起源码的时候已经说过了，linkedlist存储占内存会更多。为什么会在括号中说明极少呢。因为arraylist默认长度为10，只存储一个数据。自然比linkedlist存储一个数据占去的内存更多。

第二个区别，查询速度arrylist速度更快，那是为什么，因为arraylist本身就是数组，通过索引即可get获取，而不linkedlist是通过引用地址进行调用。其中上面我们看到过的代码

    // Positional Access Operations/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {checkElementIndex(index);//这个是判断索引是否在正确范围之内 index >= 0 && index < sizereturn node(index).item;// 可见其返回的是是node中的item值。}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {return index >= 0 && index < size;}/*** Returns the (non-null) Node at the specified element index.*/Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {//索引index 在linked中没有，因为其需要依靠前后指针来遍历次数作为伪索引，而这个>>1 代表除以2.是一个二分遍历来减少遍历次数。Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

其中get中取数数据用的 Node node(int index)方法，而这个方法确实通过循环得到的数据。简单的说就是索引就是其第几个数据。小于长度的一半就是之间从前面数第几个数，大于就是倒着数即可。

第三条，无论是插入还是删除。arrayslist慢的主要原因就是需要重新将索引排序。而linked可以将其删除数据的前后指针给前后两个数据即可。

看图的话更容易理解

如果我们删除索引1中B,后面的数据索引必须重新定义一遍，因为删除一个数据后面的都需要重新排序一遍，毕竟索引变了。


而linkedlist删除 数据b，只需要将其 A 数据的 0x02变成0x03,C数据0x02变成0x01即可，不会重新再次进行排序。

当然无论是查询还是删除数据，其中的快慢都是一般，在一些极端情况下可能不同。所以记住两个随机，而不是按照顺序进行一些操作。

所以应用场景就是查询多用arraylist，插入和删除多就用linkedlist。

这篇关于java基础 浅解list集合中ArrayList与LinkedList的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---