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

目录

• (一)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<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;//返回旧值
  }

3、总结

（1）LinkedList是线程不安全，多线程环境会造成并发修改异常java.util.ConcurrentModificationException；

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

到此这篇关于Java的List集合框架之LinkedList详细解析的文章就介绍到这了,更多相关List集合框架之LinkedList内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！