数据结构之LinkedList底层实现和原理详解

前言

日常开发中，集合是我们经常用到的一种数据结构，当然，集合也并不是一种，也没有所谓的最好的集合，只有最适合的;

成都创新互联是一家专注网站建设、网络营销策划、微信小程序定制开发、电子商务建设、网络推广、移动互联开发、研究、服务为一体的技术型公司。公司成立10年以来，已经为上1000家成都纯水机各业的企业公司提供互联网服务。现在，服务的上1000家客户与我们一路同行，见证我们的成长；未来，我们一起分享成功的喜悦。

当然作为高级程序员，我们不仅仅要会用，还要了解其中的原理;

今天我们就来聊聊LinkedList底层实现和原理

一、LinkedList介绍

 
 
 
   
  
  
  public class LinkedList   
  
  
      extends AbstractSequentialList   
  
  
      implements List, Deque, Cloneable, java.io.Serializable   
  
  
  {   
  
  
      //长度   
  
  
      transient int size = 0;   
  
  
      //指向头结点   
  
  
      transient Node first;   
  
  
      //指向尾结点   
  
  
      transient Node last;   
  
  
  }

1、LinkedList概述

LinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(stack);

这样看来，linkedList简直就是无敌的，当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(只是一个接口的名字);

关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)更好的性能;

LinkedList的实现方式决定了所有跟下表有关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装

2、数据结构

继承关系

 
 
 
   
  
  
  java.lang.Object    
  
  
      java.util.AbstractCollection    
  
  
          java.util.AbstractList    
  
  
              java.util.AbstractSequentialList    
  
  
                  java.util.LinkedList

实现接口

 
 
 
   
  
  
  Serializable, Cloneable, Iterable, Collection, Deque, List, Queue

基本属性

transient int size = 0; //LinkedList中存放的元素个数
transient Node first; //头节点
transient Node last; //尾节点
Collection 接口：Collection接口是所有集合类的根节点，Collection表示一种规则，所有实现了Collection接口的类遵循这种规则

继承的类与实现的接口

List 接口：List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合
AbstractCollection 类：Collection接口的骨架实现类，最小化实现了Collection接口所需要实现的工作量
AbstractList 类：List接口的骨架实现类，最小化实现了List接口所需要实现的工作量
Cloneable 接口：实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制，如果没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。正常情况下，实现了Cloneable接口的类会以公共方法重写Object.clone()
Serializable 接口：实现了该接口标示了类可以被序列化和反序列化，具体的查询序列化详解
Deque 接口：Deque定义了一个线性Collection，支持在两端插入和删除元素，Deque实际是“double ended queue(双端队列)”的简称，大多数Deque接口的实现都不会限制元素的数量，但是这个队列既支持有容量限制的实现，也支持没有容量限制的实现，比如LinkedList就是有容量限制的实现,其最大的容量为Integer.MAX_VALUE
AbstractSequentialList 类：提供了List接口的骨干实现，最大限度地减少了实现受“连续访问”数据存储(如链表)支持的此接口所需的工作，对于随机访问数据(如数组)，应该优先使用 AbstractList，而不是使用AbstractSequentailList类

二、底层源码分析

LinkedList是通过双向链表去实现的，既然是链表实现那么它的随机访问效率比ArrayList要低，顺序访问的效率要比较的高。每个节点都有一个前驱(之前前面节点的指针)和一个后继(指向后面节点的指针)

效果如下图：

源码标注如下：

 
 
 
   
  
  
  public class LinkedListextends AbstractSequentialList   
  
  
      implements List, Deque, Cloneable, java.io.Serializable   
  
  
  {   
  
  
      transient int size = 0;   //LinkedList中存放的元素个数   
  
  
      transient Node first;  //头节点   
  
  
      transient Node last;   //尾节点   
  
  
      //构造方法，创建一个空的列表   
  
  
      public LinkedList() {   
  
  
      }   
  
  
      //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作   
  
  
      public LinkedList(Collection c) {   
  
  
          this();   
  
  
          addAll(c);   
  
  
      }   
  
  
      //插入头节点   
  
  
      private void linkFirst(E e) {   
  
  
          final Node f = first;  //将头节点赋值给f节点   
  
  
          //new 一个新的节点，此节点的data = e , pre = null , next - > f    
  
  
          final Node newNode = new Node<>(null, e, f);   
  
  
          first = newNode; //将新创建的节点地址复制给first   
  
  
          if (f == null)  //f == null，表示此时LinkedList为空   
  
  
              last = newNode;  //将新创建的节点赋值给last   
  
  
          else   
  
  
              f.prev = newNode;  //否则f.前驱指向newNode   
  
  
          size++;   
  
  
          modCount++;   
  
  
      }   
  
  
      //插入尾节点   
  
  
      void linkLast(E e) {   
  
  
          final Node l = last;    
  
  
          final Node newNode = new Node<>(l, e, null);   
  
  
          last = newNode;   
  
  
          if (l == null)   
  
  
              first = newNode;   
  
  
          else   
  
  
              l.next = newNode;   
  
  
          size++;   
  
  
          modCount++;   
  
  
      }   
  
  
      //在succ节点前插入e节点，并修改各个节点之间的前驱后继   
  
  
      void linkBefore(E e, Node succ) {   
  
  
          // assert succ != null;   
  
  
          final Node pred = succ.prev;   
  
  
          final Node newNode = new Node<>(pred, e, succ);   
  
  
          succ.prev = newNode;   
  
  
          if (pred == null)   
  
  
              first = newNode;   
  
  
          else   
  
  
              pred.next = newNode;   
  
  
          size++;   
  
  
          modCount++;   
  
  
      }   
  
  
      //删除头节点   
  
  
      private E unlinkFirst(Node f) {   
  
  
          // assert f == first && f != null;   
  
  
          final E element = f.item;   
  
  
          final Node next = f.next;   
  
  
          f.item = null;   
  
  
          f.next = null; // help GC   
  
  
          first = next;   
  
  
          if (next == null)   
  
  
              last = null;   
  
  
          else   
  
  
              next.prev = null;   
  
  
          size--;   
  
  
          modCount++;   
  
  
          return element;   
  
  
      }   
  
  
      //删除尾节点   
  
  
      private E unlinkLast(Node l) {   
  
  
          // assert l == last && l != null;   
  
  
          final E element = l.item;   
  
  
          final Node prev = l.prev;   
  
  
          l.item = null;   
  
  
          l.prev = null; // help GC   
  
  
          last = prev;   
  
  
          if (prev == null)   
  
  
              first = null;   
  
  
          else   
  
  
              prev.next = null;   
  
  
          size--;   
  
  
          modCount++;   
  
  
          return element;   
  
  
      }   
  
  
      //删除指定节点   
  
  
      E unlink(Node x) {   
  
  
          // assert x != null;   
  
  
          final E element = x.item;   
  
  
          final Node next = x.next;  //获取指定节点的前驱   
  
  
          final Node prev = x.prev;  //获取指定节点的后继   
  
  
          if (prev == null) {   
  
  
              first = next;   //如果前驱为null, 说明此节点为头节点   
  
  
          } else {   
  
  
              prev.next = next;  //前驱结点的后继节点指向当前节点的后继节点   
  
  
              x.prev = null;     //当前节点的前驱置空   
  
  
          }   
  
  
          if (next == null) {    //如果当前节点的后继节点为null ,说明此节点为尾节点   
  
  
              last = prev;   
  
  
          } else {   
  
  
              next.prev = prev;  //当前节点的后继节点的前驱指向当前节点的前驱节点   
  
  
              x.next = null;     //当前节点的后继置空   
  
  
          }   
  
  
          x.item = null;     //当前节点的元素设置为null ,等待垃圾回收   
  
  
          size--;   
  
  
          modCount++;   
  
  
          return element;   
  
  
      }   
  
  
      //获取LinkedList中的第一个节点信息   
  
  
      public E getFirst() {   
  
  
          final Node f = first;   
  
  
          if (f == null)   
  
  
              throw new NoSuchElementException();   
  
  
          return f.item;   
  
  
      }   
  
  
      //获取LinkedList中的最后一个节点信息   
  
  
      public E getLast() {   
  
  
          final Node l = last;   
  
  
          if (l == null)   
  
  
              throw new NoSuchElementException();   
  
  
          return l.item;   
  
  
      }   
  
  
      //删除头节点   
  
  
      public E removeFirst() {   
  
  
          final Node f = first;   
  
  
          if (f == null)   
  
  
              throw new NoSuchElementException();   
  
  
          return unlinkFirst(f);   
  
  
      }   
  
  
      //删除尾节点   
  
  
      public E removeLast() {   
  
  
          final Node l = last;   
  
  
          if (l == null)   
  
  
              throw new NoSuchElementException();   
  
  
          return unlinkLast(l);   
  
  
      }   
  
  
      //将添加的元素设置为LinkedList的头节点   
  
  
      public void addFirst(E e) {   
  
  
          linkFirst(e);   
  
  
      }   
  
  
      //将添加的元素设置为LinkedList的尾节点   
  
  
      public void addLast(E e) {   
  
  
          linkLast(e);   
  
  
      }   
  
  
      //判断LinkedList是否包含指定的元素   
  
  
      public boolean contains(Object o) {   
  
  
          return indexOf(o) != -1;   
  
  
      }   
  
  
      //返回List中元素的数量   
  
  
      public int size() {   
  
  
          return size;   
  
  
      }   
  
  
      //在LinkedList的尾部添加元素   
  
  
      public boolean add(E e) {   
  
  
          linkLast(e);   
  
  
          return true;   
  
  
      }   
  
  
      //删除指定的元素   
  
  
      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;   
  
  
      }   
  
  
      //将集合中的元素添加到List中   
  
  
      public boolean addAll(Collection c) {   
  
  
          return addAll(size, c);   
  
  
      }   
  
  
      //将集合中的元素全部插入到List中，并从指定的位置开始   
  
  
      public boolean addAll(int index, Collection c) {   
  
  
          checkPositionIndex(index);   
  
  
          Object[] a = c.toArray();  //将集合转化为数组   
  
  
          int numNew = a.length;  //获取集合中元素的数量   
  
  
          if (numNew == 0)   //集合中没有元素，返回false   
  
  
              return false;   
  
  
          Node pred, succ;   
  
  
          if (index == size) {   
  
  
              succ = null;   
  
  
              pred = last;   
  
  
          } else {   
  
  
              succ = node(index); //获取位置为index的结点元素，并赋值给succ   
  
  
              pred = succ.prev;   
  
  
          }   
  
  
          for (Object o : a) {  //遍历数组进行插入操作。修改节点的前驱后继   
  
  
              @SuppressWarnings("unchecked") E e = (E) o;   
  
  
              Node newNode = new Node<>(pred, e, null);   
  
  
              if (pred == null)   
  
  
                  first = newNode;   
  
  
              else   
  
  
                  pred.next = newNode;   
  
  
              pred = newNode;   
  
  
          }   
  
  
          if (succ == null) {   
  
  
              last = pred;   
  
  
          } else {   
  
  
              pred.next = succ;   
  
  
              succ.prev = pred;   
  
  
          }   
  
  
          size += numNew;   
  
  
          modCount++;   
  
  
          return true;   
  
  
      }   
  
  
      //删除List中所有的元素   
  
  
      public void clear() {   
  
  
          // Clearing all of the links between nodes is "unnecessary", but:   
  
  
          // - helps a generational GC if the discarded nodes inhabit   
  
  
          //   more than one generation   
  
  
          // - is sure to free memory even if there is a reachable Iterator   
  
  
          for (Node x = first; x != null; ) {   
  
  
              Node next = x.next;   
  
  
              x.item = null;   
  
  
              x.next = null;   
  
  
              x.prev = null;   
  
  
              x = next;   
  
  
          }   
  
  
          first = last = null;   
  
  
          size = 0;   
  
  
          modCount++;   
  
  
      }   
  
  
      //获取指定位置的元素   
  
  
      public E get(int index) {   
  
  
          checkElementIndex(index);   
  
  
          return node(index).item;   
  
  
      }   
  
  
      //将节点防止在指定的位置   
  
  
      public E set(int index, E element) {   
  
  
          checkElementIndex(index);   
  
  
          Node x = node(index);   
  
  
          E oldVal = x.item;   
  
  
          x.item = element;   
  
  
          return oldVal;   
  
  
      }   
  
  
      //将节点放置在指定的位置   
  
  
      public void add(int index, E element) {   
  
  
          checkPositionIndex(index);   
  
  
          if (index == size)   
  
  
              linkLast(element);   
  
  
          else   
  
  
              linkBefore(element, node(index));   
  
  
      }   
  
  
      //删除指定位置的元素   
  
  
      public E remove(int index) {   
  
  
          checkElementIndex(index);   
  
  
          return unlink(node(index));   
  
  
      }   
  
  
      //判断索引是否合法   
  
  
      private boolean isElementIndex(int index) {   
  
  
          return index >= 0 && index < size;   
  
  
      }   
  
  
      //判断位置是否合法   
  
  
      private boolean isPositionIndex(int index) {   
  
  
          return index >= 0 && index <= size;   
  
  
      }   
  
  
      //索引溢出信息   
  
  
      private String outOfBoundsMsg(int index) {   
  
  
          return "Index: "+index+", Size: "+size;   
  
  
      }   
  
  
      //检查节点是否合法   
  
  
      private void checkElementIndex(int index) {   
  
  
          if (!isElementIndex(index))   
  
  
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));   
  
  
      }   
  
  
      //检查位置是否合法   
  
  
      private void checkPositionIndex(int index) {   
  
  
          if (!isPositionIndex(index))   
  
  
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));   
  
  
      }   
  
  
      //返回指定位置的节点信息   
  
  
      //LinkedList无法随机访问，只能通过遍历的方式找到相应的节点   
  
  
      //为了提高效率，当前位置首先和元素数量的中间位置开始判断，小于中间位置，   
  
  
      //从头节点开始遍历，大于中间位置从尾节点开始遍历   
  
  
      Node node(int index) {   
  
  
          // assert isElementIndex(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;   
  
  
          }   
  
  
      }   
  
  
      //返回第一次出现指定元素的位置   
  
  
      public int indexOf(Object o) {   
  
  
          int index = 0;   
  
  
          if (o == null) {   
  
  
              for (Node x = first; x != null; x = x.next) {   
  
  
                  if (x.item == null)   
  
  
                      return index;   
  
  
                  index++;   
  
  
              }   
  
  
          } else {   
  
  
              for (Node x = first; x != null; x = x.next) {   
  
  
                  if (o.equals(x.item))   
  
  
                      return index;   
  
  
                  index++;   
  
  
              }   
  
  
          }   
  
  
          return -1;   
  
  
      }   
  
  
      //返回最后一次出现元素的位置   
  
  
      public int lastIndexOf(Object o) {   
  
  
          int index = size;   
  
  
          if (o == null) {   
  
  
              for (Node x = last; x != null; x = x.prev) {   
  
  
                  index--;   
  
  
                  if (x.item == null)   
  
  
                      return index;   
  
  
              }   
  
  
          } else {   
  
  
              for (Node x = last; x != null; x = x.prev) {   
  
  
                  index--;   
  
  
                  if (o.equals(x.item))   
  
  
                      return index;   
  
  
              }   
  
  
          }   
  
  
          return -1;   
  
  
      }   
  
  
      //弹出第一个元素的值   
  
  
      public E peek() {   
  
  
          final Node f = first;   
  
  
          return (f == null) ? null : f.item;   
  
  
      }   
  
  
      //获取第一个元素   
  
  
      public E element() {   
  
  
          return getFirst();   
  
  
      }   
  
  
      //弹出第一元素，并删除   
  
  
      public E poll() {   
  
  
          final Node f = first;   
  
  
          return (f == null) ? null : unlinkFirst(f);   
  
  
      }   
  
  
      //删除第一个元素   
  
  
      public E remove() {   
  
  
          return removeFirst();   
  
  
      }   
  
  
      //添加到尾部   
  
  
      public boolean offer(E e) {   
  
  
          return add(e);   
  
  
      }   
  
  
      //添加到头部   
  
  
      public boolean offerFirst(E e) {   
  
  
          addFirst(e);   
  
  
          return true;   
  
  
      }   
  
  
      //插入到最后一个元素   
  
  
      public boolean offerLast(E e) {   
  
  
          addLast(e);   
  
  
          return true;   
  
  
      }   
  
  
      //队列操作   
  
  
      //尝试弹出第一个元素，但是不删除元素   
  
  
      public E peekFirst() {   
  
  
          final Node f = first;   
  
  
          return (f == null) ? null : f.item;   
  
  
       }   
  
  
      //队列操作   
  
  
      //尝试弹出最后一个元素，不删除   
  
  
      public E peekLast() {   
  
  
          final Node l = last;   
  
  
          return (l == null) ? null : l.item;   
  
  
      }   
  
  
      //弹出第一个元素，并删除   
  
  
      public E pollFirst() {   
  
  
          final Node f = first;   
  
  
          return (f == null) ? null : unlinkFirst(f);   
  
  
      }   
  
  
      //弹出最后一个元素，并删除   
  
  
      public E pollLast() {   
  
  
          final Node l = last;   
  
  
          return (l == null) ? null : unlinkLast(l);   
  
  
      }   
  
  
      //如队列，添加到头部   
  
  
      public void push(E e) {   
  
  
          addFirst(e);   
  
  
      }   
  
  
      //出队列删除第一个节点   
  
  
      public E pop() {   
  
  
          return removeFirst();   
  
  
      }   
  
  
     //删除指定元素第一次出现的位置   
  
  
      public boolean removeFirstOccurrence(Object o) {   
  
  
          return remove(o);   
  
  
      }   
  
  
      //删除指定元素最后一次出现的位置   
  
  
      public boolean removeLastOccurrence(Object o) {   
  
  
          if (o == null) {   
  
  
              for (Node x = last; x != null; x = x.prev) {   
  
  
                  if (x.item == null) {   
  
  
                      unlink(x);   
  
  
                      return true;   
  
  
                  }   
  
  
              }   
  
  
          } else {   
  
  
              for (Node x = last; x != null; x = x.prev) {   
  
  
               

            文章标题：数据结构之LinkedList底层实现和原理详解            

            网站路径：http://hnjierui.cn/article/cdicepo.html

网站建设资讯

数据结构之LinkedList底层实现和原理详解

前言

一、LinkedList介绍

1、LinkedList概述

2、数据结构

二、底层源码分析

其他资讯