Gnawing JDK source code (6): LinkedList

Giant tortoise 2020-11-09 22:19:19
gnawing jdk source code linkedlist


Preface

I've written a few articles about Java A collection of articles :

Let's introduce another class of containers today :LinkedList.

Text

LinkedList and ArrayList It's a collection List Implementation class of , Although compared with ArrayList, There are not many scenarios for its use , But it's also useful when , So next , Let's meet it .

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{// The bottom layer is a two-way linked list
// Element quantity
transient int size = 0;
// The first node
transient Node<E> first;
// The last node
transient Node<E> last;
.....

Actually LinkedList The bottom layer uses bidirectional linked list , You can see that there is first and last Two Node node , Let's take a look at the inner class Node The definition of :

 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;
}

It's simple , The students who have studied the linked list should be very clear .

First of all, let's look at constructors :

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

addAll(Collection<? extends E> c) Method is used to add the specified set data to LinkedList in .

Auxiliary function

Going to see LinkedList Of getadd Wait for the method , Let's take a look at some of the more important auxiliary functions :

  • First, the first auxiliary function linkFirst(E e), This method is used for Insert elements into the head of the list .
/*
* Insert elements into the head
*/
private void linkFirst(E e) {
final Node<E> f = first;
// Set up newNode The front node of is null, The last node is f
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
// First link elements , At the same time newNode Set as the last node
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

Recall the inner class Node Constructor for :Node(Node<E> prev, E element, Node<E> next), The three parameters are the previous node 、 The element value and the next node .

From the above, we can see that when inserting elements into the head of the list, we actually create a Node node , Let it next The pointer points to the first node of the list first.

  • Insert elements to the end of the list
/*
* Insert elements into the tail
*/
void linkLast(E e) {
final Node<E> l = last;
// Set up newNode The front node of is l, The last node is null
final Node<E> newNode = new Node<>(l, e, null);
// The new node becomes the last node
last = newNode;
// if l == null The description is the first link element , take first It also points to new nodes
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
// Number of changes +1
modCount++;
}

The method of inserting into the tail is the same as inserting it into the head , No more details here .

  • And then we're going to Insert an element before a given node
/*
* Insert an element before a given node e
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
// Set up newNode The front node of is pred, The last node is succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)// If succ It's the head node , take newNode Set as head node
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

It's simple , Is to give up to the fixed point succ Of prev Pointer to the previous node next Just point to our new node .

  • How about Delete a node Well ?
/*
* Delete linked list node
*/
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// Determine whether it is a head node
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;//GC Recycling
}
// Judge whether it is the tail node
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;//GC Recycling
}
x.item = null;//GC Recycling
size--;
modCount++;
return element;
}

Notice here that we Delete node x After that, we should put x Before and after references, including their own references, are set to null, such JVM Garbage collection will help us to recycle x, Otherwise, there will be a hidden danger of memory leakage .

And the last auxiliary function , be used for Get the node at the specified location .

/*
* Returns the node at the specified location
*/
Node<E> node(int index) {
// according to index Location is considered whether to traverse from the front or from the back ( Speed up query )
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;
}
}

Here is a lesson for us to learn from : It is to judge whether to traverse from the head or the tail according to the position of the index , It's also a small performance optimization .

image

With the auxiliary function, we can take a look at the more commonly used API 了

So let's see first get and set Method :

get(int index) Method is used to get the element at the specified position

/*
* Returns the specified location element
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}

You can see that you call checkElementIndex Method validation parameters , Then call the auxiliary method node(int index) Get element value .

/*
* Set the element
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

set(int index, E element) Method is used to set the element , It's simpler and I won't go into details .

Now let's look at two other ways :

peek Method is used for Return to header node , and pool be used for Delete the header and return the value of the header .

/*
* Returns the value of the head node , If the linked list is empty, return null
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/*
* Delete the header and return the header value , If the linked list is empty, return null
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

Now let's see how to delete a node :

/*
* Delete the header node by default
*/
public E remove() {
return removeFirst();
}
/*
* Delete the node at the specified location
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/*
* Delete the specified node
*/
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 (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

In fact, as long as you understand the above several auxiliary functions , Other additions, deletions and corrections are very simple .

Let's move on to another index(Object o) Method , This method is used to return Returns the index of the specified object in the linked list .

/*
* Returns the index of the specified object in the linked list ( If not, return -1)
* lastIndexOf Empathy ( It's actually traversing from back to front )
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

Now how do we put LinkedList Turn it into an array and return ? Let's see toArray Method :

/*
* Wrap the linked list into an array and return
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
// Take out the node values and put them into the array
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}

One more toArray(T[] a) Method , Can return an array of the specified type :

/*
* Wrap the linked list into an array of specified types and return
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)// The length of the array given is less than the length of the linked list
// Create a type with a equally , The length is size Array of
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;// Definition result Point to the given array , modify result == modify a
// Put the node values into result Array
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}

iterator

LinkedList and ArrayList Another big difference is LinkedList except iterator In addition to the method listIterator Method , In addition to traversing the data backward , You can also traverse forward , It is because of the underlying two-way linked list structure to achieve .

public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);// Parameter checking
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;// Last node crossed
private Node<E> next;// The next node to cross
private int nextIndex;// Next time you cross the index of the node
private int expectedModCount = modCount;// Expected number of revisions
ListItr(int index) {
next = (index == size) ? null : node(index);//index The default is 0
nextIndex = index;
}
/* Determine if there is the next element */
public boolean hasNext() {
return nextIndex < size;
}
/* Traverse backward , Returns the element crossed */
public E next() {
checkForComodification();//fail-fast
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
/* Determine if there is a previous element */
public boolean hasPrevious() {
return nextIndex > 0;
}
/* Traversal forward , Returns the element crossed */
public E previous() {
checkForComodification();//fail-fast
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;// call previous after lastReturned = next
nextIndex--;
return lastReturned.item;
}
/* Returns the next element index to be crossed */
public int nextIndex() {
return nextIndex;
}
/* Returns the index of the last element crossed */
public int previousIndex() {
return nextIndex - 1;
}
/* Remove elements */
public void remove() {
checkForComodification();//fail-fast
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);// Remove... From the list lastReturned,modCount++( This method will help you handle the node pointer pointing to )
if (next == lastReturned)// call previous after next == lastReturned
next = lastNext;
else
nextIndex--;
lastReturned = null;//GC
expectedModCount++;
}
/* Set the element */
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();//fail-fast
lastReturned.item = e;
}
/* Insert elements */
public void add(E e) {
checkForComodification();//fail-fast
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
/* Operate on elements that are not traversed */
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);// Sentenced to empty
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
/*fail-fast*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

summary

Today is about LinkedList The source code points to here for the time being , In fact, if you understand the linked list structure, then the above source code should not be very difficult , If there is anything wrong, please give me some advice .

image

版权声明
本文为[Giant tortoise]所创,转载请带上原文链接,感谢

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云