JavaSE——集合4：LinkedList、ArrayList与LinkedList的选择

LinkedList%E7%9A%84%E5%85%A8%E9%9D%A2%E8%AF%B4%E6%98%8E-toc" style="margin-left:0px;">一、LinkedList的全面说明

LinkedList%E7%9A%84%E5%BA%95%E5%B1%82%E6%93%8D%E4%BD%9C%E6%9C%BA%E5%88%B6-toc" style="margin-left:0px;">二、LinkedList的底层操作机制

LinkedList%E6%B7%BB%E5%8A%A0%E7%BB%93%E7%82%B9%E6%BA%90%E7%A0%81-toc" style="margin-left:40px;">(一)LinkedList添加结点源码

LinkedList%E5%88%A0%E9%99%A4%E7%BB%93%E7%82%B9%E6%BA%90%E7%A0%81%C2%A0-toc" style="margin-left:40px;">(二)LinkedList删除结点源码

LinkedList%E5%B8%B8%E7%94%A8%E6%96%B9%E6%B3%95-toc" style="margin-left:0px;">三、LinkedList常用方法

ArrayList%E4%B8%8ELinkedList%E7%9A%84%E9%80%89%E6%8B%A9%C2%A0-toc" style="margin-left:0px;">四、ArrayList与LinkedList的选择

一、LinkedList的全面说明

LinkedList底层实现了双向链表和双端队列的特点
可以添加任意元素(元素可以重复)，包括null
线程不安全，没有实现同步和互斥

LinkedList%E7%9A%84%E5%BA%95%E5%B1%82%E6%93%8D%E4%BD%9C%E6%9C%BA%E5%88%B6">二、LinkedList的底层操作机制

LinkedList底层维护了一个双向链表
LinkedList中维护了两个属性first和last，分别指向首节点和尾节点
每个节点(Node对象)，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表
所以LinkedList元素的添加和删除，不是通过数组完成的，相对来说效率较高

LinkedList%E6%B7%BB%E5%8A%A0%E7%BB%93%E7%82%B9%E6%BA%90%E7%A0%81">(一)LinkedList添加结点源码

1. LinkedList linkedList = new LinkedList();public LinkedList() {}
2. 这时 linkeList 的属性 first = null  last = null
3. 执行 添加public boolean add(E e) {linkLast(e);return true;}
4.将新的结点，加入到双向链表的最后void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}

LinkedList%E5%88%A0%E9%99%A4%E7%BB%93%E7%82%B9%E6%BA%90%E7%A0%81%C2%A0">(二)LinkedList删除结点源码

linkedList.remove(); // 这里默认删除的是第一个结点1. 执行 removeFirstpublic E remove() {return removeFirst();}
2. 执行public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}
3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

LinkedList%E5%B8%B8%E7%94%A8%E6%96%B9%E6%B3%95">三、LinkedList常用方法

因为LinkedList也继承了Collection和List，所以List的方法也适用于LinkedList。

add()
remove() // 默认删除第一个结点
removeFirst()
removeLast()
set(索引值,插入的元素)
get(索引值)

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add("");linkedList.add(" ");linkedList.add(' ');linkedList.add(null);linkedList.add(null);System.out.println("linkedList=" + linkedList);// linkedList=[1, 2, 3, ,  ,  , null, null]// remove默认删除第一个结点linkedList.remove();System.out.println("linkedList=" + linkedList);// linkedList=[2, 3, ,  ,  , null, null]// 修改某个结点对象linkedList.set(1, 999);System.out.println("linkedList=" + linkedList);// linkedList=[2, 999, ,  ,  , null, null]// 得到某个结点对象// get(1) 是得到双向链表的第二个对象Object o = linkedList.get(1);System.out.println(o); // 999// 因为LinkedList 是 实现了List接口, 遍历方式System.out.println("===LinkeList遍历迭代器====");Iterator iterator = linkedList.iterator();while (iterator.hasNext()) {Object next = iterator.next();System.out.println("next=" + next);}// next=2// next=999// next=// next=// next=// next=null// next=nullSystem.out.println("===LinkeList遍历增强for====");for (Object o1 : linkedList) {System.out.println("o1=" + o1);}// next=2// next=999// next=// next=// next=// next=null// next=nullSystem.out.println("===LinkeList遍历普通for====");for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}// 2// 999//////// null// null
}

ArrayList%E4%B8%8ELinkedList%E7%9A%84%E9%80%89%E6%8B%A9%C2%A0">四、ArrayList与LinkedList的选择

	底层结构	增删的效率	改查的效率
ArrayList	可变数组	较低；底层依赖数组扩容	较高；根据数组索引查找
LinkedList	双向链表	较高；底层通过链表追加	较低；在链表中从头到尾遍历

如何选择ArrayList与LinkedList：

如果改查的操作多，选择ArrayList
如果增删的操作多，选择LinkedList
一般来说，80%-90%都是查询，因此大部分情况下会选择ArrayList
根据业务灵活选择，也可能一个模块使用的是ArrayList，另一个模块使用LinkedList。