LinkedList源码剖析

喜欢ヅ旅行 2022-07-13 11:44 294阅读 0赞

1. LinkedList简介

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。

LinkedList同样是非线程安全的，只在单线程下适合使用。

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

2. LinkedList源码剖析

LinkedList的源码如下（加入了比较详细的注释）

  1. package java.util;    
  3. public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {     
  4.     // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。 
  5.     private transient Entry<E> header = new Entry<E>(null, null, null);    
  7.     // LinkedList中元素个数 
  8.     private transient int size = 0;    
  10.     // 默认构造函数：创建一个空的链表 
  11.     public LinkedList() {    
  12.         header.next = header.previous = header;    
  13.     }    
  15.     // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList 
  16.     public LinkedList(Collection<? extends E> c) {    
  17.         this();    
  18.         addAll(c);    
  19.     }    
  21.     // 获取LinkedList的第一个元素 
  22.     public E getFirst() {    
  23.         if (size==0)    
  24.             throw new NoSuchElementException();    
  26.         // 链表的表头header中不包含数据。 
  27.         // 这里返回header所指下一个节点所包含的数据。 
  28.         return header.next.element;    
  29.     }    
  31.     // 获取LinkedList的最后一个元素 
  32.     public E getLast()  {    
  33.         if (size==0)    
  34.             throw new NoSuchElementException();    
  36.         // 由于LinkedList是双向链表；而表头header不包含数据。 
  37.         // 因而，这里返回表头header的前一个节点所包含的数据。 
  38.         return header.previous.element;    
  39.     }    
  41.     // 删除LinkedList的第一个元素 
  42.     public E removeFirst() {    
  43.         return remove(header.next);    
  44.     }    
  46.     // 删除LinkedList的最后一个元素 
  47.     public E removeLast() {    
  48.         return remove(header.previous);    
  49.     }    
  51.     // 将元素添加到LinkedList的起始位置 
  52.     public void addFirst(E e) {    
  53.         addBefore(e, header.next);    
  54.     }    
  56.     // 将元素添加到LinkedList的结束位置 
  57.     public void addLast(E e) {    
  58.         addBefore(e, header);    
  59.     }    
  61.     // 判断LinkedList是否包含元素(o) 
  62.     public boolean contains(Object o) {    
  63.         return indexOf(o) != -1;    
  64.     }    
  66.     // 返回LinkedList的大小 
  67.     public int size() {    
  68.         return size;    
  69.     }    
  71.     // 将元素(E)添加到LinkedList中 
  72.     public boolean add(E e) {    
  73.         // 将节点(节点数据是e)添加到表头(header)之前。 
  74.         // 即，将节点添加到双向链表的末端。 
  75.         addBefore(e, header);    
  76.         return true;    
  77.     }    
  79.     // 从LinkedList中删除元素(o) 
  80.     // 从链表开始查找，如存在元素(o)则删除该元素并返回true； 
  81.     // 否则，返回false。 
  82.     public boolean remove(Object o) {    
  83.         if (o==null) {    
  84.             // 若o为null的删除情况 
  85.             for (Entry<E> e = header.next; e != header; e = e.next) {    
  86.                 if (e.element==null) {    
  87.                     remove(e);    
  88.                     return true;    
  89.                 }    
  90.             }    
  91.         } else {    
  92.             // 若o不为null的删除情况 
  93.             for (Entry<E> e = header.next; e != header; e = e.next) {    
  94.                 if (o.equals(e.element)) {    
  95.                     remove(e);    
  96.                     return true;    
  97.                 }    
  98.             }    
  99.         }    
  100.         return false;    
  101.     }    
  103.     // 将“集合(c)”添加到LinkedList中。 
  104.     // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。 
  105.     public boolean addAll(Collection<? extends E> c) {    
  106.         return addAll(size, c);    
  107.     }    
  109.     // 从双向链表的index开始，将“集合(c)”添加到双向链表中。 
  110.     public boolean addAll(int index, Collection<? extends E> c) {    
  111.         if (index < 0 || index > size)    
  112.             throw new IndexOutOfBoundsException("Index: "+index+    
  113.                                                 ", Size: "+size);    
  114.         Object[] a = c.toArray();    
  115.         // 获取集合的长度 
  116.         int numNew = a.length;    
  117.         if (numNew==0)    
  118.             return false;    
  119.         modCount++;    
  121.         // 设置“当前要插入节点的后一个节点” 
  122.         Entry<E> successor = (index==size ? header : entry(index));    
  123.         // 设置“当前要插入节点的前一个节点” 
  124.         Entry<E> predecessor = successor.previous;    
  125.         // 将集合(c)全部插入双向链表中 
  126.         for (int i=0; i<numNew; i++) {    
  127.             Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);    
  128.             predecessor.next = e;    
  129.             predecessor = e;    
  130.         }    
  131.         successor.previous = predecessor;    
  133.         // 调整LinkedList的实际大小 
  134.         size += numNew;    
  135.         return true;    
  136.     }    
  138.     // 清空双向链表 
  139.     public void clear() {    
  140.         Entry<E> e = header.next;    
  141.         // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作： 
  142.         // (01) 设置前一个节点为null 
  143.         // (02) 设置当前节点的内容为null 
  144.         // (03) 设置后一个节点为“新的当前节点” 
  145.         while (e != header) {    
  146.             Entry<E> next = e.next;    
  147.             e.next = e.previous = null;    
  148.             e.element = null;    
  149.             e = next;    
  150.         }    
  151.         header.next = header.previous = header;    
  152.         // 设置大小为0 
  153.         size = 0;    
  154.         modCount++;    
  155.     }    
  157.     // 返回LinkedList指定位置的元素 
  158.     public E get(int index) {    
  159.         return entry(index).element;    
  160.     }    
  162.     // 设置index位置对应的节点的值为element 
  163.     public E set(int index, E element) {    
  164.         Entry<E> e = entry(index);    
  165.         E oldVal = e.element;    
  166.         e.element = element;    
  167.         return oldVal;    
  168.     }    
  170.     // 在index前添加节点，且节点的值为element 
  171.     public void add(int index, E element) {    
  172.         addBefore(element, (index==size ? header : entry(index)));    
  173.     }    
  175.     // 删除index位置的节点 
  176.     public E remove(int index) {    
  177.         return remove(entry(index));    
  178.     }    
  180.     // 获取双向链表中指定位置的节点 
  181.     private Entry<E> entry(int index) {    
  182.         if (index < 0 || index >= size)    
  183.             throw new IndexOutOfBoundsException("Index: "+index+    
  184.                                                 ", Size: "+size);    
  185.         Entry<E> e = header;    
  186.         // 获取index处的节点。 
  187.         // 若index < 双向链表长度的1/2,则从前先后查找; 
  188.         // 否则，从后向前查找。 
  189.         if (index < (size >> 1)) {    
  190.             for (int i = 0; i <= index; i++)    
  191.                 e = e.next;    
  192.         } else {    
  193.             for (int i = size; i > index; i--)    
  194.                 e = e.previous;    
  195.         }    
  196.         return e;    
  197.     }    
  199.     // 从前向后查找，返回“值为对象(o)的节点对应的索引” 
  200.     // 不存在就返回-1 
  201.     public int indexOf(Object o) {    
  202.         int index = 0;    
  203.         if (o==null) {    
  204.             for (Entry e = header.next; e != header; e = e.next) {    
  205.                 if (e.element==null)    
  206.                     return index;    
  207.                 index++;    
  208.             }    
  209.         } else {    
  210.             for (Entry e = header.next; e != header; e = e.next) {    
  211.                 if (o.equals(e.element))    
  212.                     return index;    
  213.                 index++;    
  214.             }    
  215.         }    
  216.         return -1;    
  217.     }    
  219.     // 从后向前查找，返回“值为对象(o)的节点对应的索引” 
  220.     // 不存在就返回-1 
  221.     public int lastIndexOf(Object o) {    
  222.         int index = size;    
  223.         if (o==null) {    
  224.             for (Entry e = header.previous; e != header; e = e.previous) {    
  225.                 index--;    
  226.                 if (e.element==null)    
  227.                     return index;    
  228.             }    
  229.         } else {    
  230.             for (Entry e = header.previous; e != header; e = e.previous) {    
  231.                 index--;    
  232.                 if (o.equals(e.element))    
  233.                     return index;    
  234.             }    
  235.         }    
  236.         return -1;    
  237.     }    
  239.     // 返回第一个节点 
  240.     // 若LinkedList的大小为0,则返回null 
  241.     public E peek() {    
  242.         if (size==0)    
  243.             return null;    
  244.         return getFirst();    
  245.     }    
  247.     // 返回第一个节点 
  248.     // 若LinkedList的大小为0,则抛出异常 
  249.     public E element() {    
  250.         return getFirst();    
  251.     }    
  253.     // 删除并返回第一个节点 
  254.     // 若LinkedList的大小为0,则返回null 
  255.     public E poll() {    
  256.         if (size==0)    
  257.             return null;    
  258.         return removeFirst();    
  259.     }    
  261.     // 将e添加双向链表末尾 
  262.     public boolean offer(E e) {    
  263.         return add(e);    
  264.     }    
  266.     // 将e添加双向链表开头 
  267.     public boolean offerFirst(E e) {    
  268.         addFirst(e);    
  269.         return true;    
  270.     }    
  272.     // 将e添加双向链表末尾 
  273.     public boolean offerLast(E e) {    
  274.         addLast(e);    
  275.         return true;    
  276.     }    
  278.     // 返回第一个节点 
  279.     // 若LinkedList的大小为0,则返回null 
  280.     public E peekFirst() {    
  281.         if (size==0)    
  282.             return null;    
  283.         return getFirst();    
  284.     }    
  286.     // 返回最后一个节点 
  287.     // 若LinkedList的大小为0,则返回null 
  288.     public E peekLast() {    
  289.         if (size==0)    
  290.             return null;    
  291.         return getLast();    
  292.     }    
  294.     // 删除并返回第一个节点 
  295.     // 若LinkedList的大小为0,则返回null 
  296.     public E pollFirst() {    
  297.         if (size==0)    
  298.             return null;    
  299.         return removeFirst();    
  300.     }    
  302.     // 删除并返回最后一个节点 
  303.     // 若LinkedList的大小为0,则返回null 
  304.     public E pollLast() {    
  305.         if (size==0)    
  306.             return null;    
  307.         return removeLast();    
  308.     }    
  310.     // 将e插入到双向链表开头 
  311.     public void push(E e) {    
  312.         addFirst(e);    
  313.     }    
  315.     // 删除并返回第一个节点 
  316.     public E pop() {    
  317.         return removeFirst();    
  318.     }    
  320.     // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点 
  321.     // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点 
  322.     public boolean removeFirstOccurrence(Object o) {    
  323.         return remove(o);    
  324.     }    
  326.     // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点 
  327.     // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点 
  328.     public boolean removeLastOccurrence(Object o) {    
  329.         if (o==null) {    
  330.             for (Entry<E> e = header.previous; e != header; e = e.previous) {    
  331.                 if (e.element==null) {    
  332.                     remove(e);    
  333.                     return true;    
  334.                 }    
  335.             }    
  336.         } else {    
  337.             for (Entry<E> e = header.previous; e != header; e = e.previous) {    
  338.                 if (o.equals(e.element)) {    
  339.                     remove(e);    
  340.                     return true;    
  341.                 }    
  342.             }    
  343.         }    
  344.         return false;    
  345.     }    
  347.     // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器) 
  348.     public ListIterator<E> listIterator(int index) {    
  349.         return new ListItr(index);    
  350.     }    
  352.     // List迭代器 
  353.     private class ListItr implements ListIterator<E> {     
  354.         // 上一次返回的节点 
  355.         private Entry<E> lastReturned = header;    
  356.         // 下一个节点 
  357.         private Entry<E> next;    
  358.         // 下一个节点对应的索引值 
  359.         private int nextIndex;    
  360.         // 期望的改变计数。用来实现fail-fast机制。 
  361.         private int expectedModCount = modCount;    
  363.         // 构造函数。 
  364.         // 从index位置开始进行迭代 
  365.         ListItr(int index) {    
  366.             // index的有效性处理 
  367.             if (index < 0 || index > size)    
  368.                 throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);    
  369.             // 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找； 
  370.             // 否则，从最后一个元素往前查找。 
  371.             if (index < (size >> 1)) {    
  372.                 next = header.next;    
  373.                 for (nextIndex=0; nextIndex<index; nextIndex++)    
  374.                     next = next.next;    
  375.             } else {    
  376.                 next = header;    
  377.                 for (nextIndex=size; nextIndex>index; nextIndex--)    
  378.                     next = next.previous;    
  379.             }    
  380.         }    
  382.         // 是否存在下一个元素 
  383.         public boolean hasNext() {    
  384.             // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。 
  385.             return nextIndex != size;    
  386.         }    
  388.         // 获取下一个元素 
  389.         public E next() {    
  390.             checkForComodification();    
  391.             if (nextIndex == size)    
  392.                 throw new NoSuchElementException();    
  394.             lastReturned = next;    
  395.             // next指向链表的下一个元素 
  396.             next = next.next;    
  397.             nextIndex++;    
  398.             return lastReturned.element;    
  399.         }    
  401.         // 是否存在上一个元素 
  402.         public boolean hasPrevious() {    
  403.             // 通过元素索引是否等于0，来判断是否达到开头。 
  404.             return nextIndex != 0;    
  405.         }    
  407.         // 获取上一个元素 
  408.         public E previous() {    
  409.             if (nextIndex == 0)    
  410.             throw new NoSuchElementException();    
  412.             // next指向链表的上一个元素 
  413.             lastReturned = next = next.previous;    
  414.             nextIndex--;    
  415.             checkForComodification();    
  416.             return lastReturned.element;    
  417.         }    
  419.         // 获取下一个元素的索引 
  420.         public int nextIndex() {    
  421.             return nextIndex;    
  422.         }    
  424.         // 获取上一个元素的索引 
  425.         public int previousIndex() {    
  426.             return nextIndex-1;    
  427.         }    
  429.         // 删除当前元素。 
  430.         // 删除双向链表中的当前节点 
  431.         public void remove() {    
  432.             checkForComodification();    
  433.             Entry<E> lastNext = lastReturned.next;    
  434.             try {    
  435.                 LinkedList.this.remove(lastReturned);    
  436.             } catch (NoSuchElementException e) {    
  437.                 throw new IllegalStateException();    
  438.             }    
  439.             if (next==lastReturned)    
  440.                 next = lastNext;    
  441.             else   
  442.                 nextIndex--;    
  443.             lastReturned = header;    
  444.             expectedModCount++;    
  445.         }    
  447.         // 设置当前节点为e 
  448.         public void set(E e) {    
  449.             if (lastReturned == header)    
  450.                 throw new IllegalStateException();    
  451.             checkForComodification();    
  452.             lastReturned.element = e;    
  453.         }    
  455.         // 将e添加到当前节点的前面 
  456.         public void add(E e) {    
  457.             checkForComodification();    
  458.             lastReturned = header;    
  459.             addBefore(e, next);    
  460.             nextIndex++;    
  461.             expectedModCount++;    
  462.         }    
  464.         // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。 
  465.         final void checkForComodification() {    
  466.             if (modCount != expectedModCount)    
  467.             throw new ConcurrentModificationException();    
  468.         }    
  469.     }    
  471.     // 双向链表的节点所对应的数据结构。 
  472.     // 包含3部分：上一节点，下一节点，当前节点值。 
  473.     private static class Entry<E> {     
  474.         // 当前节点所包含的值 
  475.         E element;    
  476.         // 下一个节点 
  477.         Entry<E> next;    
  478.         // 上一个节点 
  479.         Entry<E> previous;    
  481.         /** * 链表节点的构造函数。 * 参数说明： * element —— 节点所包含的数据 * next —— 下一个节点 * previous —— 上一个节点 */   
  482.         Entry(E element, Entry<E> next, Entry<E> previous) {    
  483.             this.element = element;    
  484.             this.next = next;    
  485.             this.previous = previous;    
  486.         }    
  487.     }    
  489.     // 将节点(节点数据是e)添加到entry节点之前。 
  490.     private Entry<E> addBefore(E e, Entry<E> entry) {    
  491.         // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e 
  492.         Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);    
  493.         newEntry.previous.next = newEntry;    
  494.         newEntry.next.previous = newEntry;    
  495.         // 修改LinkedList大小 
  496.         size++;    
  497.         // 修改LinkedList的修改统计数：用来实现fail-fast机制。 
  498.         modCount++;    
  499.         return newEntry;    
  500.     }    
  502.     // 将节点从链表中删除 
  503.     private E remove(Entry<E> e) {    
  504.         if (e == header)    
  505.             throw new NoSuchElementException();    
  507.         E result = e.element;    
  508.         e.previous.next = e.next;    
  509.         e.next.previous = e.previous;    
  510.         e.next = e.previous = null;    
  511.         e.element = null;    
  512.         size--;    
  513.         modCount++;    
  514.         return result;    
  515.     }    
  517.     // 反向迭代器 
  518.     public Iterator<E> descendingIterator() {    
  519.         return new DescendingIterator();    
  520.     }    
  522.     // 反向迭代器实现类。 
  523.     private class DescendingIterator implements Iterator {     
  524.         final ListItr itr = new ListItr(size());    
  525.         // 反向迭代器是否下一个元素。 
  526.         // 实际上是判断双向链表的当前节点是否达到开头 
  527.         public boolean hasNext() {    
  528.             return itr.hasPrevious();    
  529.         }    
  530.         // 反向迭代器获取下一个元素。 
  531.         // 实际上是获取双向链表的前一个节点 
  532.         public E next() {    
  533.             return itr.previous();    
  534.         }    
  535.         // 删除当前节点 
  536.         public void remove() {    
  537.             itr.remove();    
  538.         }    
  539.     }    
  542.     // 返回LinkedList的Object[]数组 
  543.     public Object[] toArray() {    
  544.     // 新建Object[]数组 
  545.     Object[] result = new Object[size];    
  546.         int i = 0;    
  547.         // 将链表中所有节点的数据都添加到Object[]数组中 
  548.         for (Entry<E> e = header.next; e != header; e = e.next)    
  549.             result[i++] = e.element;    
  550.     return result;    
  551.     }    
  553.     // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型 
  554.     public <T> T[] toArray(T[] a) {    
  555.         // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素) 
  556.         // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。 
  557.         if (a.length < size)    
  558.             a = (T[])java.lang.reflect.Array.newInstance(    
  559.                                 a.getClass().getComponentType(), size);    
  560.         // 将链表中所有节点的数据都添加到数组a中 
  561.         int i = 0;    
  562.         Object[] result = a;    
  563.         for (Entry<E> e = header.next; e != header; e = e.next)    
  564.             result[i++] = e.element;    
  566.         if (a.length > size)    
  567.             a[size] = null;    
  569.         return a;    
  570.     }    
  573.     // 克隆函数。返回LinkedList的克隆对象。 
  574.     public Object clone() {    
  575.         LinkedList<E> clone = null;    
  576.         // 克隆一个LinkedList克隆对象 
  577.         try {    
  578.             clone = (LinkedList<E>) super.clone();    
  579.         } catch (CloneNotSupportedException e) {    
  580.             throw new InternalError();    
  581.         }    
  583.         // 新建LinkedList表头节点 
  584.         clone.header = new Entry<E>(null, null, null);    
  585.         clone.header.next = clone.header.previous = clone.header;    
  586.         clone.size = 0;    
  587.         clone.modCount = 0;    
  589.         // 将链表中所有节点的数据都添加到克隆对象中 
  590.         for (Entry<E> e = header.next; e != header; e = e.next)    
  591.             clone.add(e.element);    
  593.         return clone;    
  594.     }    
  596.     // java.io.Serializable的写入函数 
  597.     // 将LinkedList的“容量，所有的元素值”都写入到输出流中 
  598.     private void writeObject(java.io.ObjectOutputStream s)    
  599.         throws java.io.IOException {    
  600.         // Write out any hidden serialization magic 
  601.         s.defaultWriteObject();    
  603.         // 写入“容量” 
  604.         s.writeInt(size);    
  606.         // 将链表中所有节点的数据都写入到输出流中 
  607.         for (Entry e = header.next; e != header; e = e.next)    
  608.             s.writeObject(e.element);    
  609.     }    
  611.     // java.io.Serializable的读取函数：根据写入方式反向读出 
  612.     // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出 
  613.     private void readObject(java.io.ObjectInputStream s)    
  614.         throws java.io.IOException, ClassNotFoundException {    
  615.         // Read in any hidden serialization magic 
  616.         s.defaultReadObject();    
  618.         // 从输入流中读取“容量” 
  619.         int size = s.readInt();    
  621.         // 新建链表表头节点 
  622.         header = new Entry<E>(null, null, null);    
  623.         header.next = header.previous = header;    
  625.         // 从输入流中将“所有的元素值”并逐个添加到链表中 
  626.         for (int i=0; i<size; i++)    
  627.             addBefore((E)s.readObject(), header);    
  628.     }    
  630. }

3. 几点总结

关于LinkedList的源码，给出几点比较重要的总结：

1、从源码中很明显可以看出，LinkedList的实现是基于双向循环链表的，且头结点中不存放数据，如下图;

20140629153056171

2、注意两个不同的构造方法。无参构造方法直接建立一个仅包含head节点的空链表，包含Collection的构造方法，先调用无参构造方法建立一个空链表，然后将Collection中的数据加入到链表的尾部后面。

3、在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。

4、LinkedList是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法。

5、注意源码中的Entry entry(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index

  1. // 双向链表的节点所对应的数据结构。 
  2. // 包含3部分：上一节点，下一节点，当前节点值。 
  3. private static class Entry<E> {     
  4.     // 当前节点所包含的值 
  5.     E element;    
  6.     // 下一个节点 
  7.     Entry<E> next;    
  8.     // 上一个节点 
  9.     Entry<E> previous;    
  11.     /** * 链表节点的构造函数。 * 参数说明： * element —— 节点所包含的数据 * next —— 下一个节点 * previous —— 上一个节点 */   
  12.     Entry(E element, Entry<E> next, Entry<E> previous) {    
  13.         this.element = element;    
  14.         this.next = next;    
  15.         this.previous = previous;    
  16.     }    
  17. }

7、LinkedList是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）。

8、要注意源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。

原文链接：https://github.com/GeniusVJR/LearningNotes

数据结构与算法

发表评论

表情：
评论列表 （有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LinkedList源码剖析

    1. LinkedList简介 LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。

    喜欢ヅ旅行喜欢ヅ旅行/ 0 赞/ 295 阅读

    相关 LinkedList源码剖析

    简介 LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。 由于是链表结构,Linke

    小咪咪小咪咪/ 0 赞/ 324 阅读

    相关 LinkedList源码

    LinkedList底层是基于双向链表，链表在内存中不是连续的，而是通过引用来关联所有的元素，所以链表的优点在于添加和删除元素比较快，因为只是移动指针，并且不需要判断是否需要扩

    布满荆棘的人生布满荆棘的人生/ 0 赞/ 420 阅读