Java的List集合框架之LinkedList详细解析_开发_开发者

(一)List子父层级：

Java的List集合框架之LinkedList详细解析

List接口继承于Collection，Collection继承Iterable;
LIst接口实现类分为：Vector、ArrayList、LinkedList;

(二)List实现类

1、LinkedList实现类

（1）LinkedList底层编程客栈是内部Node类的存储，prev、next、item值，同时最外层还有first、last节点；

（2）LinkedList是线程不安全的，多线程环境会报并发修改异常Java.util.ConcurrentModificationException。

（3）LinkedList无扩容机制，底层是双向链表结构，内部是Node结构，外部是first、last首尾节点。

2、常见源码

（1）构造方法：

//无参构造，有参构造是将一个LinkedList对象传入进行追加（数据复制）
	public LinkedList() {   }

（2）add方法：

   public boolean add(E e) {
      linkLast(e);//将e以尾插法入链表
      return true;
    }
    //新数据入链表
    void linkLast(E e) {
        final Node<E> l = last;//获取尾节点
        final Node<E> newNode = new Node<>(l, e, null);//调用Nodjavascripte构造方法进行入链表
        last = newNode;//修改最新尾节点
        if (l == null)//判定是否为第一个链表节点
      编程客栈      first = newNode;//设置为第一个节点
        else
            l.next = newNode;//将新节点与旧节点相连
        size++;//数量自增
        modCount++;//操作链表自增
    }
    //内部类Node，用于链表底层数据存储
    private static class Node<E> {
        E item;//存储值类型泛型
        Node<E> next;//下一节点
        Node<E> prev;//上一节点
        //基于构造方法进行链表构造
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//当前节点存储值
            this.next = next;//设置当前新节点的下一节点值
            this.prev = prev;//设置当前新节点的上一节点值
        }
    }

（3）remove方法：

 //列举根据值删除,不列举按索引删除remove，逻辑大体差不多
  public boolean remove(Object o) {
     if (o == null) {//空值删除
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 unlink(x);//调用删除方法
                 return true;
             }
         }
     } else {
         for (NMXKhiOHTpyode<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item)) {
                 unlink(x);//调用删除方法
                 return true;
             }
         }
     }
     return false;
   }
   //删除节点方法，将节点的前后节点进行连接，然后将自身置空，其中判定首节点和尾节点为空处理
   E unlink(Node<E> x) {
       final E element = x.item;//删除节点值
       final Node<E> next = x.next;//删除节点的下一节点
       final Node<E> prev = x.prev;//删除节点的上一节点
       if (prev =python= null) {//上一节点那为空
           first = next;//设置新的首节点
       } else {
           prev.next = next;//将删节点的前后链接（前节点）
           x.prev = null;//置空当前节点的prev值
       }
       if (next == null) {//删除节点下一节点为空
           last = prev;//设置新的尾节点
       } else {
           next.prev = prev;//删除节点的前后链接（针对后节点）
           x.next = null;//置空当前节点的next值
       }
       x.item = null;//置空当前节点值
       size--;//数量减一
       modCount++;//操作次数自增
       return element;//返回删除节点值
   }

（4）get方法：

 public E get(int index) {
    checkElementIndex(index);//是否在正常范围内，index>=0&&index<size
     return node(index).item;//返回指定索引节点值
 }
 //根据索引值返回节点,根据二分法(折半)查找
 Node<E> node(int 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;//返回节点
     }
 }

（5）set方法：

 //指定索引位置进行设值
  public E set(int index, E element) {
      checkElementIndex(index);//检查索引是否合法
      Node<E> x = node(index);//获取索引节点
      E oldVal = x.item;//原索引节点值
      x.item = element;//设值
      return oldVal;//返回旧值
  }