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

目录

一、LinkedList的全面说明

二、LinkedList的底层操作机制

(一)LinkedList添加结点源码

(二)LinkedList删除结点源码 

三、LinkedList常用方法

四、ArrayList与LinkedList的选择 

---

一、LinkedList的全面说明

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

二、LinkedList的底层操作机制

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

(一)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删除结点源码 

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常用方法

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

1. add()
2. remove()    // 默认删除第一个结点
3. removeFirst()
4. removeLast()
5. set(索引值,插入的元素)
6. 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与LinkedList的选择 

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

如何选择ArrayList与LinkedList：

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