JDK growth Note 5: Initial introduction to LinkedList

LinkedList is a preliminary study

As a Java engineer, you probably don’t use LinkedList very much; most of you are always in New ArrayList. A lot of interview time is spent comparing LinkedList to ArrayList. Always ask you what’s the difference between an ArrayList and a LinkedList? Are they thread safe? And so on. Most of the time you’re used to using ArrayList and rarely think about using LinkedList. You probably didn’t know it could be used as a memory queue or stack. In the next few sections, you’ll learn about the underlying source code for LinkedList, as well as the method analysis source code.

Let’s start by reviewing the basics of LinkedList.

LinkedList fundamentals and pros and cons

1) LinkedList fundamentals

In short, in the JDK, the LinkedList underlying maintains data based on a bidirectional LinkedList, which was a bidirectional cyclic LinkedList prior to JDK 1.7.

2) Strengths and weaknesses of LinkedList

Disadvantages:

1. Random access performance is poor

Advantages:

1. Frequent insert and delete elements perform well with unlimited capacity
2. Can be used as a memory queue or stack
3. A sequential

Explore the context of LinkedList

What should you do first? Yes, that’s right. Take a look at the source code for LinkedList:

In the first figure, you can see that only three members traverse size, FISrt, and last. Except for size, the other two variables are of type Node, so you can guess that Node should be its inner class. That leaves the usual constructors, add, get, set, remove, and finally toArray, addAll, and indexOf, which are similar to the API of ArrayList.

The second picture is as follows:

In this diagram, you can see some pop, push, poll, and Offer methods. If you are familiar with data structures, these method names are similar to those used for queuing, queuing, and stack loading and unloading of queue data structures. Then there are ListItr and Node inner classes.

Once you’ve looked at LinkeList’s source code, shouldn’t you simply write a Demo, starting with its entry, and take a look at its core source code?

Explore the LinkedList starting with the Add method

You’ll remember we mentioned earlier that core source code is usually viewed from the entry point, often referred to as the top down.

First you have to have a code Demo. When you use LinkedList, do you create a LinkedList first and then call the Add method? Take a look at the following code listing:

import java.util.LinkedList;

public class LinkedListDemo {

public static void main(String[] args) {

  LinkedList<String> hostList = new LinkedList<>();

  hostList.add("host1");

  hostList.add("host2");

  hostList.add("host3"); }}Copy the code

The first line creates a LinkedList of elements of type String, using the default constructor with no arguments. Click on the constructor to access the source code:

/** * Constructs an empty list. */

public LinkedList(a) {}Copy the code

Nothing is done and, judging from the comments, an empty LinkedList is constructed. You may have noticed the size variable earlier, but as you can guess, there is no limit to the size of the LinkedList and in theory enough memory to go on indefinitely. After executing the above code, we reviewed that LinkedList is a bidirectional LinkedList, so it will look like this:

The main function then executes the next line and executes the add method:

public boolean add(E e) {

   linkLast(e);

   return true;

}
Copy the code

LinkLast is called directly and returns true.

So you need to look at the linkLast method source code. Finally, we get to the point, the skeleton of this method, which has two last and first members, newNode, if-else, and size++ returned. It seems simple enough.

transient Node<E> first;

transient Node<E> last;

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

}
Copy the code

But what is this Node for? You have to research:

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; }}Copy the code

Node is an inner class with an item element and a Next and prev object.

Does this structure sound familiar? If you are familiar with data structures, or if you know that the underlying LinkedList data is a two-way list, you can assume that this is the wrapper class that represents the underlying LinkedList.

Prev and next are two Pointers to the previous node and the next node. Item is a generic type and should hold the corresponding data element. I hope you haven’t given this data structure back to university faculty.

Now that you know what Node is, take a look at the linkLast method source 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++;

}
Copy the code

When the first line is executed, it still doesn’t look easy to understand, so you need a solution: ** Draw! ** draws a picture to tease out the context of this approach. As follows:

** Final Node l = last; Last is null, so the l variable is null.

Final Node newNode = newNode <>(l, e, null);

As shown in the figure above, a Node object is created named newNode, the item element is “host1”, and the prev pointer and L of newNode point to an address. L points to last, which is null, so prev is null.

Execute the next line, last = newNode, this is simple, last refers to the newNode node, as shown below:

Next, you can see that the if-else judgment is entered, as shown below:

You actually have first pointing to newNode. And then finally size++, the linkLast method returns. Is the final result as shown below?

After these five steps, do you understand the Add method of LinkedList? The following three things have been done:

1. Use the temporary pointer L to record the position of the last element
2. Creates a new element whose prev pointer points to the last element
3. The last pointer points to the new element, and fisRT points to the new element if it’s added for the first time

So you can imagine, if you add another element, is that the same idea? With this idea in mind, try drawing your own pictures to get a feel for it!

You get something like this:

But what you really want to remember is the idea of auxiliary Pointers, and that’s a good idea for later on if you want to make a list first, or flip a one-way list. You’ll see that at the end of the episode.

Golden words of dessert

In addition to today’s knowledge and skill growth, I bring you a golden sentence dessert, to end my sharing today: believe is more important than know.

Let me tell you a story. Once in the West, there was a priest who was very successful in his mission. Why? Because he believed 100% in God, when he preached, he always said, “God says…” He has more and more followers. One day he suddenly realized that none of these people had ever seen God. It was I who was saying to them, “God said, God said…” . So why did I say “God says”? From then on he changed it to “I say… I said…” . So later on, when he was preaching, he was like, “I said… As a result, there were fewer and fewer followers until he was alone. What can you learn from this story? The power of belief.

In fact, many times we believe that things will get better, that the disease will get better. A lot of truth, things, you can’t just know, but to believe. What’s the difference between believing and knowing? It’s like knowing that the hat on your head may blow away when the wind blows, while believing that the hair on your head will not come off when the wind blows. Belief is ingrained, a belief that gradually shapes your beliefs and becomes your own values. So most of the time don’t just know that learning and growing every day will make you improve, will make you better, but you have to believe that looking at your growth every day will make you grow up and become better and better. Remember that believing is more important than knowing.

Finally, you can read the source code, ask colleagues or classmates over lunch, you can also share, tell him to listen to.

Feel free to leave a comment in the comments section.

This article is published by OpenWrite!