作者：峡谷人123_742 | 来源：互联网 | 2023-09-09 12:10
LinkedList是Collection下的一个list实现，就像ArrayList一样。和ArrayList不同的是它是链表结构，而ArrayList是顺序结构。我们平常使用的
链接列表是Collection下的列表实现，类似于ArrayList。 与ArrayList不同，它是链表结构，ArrayList是顺序结构。 我们平时使用的list是一样的，理论上一种list可以满足所有的需求。 但是，它们在执行过程中存在差异，达到需求所需的资源也不同。 关于在什么情况下使用哪个list，让我们来看看需求和当前情况。
视频：
链接列表由AbstractSequentialList继承的双向链表
链接列表可以作为堆栈、队列或双端队列进行操作。
因为链接列表实现了列表接口，所以队列操作
链接列表实现了Deque接口，可以将链接列表用作双端队列。
LinkedList实现了Cloneable接口，可以覆盖函数clone()，进行克隆。
由于链接列表提供了java.io.Serializable接口，因此可以通过串行化传输链接列表http://www.Sina.com /。
链接列表是异步的。
支持序列化
//创建一个LinkedList来保护缺省构造函数LinkedList () Collection中的所有元素。 链接列表(collection？ 扩展会话(http://www.Sina.com /
链接的列表由AbstractSequentialList继承，并实现了Dequeue接口。 “链接的列表”包含两个重要成员：头和大小。
header是双向链表的标题，是与双向链表节点对应的类Entry的实例。 Entry包含名为previous、next和element的成员变量。 其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点包含的值。
size是双向链表中的节点数。 ##双向链表结构
链表：链表是一种重要的数据结构，有单链表和双链表分单链表。
单链表(单向链表)由两部分组成：数据域(Data )和节点域(Node )。 单链表就像一条结很多的绳子，每个结相当于一个节点，每个节点之间都有一条绳子相连。 这种原理的实现是通过节点节点区域的头部指针head实现的，每个节点都有一个指针，每个节点指针的方向都指向自己，最后一个节点的head点为null，这样就像前面提到的绳索一样链如果需要查找链表中的任何节点，则必须从一开始就进行遍历。
双向链表结构
双链表(双向链表)双链表比单链表多尾指针(tail )，双链表的每个节点都有头指针head和尾指针tail。 双链表比单链表更容易操作，双链表节点第一个节点的head指向null，tail指向下一个节点的tail。 末尾节点的head指向上一个节点的head，tail指向null，是双向关系；
如果需要在单链表中搜索元素，则必须从第一个元素开始搜索。 双向链表在每个节点上包含两个指针，第一个节点和最后一个节点除外。 此指针指向上一个节点的地址和下一个节点的地址，以便还可以通过该节点搜索其他节点。
插入删除不需要移动元素。 您也可以立即插入删除、在结构前后插入数据，或双向遍历###链表
AbstractSequentialList链接列表是AbstractSequentialList的子类
AbstractSequentialList是get (索引)、set (索引、E element )、add (索引、E element )、remove (索引) ) 既然所有这些接口都是随机访问列表的，且链接列表已由双向链表AbstractSequentialList继承，那么名为“get (索引)”的接口就已经实现
另外，如果需要使用AbstractSequentialList实现自己的列表，则可以扩展该类并提供listIterator (和size )方法的实现。 要实现不可修改的列表，需要实现列表迭代器的hasNext、next、hasPrevious、previous和索引方法。
链接列表继承关系：
Java.lang.object Java.util.abstractcollectionejava.util.abstractlistejava.uti
l.AbstractSequentialList
↳ java.util.LinkedList public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { …… } LinkedList与Collection关系
Collection:
Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
LinkedList的本质是双链表，实现 List 和 Deque接口:
在LinkedList中，每个节点都用内部类Node表示：
具体的过程可以看下面这张图：
点我
每个node都是节点，里面有三个属性，分别指向上一个节点、下一个节点、实际储存元素开辟的内存空间
而对linkedlist里元素的操作方法都是对这些节点进行操作：
add()操作:
/** * Appends the specified element to the end of this list. * * This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } remove()操作
/** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }//查找对应索引 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Unlinks non-null node x. */ E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; } 可以看到都是对node节点进行操作，真实的实例内存并没有任何改变，等着jvm回收。
List使用场景
ArrayList在随机访问方面比较擅长，LinkedList在随机增删方面比较擅长
对于需要快速插入，删除元素，使用LinkedList。因为ArrayList要想在数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。
对于需要快速随机访问元素（get()），应该使用ArrayList，因为LinkedList要移动指针、遍历节点来定位，所以速度慢。
对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
对于插入数据使用时间的对比：
public static void addTest(){ //批量插入，每次都向首位插入数据； LinkedList linkedList = new LinkedList(); long time1 = new Date().getTime(); for(int m=0;m<300000;m++){ linkedList.add(0,null); } long time2 = new Date().getTime(); System.out.print("linkedList批量插入时间:"+(time2 - time1)+"ms\n"); ArrayList arraylist = new ArrayList(); long time3 = new Date().getTime(); for(int n=0;n<300000;n++){ arraylist.add(0, null); } long time4 = new Date().getTime(); System.out.print("arrayList批量插入时间:"+(time4 - time3)+"ms\n"); } 结果：
linkedList批量插入时间:9ms
arrayList批量插入时间:3696ms
那么问题就来了：
Q：什么时候使用Arraylist，什么时候使用LinkedList？
A：zjdmn需要频繁查询数组的时候使用ArrayList比较快，zjdmn需要频繁操作数组进行增删插入操作的时候使用LinkList比较合适。当然直接在末尾添加数据ArrayList用时也不是特别多，因为在末尾操作后面没有数据。
Q：那什么时候适合用list呢
A：涉及到“栈”、“队列”、“链表”等操作，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍
对于需要快速插入，删除元素，应该使用LinkedList。对于需要快速随机访问元素，应该使用ArrayList。对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。 Q：线程安全的数组，什么是线程安全？
A：线程安全就是当前资源只能被单独一个线程访问，也就是加同步锁的线程。默认的线程安全的list是Vector；
以上，如果有哪里不对或者不清楚的地方欢迎勾搭，多谢指正
京公网安备 11010802041100号