转：【Java集合源码剖析】LinkedList源码剖析

2022-06-14 20:29:19

转载请注明出处：http://blog.csdn.net/ns_code/article/details/35787253

 

您好，我正在参加CSDN博文大赛，如果您喜欢我的文章，希望您能帮我投一票，谢谢！

投票地址：http://vote.blog.csdn.net/Article/Details?articleid=35568011

LinkedList简介

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

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

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

LinkedList源码剖析

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

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

几点总结

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

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

转：【Java集合源码剖析】LinkedList源码剖析

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

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

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

5、注意源码中的Entry<E> entry(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。

6、注意链表类对应的数据结构Entry。如下;

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

7、LinkedList是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）。
    8、要注意源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。

上一篇：运行PHP


下一篇：Deformity PHP Webshell、Webshell Hidden Learning