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.

1 goal

The goal of this source code analysis is to gain insight into the implementation mechanism of the Add (int Index, E E) method in the LinkedList class.

 

2 Analysis Methods

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:

3 Analysis Process

LinkLisk: LinkLisk: 4444 LinkLisk: 4444 LinkLisk: 4444 LinkLisk: 4444 LinkLisk: 4444 LinkLisk Click the debug button to start analyzing the process.

 

3.1 Add (int index, Eelement) method

Let’s go straight to the add method analysis and hit Shift+F7 at breakpoint 1 to get inside the method implementation.

Once you click in, you’ll see the code above. This method has five lines of code and calls three methods.

First call checkPositionIndex method, hold down Ctrl+B to enter its source code implementation:

This method calls isPositionIndex ().

CheckPositionIndex (); checkPositionIndex (); checkPositionIndex ();

If index==size, then call linkLast to add the element to the end of the list. Otherwise, call the linkBefore method to add elements in the middle of the list.

LinkLast method has been specifically introduced before, for specific reference

Next, we will focus on the implementation of the linkBefore method.

3.2 linkBefore(E E,Node<E> succ) method

LinkBefore = node (int index); linkBefore = node (int index); linkBefore = node (int index);

This method determines whether the index is in the top half of the list or the bottom half of the list. If it is in the top half of the list, it starts from the beginning. If it is in the bottom half of the list, it starts from the tail.

Since there is no subscript index in the linked list, to get the node at the specified location, you need to traverse the list and return it when you get it. From the source code implementation, we see that there is an acceleration action here. If index<size/2, only from position 0 back traversal position index, and if index>size/2, only from position size forward traversal position index. Therefore, the time complexity of subscript search and modification operation is O (N /2), which improves the running efficiency of the program.

The linkBefore() method looks like this:

After executing this method, an Add operation is complete. Let’s have a visual look at the operation process of this method through the method execution process diagram:

Figure 3-1 linkBefore() adding a node

The above is a flow chart for inserting a new node in a fixed position in a bidirectional linked list.

4 summarizes

In this paper, the source code of add(int index, E E) method of LinkedList is analyzed in detail, and the implementation method of adding elements in the specified location of LinkedList is understood. The method of linkBefore is mainly introduced. We can conclude that linkBefore is mainly divided into three steps:

Step 1: Create a newNode node with a successor pointer to suCC and a precursor pointer to pred.

Step 2: Place the precursor pointer to suCC to newNode.

Step 3: Perform different operations depending on whether pred is null.

– If pred is null, the first header is reset before the node is inserted.

– If pred is not null, direct the subsequent pointer to pred to newNode.

Combined with the previous lecture, we have introduced the two forms of add method of LinkedList, and understood that LinkedList is added by modifying the reference relationship between adjacent nodes, which is relatively efficient.

The author of this article is Zhang Chengcai, majoring in Information Management and information system of Sichuan Tourism University in 2016.

\

More interesting articles:

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!