List集合框架(三)——LinkedList(JDK1.8)

List集合框架(三)——LinkedList(JDK1.8)

文章目录

• • (一)List子父层级：
  • (二)List实现类
  • • • 1、linkedList实现类
      • 2、常见源码
      • • （1）构造方法：
        • （2）add方法：
        • （3）remove方法：
        • （4）get方法：
        • （5）set方法：
      • 3、总结

(一)List子父层级：

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 l = last;//获取尾节点
        final Node newNode = new Node<>(l, e, null);//调用Node构造方法进行入链表
        last = newNode;//修改最新尾节点
        if (l == null)//判定是否为第一个链表节点
            first = newNode;//设置为第一个节点
        else
            l.next = newNode;//将新节点与旧节点相连
        size++;//数量自增
        modCount++;// *** 作链表自增
    }
    //内部类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;//设置当前新节点的上一节点值
        }
    }

（3）remove方法：

 //列举根据值删除,不列举按索引删除remove，逻辑大体差不多
  public boolean remove(Object o) {
     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;
             }
         }
     }
     return false;
   }
   //删除节点方法，将节点的前后节点进行连接，然后将自身置空，其中判定首节点和尾节点为空处理
   E unlink(Node x) {
       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;//置空当前节点的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 node(int index) {
     if (index < (size >> 1)) {//前半部分查找
         Node x = first;//首节点
         for (int i = 0; i < index; i++)
             x = x.next;//获得指定索引节点
         return x;//返回节点
     } else {
         Node 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 x = node(index);//获取索引节点
      E oldVal = x.item;//原索引节点值
      x.item = element;//设值
      return oldVal;//返回旧值
  }

3、总结

  （1）linkedList是线程不安全，多线程环境会造成并发修改异常java.util.ConcurrentModificationException；
  （2）linkedList是一个双向链表结构（无扩容机制），内部是Node，外部是首尾节点first、last。