Welcome to “Algorithms and the Beauty of Programming” ↑ pay attention to us! \
This article was first published on the wechat official account “Beauty of Algorithms and Programming”. Welcome to follow and learn more about this series of blogs in time.
\
Previous source code analysis of the Add method of the ArrayList collection (
1 goal
The goal of this source code analysis is to gain insight into the implementation mechanism of the Add (E E) method in the LinkedList class.
2 Analysis Methods
First, write test code, and then use the single step debugging function of Intellij Idea to analyze its implementation ideas step by step.
\
The test code is as follows:
List
3 Analysis Process
Click the debug button to start analyzing the process.
3.1 Constructors
The constructor analysis begins by clicking Shift+F7 at breakpoint 1 to enter the constructor implementation. public LinkedList() { }
\
Once we click in, we see the constructor for LinkedList, which is an empty parameter construct. We can also see the inheritance of the LinkedList class
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable,java.io.Serializable
\
You see that LinkedList inherits from AbstractSequentialList rather than directly inheriting from AbstractList like ArrayList. It also implements three interfaces, Deque, Cloneable, java.io.Serializable, which enable it to be used as a dual-end queue, and clone() can be used to copy linked lists and serialize LinkedList. These three interfaces will be discussed in more detail when we have the opportunity. Because LinkedList implements both the List and Deque interfaces, LinkedList can add elements to the tail, to the specified index location, or to the entire collection.
\
We will introduce the List interface and the Deque interface respectively, which correspond to the add(E,E) method and add(int index,E,E) method. In this article we’ll focus on the Add (E E) method, but first we’ll look at the LinkedList member variables.
\
transient int size = 0; // Set element number transient Node<E> first; // header reference transient Node<E> last; // End referenceCopy the code
3.2 Add (E E) method
Next we examine the implementation mechanism of the Add (E E) method. Click Shift +F7 at breakpoint 2 to access the source code.
public boolean add(E e) {
linkLast(e);
return true;
}
This method is just two lines of code, which seems pretty simple. Here you can see that it calls a linkLast method and returns true. So what does this linkLast method do by putting it here? How did he do that?
\
Continuing F7 debugging, go inside this method and see the following code.
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
\
You can see the word “Node” used a lot. What does it mean? We already know that LinkedList is based on a two-way LinkedList, and there is a word “Node” in the LinkedList. Node literally stands for Node, so we can guess what this code means: Take the last element before, create a new node, the successor of the new node points to the original head node, that is, the original head node is moved back one, the new node takes the place of the head node. The next node is null because it has no elements in it yet. If the initial list is empty, size++ will increase the list size. ModCount++ changes increased.
\
Now let’s see if we’re right:
Let’s navigate to Node and hit Ctrl+B to see the source code
private static class Node
{ E item; Node
next; Node
prev; Node(Node
prev, E element, Node
next) { this.item=element; this.next= next; this.prev= prev; }}
\
Node is an inner class that defines three member variables:
Item represents the element to be added,
Next is the reference to the next node,
Prev represents a reference to the previous node;
\
And a constructor that passes in the above three values. Debugging continues, and sure enough, he starts executing the code above, referencing the three member variables. As we continue to debug, we will find that our above guess is basically correct. But we don’t know yet what he does when his entire list is empty when it’s empty.
\
Look at the following code
if (l == null)
first = newNode;
else
l.next = newNode;
If the reference to the previous node is empty, the new node is the head node. If the reference to the previous node is not empty, the new node is assigned to the next node referenced by the head node. Finally, we do size++ and modCount++. This completes the first Add operation for the LinkedList. When the second operation is performed, the above process is repeated. From this we can analyze the basic data structure of the LinkedList. We use diagrams to illustrate its structure, first of all, the structure of nodes.
\
Figure 3-1 Node structure
Next comes the LinkedList basic data structure:
\
Figure 3-2 LinkedList underlying structure
\
P refers to the header reference, N refers to the tail reference. Each node of the linked list has three elements: prev refers to the predecessor, item refers to the value of the node element, and next refers to the successor.
Every node in LinedList has the same structure. Nodes are connected to each other and form the basic data structure of our LinkedList, which is also the core of LinkedList. It’s easy to understand with the picture above.
\
4 summarizes
In this paper, we analyze the add (E E) method of LinkedList class, which realizes adding elements at the end of the list. Compare the add (E E) method of ArrayList before, the add method of ArrayList is to add elements to the existing set of fixed length. When the set is full, It expands before adding elements.
\
LinkedList, on the other hand, modifies the reference relationship of the existing objects, assigning the reference of the previous object to the new node as the element before the new node, and changing the reference of the last element to the new node, finally updating the number of lists without fixing the capacity in advance.
\
ArrayList can add elements to a given location. How about LinkedList? If you can, how does he do that?
* * * *
The author of this article is Zhang Chengcai, majoring in Information Management and information system of Sichuan Tourism University in 2016.
\
More interesting articles:
\
\
\
\
* * * * \
\
Sichuan Tourism Institute Where2Go team
* * * * * * * * \
Wechat: The beauty of algorithms and programming
Long press to identify the QR code to follow us!
Tips: Click on the lower right corner of the page “Write a message” to comment, looking forward to your participation! Welcome to forward!
\
\