源码详解数据结构Linked List

转x33g5p2x  于2022-03-17 转载在 其他  
字(7.7k)|赞(0)|评价(0)|浏览(429)

本文分享自华为云社区《LinkedList 源码分析》，作者： 陈皮的JavaLib。

LinkedList 简介

java.util.Linked List 是 Java 集合框架中的成员之一，底层是基于双向链表实现，集合容量可动态变化的。它继承自 Abstract Sequential List 抽象类，实现了 List 接口。同时还实现了 Cloneable 和 Serializable 三个标记接口，说明 Array List 是可克隆复制的，可序列化的。

Array List 数组列表底层是基于动态数组实现的，所以优点是能支持快速随机访问，但是增删操作可能会比较慢（因为可能需要进行数组扩容，数据拷贝）。而且数组需要先申请一定的内存空间，可能会造成浪费。而链表列表 LinkedList 的优点是增删操作速度比较快，而且列表存储多少元素就动态申请多少节点来存储，比较节省内存空间。

为何要使用双向链表呢，主要在于遍历效率比单向链表高。例如当我们需要查找指定下标的节点，在指定下标进行增删改操作时，先判断这个位置是靠近头部还是尾部，从而决定从头部还是从尾部开始查找，提高效率。

  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>
  3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  5. }

2 LinkedList 源码分析

2.1 内部变量

LinkedList 的元素是存储在节点对象中的，节点类是 LinkedList 类的一个内部私有静态类，源码如下所示：

  1. private static class Node<E> {
  2.     E item;
  3.     Node<E> next;
  4.     Node<E> prev;
  6.     Node(Node<E> prev, E element, Node<E> next) {
  7.         this.item = element;
  8.         this.next = next;
  9.         this.prev = prev;
  10.     }
  11. }

LinkedList 中定义了3个变量，一个代表当前列表的元素个数，另外两个变量指向链表的头部和尾部。以及它的父类 AbstractList 中的 modCount 变量，每次对链表的增删改操作都会使它加1。

  1. transient int size = 0;
  3. transient Node<E> first;
  5. transient Node<E> last;
  7. protected transient int modCount = 0;

2.2 构造函数

ArrayList 有2个构造函数，一个无参构造函数，另一个使用指定 Collection 集合来构造集合的构造函数。

无参构造函数，什么都没有操作。

  1. public LinkedList() {}

使用指定 Collection 集合来构造链表，如果 Collection 不能为 null ，否则会抛出 npe 。

  1. public LinkedList(Collection<? extends E> c) {
  2.     this();
  3.     addAll(c);
  4. }
  6. public boolean addAll(Collection<? extends E> c) {
  7.     return addAll(size, c);
  8. }
  10. public boolean addAll(int index, Collection<? extends E> c) {
  11.     checkPositionIndex(index);
  13.     Object[] a = c.toArray();
  14.     int numNew = a.length;
  15.     if (numNew == 0)
  16.         return false;
  18.     Node<E> pred, succ;
  19.     if (index == size) {
  20.         succ = null;
  21.         pred = last;
  22.     } else {
  23.         succ = node(index);
  24.         pred = succ.prev;
  25.     }
  27.     for (Object o : a) {
  28.         @SuppressWarnings("unchecked") E e = (E) o;
  29.         Node<E> newNode = new Node<>(pred, e, null);
  30.         if (pred == null)
  31.             first = newNode;
  32.         else
  33.             pred.next = newNode;
  34.         pred = newNode;
  35.     }
  37.     if (succ == null) {
  38.         last = pred;
  39.     } else {
  40.         pred.next = succ;
  41.         succ.prev = pred;
  42.     }
  44.     size += numNew;
  45.     modCount++;
  46.     return true;
  47. }

2.3 常用方法

  • public E getFirst()

获取链表的第一个元素，如果不存在第一个节点，抛出异常。

  1. public E getFirst() {
  2.     final Node<E> f = first;
  3.     if (f == null)
  4.         throw new NoSuchElementException();
  5.     return f.item;
  6. }
  • public E getLast()

获取链表的最后一个元素，如果链表为空，则抛出异常。

  1. public E getLast() {
  2.     final Node<E> l = last;
  3.     if (l == null)
  4.         throw new NoSuchElementException();
  5.     return l.item;
  6. }
  • public E removeFirst()

删除第一个元素，如果链表为空，则抛出异常。

  1. public E removeFirst() {
  2.     final Node<E> f = first;
  3.     if (f == null)
  4.         throw new NoSuchElementException();
  5.     return unlinkFirst(f);
  6. }
  • public E removeLast()

删除最后一个元素，如果链表为空，则抛出异常。

  1. public E removeLast() {
  2.     final Node<E> l = last;
  3.     if (l == null)
  4.         throw new NoSuchElementException();
  5.     return unlinkLast(l);
  6. }
  • public void clear()

情况链表，遍历每一个节点，将每一个节点的内部引用都置为 null ，便于进行垃圾回收。

  1. public void clear() {
  2.     for (Node<E> x = first; x != null; ) {
  3.         Node<E> next = x.next;
  4.         x.item = null;
  5.         x.next = null;
  6.         x.prev = null;
  7.         x = next;
  8.     }
  9.     first = last = null;
  10.     size = 0;
  11.     modCount++;
  12. }
  • public boolean add(E e)

在链表尾部添加一个元素。

  1. public boolean add(E e) {
  2.     linkLast(e);
  3.     return true;
  4. }
  • public Iterator iterator()

获取 list 的迭代器，用于遍历集合中的元素。

  1. public Iterator<E> iterator() {
  2.     return new Itr();
  3. }
  • public int size()：返回集合元素个数。
  • public boolean contains(Object o)：是否包含某个元素。
  • public boolean remove(Object o)：删除某个元素。
  • public E get(int index)：获取指定下标的元素。
  • public E set(int index, E element)：在指定下标修改元素值。
  • public void add(int index, E element)：在指定下标添加元素。

3 常见面试题分析

3.1 LinkedList 是线程安全的吗？

我们通过分析源码可知，对它的任何操作都是没有加锁的，所以在多线程场景下，它是线程不安全的。它适合在非多线程使用场景下，并且增删操作比较多的情况。

  1. public static void main(String[] args) throws InterruptedException {
  3.     LinkedList<String> list = new LinkedList<>();
  5.     Thread thread1 = new Thread(() -> {
  6.       for (int i = 0; i < 1000; i++) {
  7.         list.add(Thread.currentThread().getName() + i);
  8.       }
  9.     }, "Thread01");
  10.     thread1.start();
  12.     Thread thread2 = new Thread(() -> {
  13.       for (int i = 0; i < 1000; i++) {
  14.         list.add(Thread.currentThread().getName() + i);
  15.       }
  16.     }, "Thread02");
  17.     thread2.start();
  19.     thread1.join();
  20.     thread2.join();
  22.     System.out.println(list.size()); // 输出不一定是2000，例如1850
  24. }

如果增删操作比较多的话，可以使用 LinkedList ，LinkedList 增删操作速度比较快。

如果需要线程安全的话，可以使用 JDK 集合中的工具类 Collections 提供一个方法 synchronizedList 可以将线程不安全的 List 集合变成线程安全的集合对象，如下所示。

  1. public static void main(String[] args) throws InterruptedException {
  3.     LinkedList<String> list = new LinkedList<>();
  4.     // 封装成线程安全的集合
  5.     List<String> synchronizedList = Collections.synchronizedList(list);
  7.     Thread thread1 = new Thread(() -> {
  8.       for (int i = 0; i < 1000; i++) {
  9.         synchronizedList.add(Thread.currentThread().getName() + i);
  10.       }
  11.     }, "Thread01");
  12.     thread1.start();
  14.     Thread thread2 = new Thread(() -> {
  15.       for (int i = 0; i < 1000; i++) {
  16.         synchronizedList.add(Thread.currentThread().getName() + i);
  17.       }
  18.     }, "Thread02");
  19.     thread2.start();
  21.     thread1.join();
  22.     thread2.join();
  24.     System.out.println(synchronizedList.size());
  26.  }

3.2 LinkedList 优缺点

  • 优点：增删操作速度快，不仅有头部和尾部双指针，可以根据要操作的下标靠近哪边，从而决定从哪一边开始遍历找到指定的下标。找到位置后，删除和插入操作的时间复杂度为 O(1) 。
  • 缺点：不支持快速随机访问，相对 ArrayList 比较慢，但也不是决定的，取决于列表的长度，以及访问的下标位置。

3.3 使用迭代器 Iterator 过程中，可以增删元素吗？

通过源码分析，在获取集合的迭代器方法中，返回的是 AbstractList 抽象类中定义的 ListItr 迭代器对象，在他的父类 Itr 中持有变量 expectedModCount ，在初始化迭代器对象时这个变量的值被赋予此时链表中的操作次数 modCount 。在迭代获取元素时，会检查这两变量是否相等，不相等则抛出并发修改异常。所以不支持在使用迭代器的过程中，对原链表进行增删改操作。但是可以调用迭代器的增删操作。

  1. private class ListItr extends Itr implements ListIterator<E> {
  2.     ListItr(int index) {
  3.         cursor = index;
  4.     }
  6.     public boolean hasPrevious() {
  7.         return cursor != 0;
  8.     }
  10.     public E previous() {
  11.         checkForComodification();
  12.         try {
  13.             int i = cursor - 1;
  14.             E previous = get(i);
  15.             lastRet = cursor = i;
  16.             return previous;
  17.         } catch (IndexOutOfBoundsException e) {
  18.             checkForComodification();
  19.             throw new NoSuchElementException();
  20.         }
  21.     }
  23.     public int nextIndex() {
  24.         return cursor;
  25.     }
  27.     public int previousIndex() {
  28.         return cursor-1;
  29.     }
  31.     public void set(E e) {
  32.         if (lastRet < 0)
  33.             throw new IllegalStateException();
  34.         checkForComodification();
  36.         try {
  37.             AbstractList.this.set(lastRet, e);
  38.             expectedModCount = modCount;
  39.         } catch (IndexOutOfBoundsException ex) {
  40.             throw new ConcurrentModificationException();
  41.         }
  42.     }
  44.     public void add(E e) {
  45.         checkForComodification();
  47.         try {
  48.             int i = cursor;
  49.             AbstractList.this.add(i, e);
  50.             lastRet = -1;
  51.             cursor = i + 1;
  52.             expectedModCount = modCount;
  53.         } catch (IndexOutOfBoundsException ex) {
  54.             throw new ConcurrentModificationException();
  55.         }
  56.     }
  57. }
  58. private class Itr implements Iterator<E> {
  59.     /**
  60.      * Index of element to be returned by subsequent call to next.
  61.      */
  62.     int cursor = 0;
  64.     /**
  65.      * Index of element returned by most recent call to next or
  66.      * previous.  Reset to -1 if this element is deleted by a call
  67.      * to remove.
  68.      */
  69.     int lastRet = -1;
  71.     /**
  72.      * The modCount value that the iterator believes that the backing
  73.      * List should have.  If this expectation is violated, the iterator
  74.      * has detected concurrent modification.
  75.      */
  76.     int expectedModCount = modCount;
  78.     public boolean hasNext() {
  79.         return cursor != size();
  80.     }
  82.     public E next() {
  83.         checkForComodification();
  84.         try {
  85.             int i = cursor;
  86.             E next = get(i);
  87.             lastRet = i;
  88.             cursor = i + 1;
  89.             return next;
  90.         } catch (IndexOutOfBoundsException e) {
  91.             checkForComodification();
  92.             throw new NoSuchElementException();
  93.         }
  94.     }
  96.     public void remove() {
  97.         if (lastRet < 0)
  98.             throw new IllegalStateException();
  99.         checkForComodification();
  101.         try {
  102.             AbstractList.this.remove(lastRet);
  103.             if (lastRet < cursor)
  104.                 cursor--;
  105.             lastRet = -1;
  106.             expectedModCount = modCount;
  107.         } catch (IndexOutOfBoundsException e) {
  108.             throw new ConcurrentModificationException();
  109.         }
  110.     }
  112.     final void checkForComodification() {
  113.         if (modCount != expectedModCount)
  114.             throw new ConcurrentModificationException();
  115.     }
  116. }

3.4 LinkedList 可以存储 null 值吗？元素可以重复吗？

LinkedList 底层是由双向链表实现的，并且在添加元素的时候，没有对元素进行值校验，所以可以存储 null 值，并且存储的元素是可以重复的。

  1. public boolean add(E e) {
  2.     linkLast(e);
  3.     return true;
  4. }
  6. void linkLast(E e) {
  7.     final Node<E> l = last;
  8.     final Node<E> newNode = new Node<>(l, e, null);
  9.     last = newNode;
  10.     if (l == null)
  11.         first = newNode;
  12.     else
  13.         l.next = newNode;
  14.     size++;
  15.     modCount++;
  16. }

3.5 如何边遍历 ArrayList 元素，边删除指定元素？

不支持在遍历的同时对原链表进行操作，会抛出 ConcurrentModificationException 并发修改异常，前面我们提到使用迭代器 Iterator 遍历集合时，不能对集合进行增删操作（会导致 modCount 值变化）。应该使用 Iterator 类的 remove 方法。

  1. package com.chenpi;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  6. /**
  7.  * @author 陈皮
  8.  * @version 1.0
  9.  * @description
  10.  * @date 2022/3/1
  11.  */
  12. public class ChenPi {
  14.   public static void main(String[] args) {
  16.     LinkedList<String> list = new LinkedList<>();
  17.     list.add("Java");
  18.     list.add("C++");
  19.     list.add("Python");
  20.     list.add("Lua");
  22.     Iterator<String> iterator = list.iterator();
  23.     while (iterator.hasNext()) {
  24.       String next = iterator.next();
  25.       if ("C++".equals(next)) {
  26.         iterator.remove();
  27.         continue;
  28.       }
  29.       System.out.println(next);
  30.     }
  32.   }
  33. }
  35. // 输出结果如下
  36. Java
  37. Python
  38. Lua

点击关注，第一时间了解华为云新鲜技术~

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://huaweicloud.blog.csdn.net/article/details/123544371

内容来源于网络，如有侵权，请联系作者删除！

JavaLinkedList链表技术交流框架双向链表

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com