LinkedList的深入了解

　　什么是LinkedList?

　　LinkedList是一种双向链表。那什么是双向链表?根据双向链表的特点就是会有头节点和尾节点，并且节点之间是通过前驱指针和后继指针来维护关系的，而不是像数组那样通过上下标来维护节点之间的关系的。也就是说双向链表即可以从头到尾遍历，也可以从尾到头遍历

　　LinkedList与ArrayList的区别

　　大致区别如下：

　　1、ArrayList是基于动态数组的数据结构，LinkedList是基于链表的数据结构

　　2、对于随机访问 get() 和 set() 操作，ArrayList优于LinkedList，因为LinkedList没有继承RandomAccess，而且LinkedList要移动指针

　　3、对于add(新增)操作和remove(删除)操作，LinkedList比较占优势，因为ArrayList要移动数据

　　LinkedList继承了哪些类与接口?

　　public class LinkedList

　　extends AbstractSequentialList

　　implements List, Deque, Cloneable, java.io.Serializable{

　　}

　　LinkedList 类继承了 AbstractSequentialList 类，并实现了 List、Deque、Cloneable、Serializable

　　LinkedList中主要的成员变量

　　// 初始化链表的长度为0

　　transient int size = 0;

　　// 指向头节点的变量

　　transient Node first;

　　// 指向尾节点的变量

　　transient Node last;

　　LinkedList的构造方法

　　LinkedList()

　　// 创建一个空的构造方法

　　public LinkedList() {

　　}

　　LinkedList(Collection c)

　　// 创建一个指定Collection对象作为参数的构造函数，元素的顺内由这个对象迭代返回的顺序决定

　　public LinkedList(Collection c) {

　　this();

　　addAll(c);

　　}

　　addAll(Collection c)方法

　　// 将集合中的所有元素从指定的位置开始插入这个列表

　　public boolean addAll(Collection c) {

　　return addAll(size, c);

　　}

　　addAll(int index, Collection c)方法

　　public boolean addAll(int index, Collection c) {

　　// 判断下标元素是否在链表的长度范围之内

　　checkPositionIndex(index);

　　// 将集合转换为Object数组

　　Object[] a = c.toArray();

　　// 计算Object数组的长度

　　int numNew = a.length;

　　// 如果Object数组长度为0

　　if (numNew == 0)

　　// 返回布尔值false

　　return false;

　　// pred节点为succ节点的前驱

　　Node pred, succ;

　　// 如果下标等于链表长度的时候

　　if (index == size) {

　　// succ节点指向为null

　　succ = null;

　　// pred节点指向尾节点

　　pred = last;

　　} else {

　　// 否则如果下标不等于链表长度的话，那么succ节点就是node()方法通过下标索引获得

　　succ = node(index);

　　// 获得链表中的对应的节点对象

　　pred = succ.prev;

　　}

　　// 遍历要添加内容的数组

　　for (Object o : a) {

　　@SuppressWarnings("unchecked") E e = (E) o;

　　// 创建新的节点，将遍历的值包装成Node节点

　　Node newNode = new Node<>(pred, e, null);

　　// 如果前驱节点为null

　　if (pred == null)

　　// 那么新的节点就是头节点

　　first = newNode;

　　else

　　// 否则pred指向新创建的节点

　　pred.next = newNode;

　　// pred节点往后移动一位

　　pred = newNode;

　　}

　　// 因为pred节点是succ节点的前驱节点，反过来也就是说succ是pred的后继节点

　　// 所以如果succ为null，表示pred为尾节点

　　if (succ == null) {

　　last = pred;

　　} else {

　　/**

　　* 否则如果succ不是尾节点，那么只要保证pred节点是succ节点的前驱节点、

　　succ节点是pred的后继节点这种双向链表的关系就可以了

　　*/

　　pred.next = succ;

　　succ.prev = pred;

　　}

　　// 元素个数增加

　　size += numNew;

　　modCount++;

　　return true;

　　}

　　checkPositionIndex(int index)方法

　　private void checkPositionIndex(int index) {

　　if (!isPositionIndex(index))

　　// 抛出 IndexOutOfBoundsException 异常

　　throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

　　}

　　isPositionIndex(int index)方法

　　private boolean isPositionIndex(int index) {

　　// 这个这么简单就不解释了吧

　　return index >= 0 && index <= size;

　　}

　　Node节点

　　private static class Node {

　　E item; // 节点的值

　　Node next; // 指向前一个节点

　　Node prev; // 指向后一个节点

　　// 初始化

　　Node(Node prev, E element, Node next) {

　　this.item = element;

　　this.next = next;

　　this.prev = prev;

　　}

　　}

　　LinkedList的常用方法

　　add(E e)

　　// 使用双向链表的尾插法

　　public boolean add(E e) {

　　// 将元素插入到链表尾部

　　linkLast(e);

　　return true;

　　}

　　linkLast(E e)

　　// 插入的节点为尾节点

　　void linkLast(E e) {

　　// 创建一个节点并初始化为尾节点

　　final Node l = last;

　　// 初始化新的节点，前驱的节点为l，后继节点为null

　　final Node newNode = new Node<>(l, e, null);

　　// 因为是在链表的尾部插入节点，所以新的节点作为尾节点(这个不难理解)

　　last = newNode;

　　// l节点作为newNode节点的前驱节点，如果l为空，则说明newNode前驱节点为空

　　if (l == null)

　　// 在双向链表中，前驱节点为空，那么该节点为头节点

　　first = newNode;

　　else

　　// 否则 l 的下一个节点指向该节点

　　l.next = newNode;

　　// 链表长度+1

　　size++;

　　modCount++;

　　}

　　add(int index, E element)

　　// 指定位置插入元素

　　public void add(int index, E element) {

　　// 判断下标索引是否在链表长度范围内(上述讲到过)

　　checkPositionIndex(index);

　　// 如果下标索引等于链表长度

　　if (index == size)

　　// 则采用尾插法(刚刚讲到过)

　　linkLast(element);

　　else

　　// 否则采用头插法

　　linkBefore(element, node(index));

　　}

　　linkBefore()

　　// 插入的节点为头节点，在节点succ之前插入元素e

　　void linkBefore(E e, Node succ) {

　　// assert succ != null;

　　// succ节点的前驱节点为pred

　　final Node pred = succ.prev;郑州哪家医院看妇科好 http://www.120zzkd.com/

　　// 初始化新的前驱节点为pred，后继节点为succ(简单地说就是在pred和succ节点之间插入元素)

　　final Node newNode = new Node<>(pred, e, succ);

　　// 后继节点为succ，succ的前驱节点为newNode

　　succ.prev = newNode;

　　// 如果pred为null

　　if (pred == null)

　　// 则newNode为头节点

　　first = newNode;

　　else

　　// 否则pred的下一个节点指向newNode

　　pred.next = newNode;

　　// 链表长度+1

　　size++;

　　modCount++;

　　}

　　remove(Object o)

　　// 删除元素

　　public boolean remove(Object o) {

　　/** 通过双向链表的前后关系，遍历双向链表。

　　* 判断是否存在元素和要删除的元素相同。

　　* 如果遍历到了，那么就删除元素，并且返回true

　　*/

　　if (o == null) {

　　for (Node x = first; x != null; x = x.next) {

　　if (x.item == null) {

　　unlink(x);

　　return true;

　　}

　　}

　　} else {

　　for (Node x = first; x != null; x = x.next) {

　　if (o.equals(x.item)) {

　　unlink(x);

　　return true;

　　}

　　}

　　}

　　// 如果没遍历到，那么就返回false

　　return false;

　　}

　　unlink()

　　// 删除非空节点

　　E unlink(Node x) {

　　// assert x != null;

　　final E element = x.item;

　　// 获取该元素的后继节点

　　final Node next = x.next;

　　// 获取该元素的前驱节点

　　final Node prev = x.prev;

　　// 如果前驱节点pred为null

　　if (prev == null) {

　　// 表示当前要删除的节点为头节点，让pred的后继节点作为头节点

　　first = next;

　　} else {

　　// 否则直接使用双向链表删除节点

　　prev.next = next;

　　// 将删除节点x的前驱节点设置为null

　　x.prev = null;

　　}

　　// 如果后继节点为null

　　if (next == null) {

　　// 表示当前删除的节点为尾节点，将前驱节点作为尾节点

　　last = prev;

　　} else {

　　// 否则如果后继节点不为null，使用双向链表删除节点

　　next.prev = prev;

　　// 将删除节点x的后继节点设置为null

　　x.next = null;

　　}

　　// 将删除节点的值设置为null，方便垃圾回收

　　x.item = null;

　　// 链表长度-1

　　size--;

　　modCount++;

　　return element;

　　}

　　get(int index)

　　// 获取下标元素

　　public E get(int index) {

　　// 判断下标是否在链表长度范围内(上述讲到过)

　　checkElementIndex(index);

　　// 获取下标节点，返回节点的值

　　return node(index).item;

　　}

　　node(int index)

　　// 获取下标节点

　　Node node(int index) {

　　// assert isElementIndex(index);

　　// 判断下标索引是靠近头节点还是尾节点

　　if (index < (size >> 1)) {

　　// 获取头节点

　　Node x = first;

　　// 遍历index的节点

　　for (int i = 0; i < index; i++)

　　x = x.next;

　　return x;

　　} else {

　　// 获取尾节点

　　Node x = last;

　　// 遍历index的节点

　　for (int i = size - 1; i > index; i--)

　　x = x.prev;

　　return x;

　　}

　　}

　　总结

　　1、LinkedList 添加的元素在取的时候与添加的时候的顺序一致。因为向双向链表的尾部添加元素，然后按照头节点顺序遍历获取，所以一致

　　2、LinkedList 允许添加重复元素

　　3、LinkedList 不是线程安全的集合

　　4、LinkedList 允许添加 null 元素

　　5、add 方法插入元素是在双向链表的尾部插入

　　6、get 方法遍历双向链表，先判断下标靠近头节点还是尾节点，这样会减少多余的循环