1. Linkedin List

Hello everyone, I am LinkedList and ArrayList are the same students, but our internal skills are completely different. My brother practiced dynamic array, I practiced linked list.

Let me ask you a question. Do you know why I want to practice linked lists?

For example, if you have to manage a bunch of bills, maybe you have one, maybe you have 100 million bills.

What to do?

Apply for a large 10G array waiting? What if there are only 100 notes?

Apply for a default size array, as the amount of data increases? Remember that expansion requires copying the array again, which is time consuming.

The point is, another drawback of arrays is that if you have 5 million tickets, to delete one ticket from the middle, you have to move 2.5 million tickets one space forward.

When this happens, my elder brother almost breaks down emotionally and suffers terribly. Master could not bear to see his brother so painful, so beat me into the teacher that day, he forced me to practice the chain list of internal skills, at first I did not understand, afraid of master’s partiality, not to teach me the most powerful internal skills of the teacher.

It was not until one day that I witnessed my master almost go crazy because of moving data that I realized master’s good intentions. From then on, I practiced “linked list” this door internal skill, made remarkable progress, master and senior praise I have talent.

The internal work of linked list can be roughly divided into three levels:

  • The first layer is called a “one-way linked list”, where I only have a back pointer to the next data;
  • The second layer is called a bidirectional linked list, and I have two Pointers, the back pointer to the next data, and the front pointer to the previous data.
  • The third layer, called a binary tree, removes the back Pointers and replaces them with left and right Pointers.

But now I can not reach the third level, but master said I have this potential, it is a matter of time to practice magic.

The Java Programmer’s Path to Advancement column has been open source on GitHub. If you have a GitHub account, arrange a wave of star! See if you can make a trending list, please.

GitHub address: github.com/itwanger/to…

Two, LinkedList internal mind method

Well, after what I have done, I should be no stranger to you. So next, I’m going to show you my inner workings.

My inner workings focus on a private static inner class called Node, which stands for nodes.

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

It consists of three parts:

  • The element on the node
  • Next node
  • Previous node

Let me draw a picture to show you.

  • For the first node, prev is null;
  • For the last node, next is null;
  • For the rest of the nodes, prev points to the first one and next points to the second one.

My internal mental method is so simple, in fact, I have already learned it by heart. But the master told me that every morning when I woke up, every night when I went to bed, I must recite it silently. Although I was a little bored, I always did what master told me to do.

The LinkedList move

Like my brother’s ArrayList, my methods are no more than “add, delete, change and check”. Before that, we all have to initialize.

LinkedList<String> list = new LinkedList();
Copy the code

At initialization, the default size is 10, or you can specify the size, depending on how many elements you want to store. I don’t need to.

1) Move 1: increase

We can call the add method to add elements:

list.add("Silent King II.");
list.add("Silent King three.");
list.add("The Silent King iv.");
Copy the code

The add method actually calls linkLast inside:

public boolean add(E e) {
    linkLast(e);
    return true;
}
Copy the code

LinkLast, as the name suggests, is a link at the end of a list:

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 element is added, both first and last are null.
  • Then create a newNode, newNode, whose prev and next are also null.
  • Then assign both last and first to newNode.

You can’t call it a linked list yet, because the front and back nodes are broken.

  • When the second element is added, both first and last refer to the first node.
  • Then create a newNode, newNode, whose prev points to the first node and next to null.
  • Then assign the first node’s next value to newNode.

The linked list is not complete at this point.

  • When the third element is added, first points to the first node and last points to the last node.
  • Then create a newNode, newNode, whose prev points to the second node and next to null.
  • Then assign next to the second node to newNode.

At this point the linked list is complete.

My increment can evolve into two more:

  • addFirst()Method adds the element to the first;
  • addLast()Method adds the element to the end.

AddFirst calls linkFirst internally:

public void addFirst(E e) {
    linkFirst(e);
}
Copy the code

LinkFirst is responsible for setting the new node to first and updating the next of the new first to the previous first.

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
Copy the code

The addLast kernel is basically the same as addFirst, so I’ll leave it to you.

2) Move 2: Delete

There are a lot of ways I can do this:

  • remove(): Deletes the first node
  • remove(int): Deletes a node at a specified location
  • remove(Object): Deletes the node of the specified element
  • removeFirst(): Deletes the first node
  • removeLast(): Deletes the last node

Remove calls removeFirst inside, so both moves have the same effect.

Remove (int) actually calls the unlink method inside.

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
Copy the code

The unlink method is pretty straightforward: update the next and prev of the current node, and set the element on the current node to NULL.

E unlink(Node<E> x) {
    // assert x ! = null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
Copy the code

The unlink method is also called inside remove(Object), but first finds the node where the element resides:

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

If the element is null, it must be checked by ==. One is to use equals if the element is not null. Equals cannot be used to null and will throw an NPE error.

RemoveFirst calls the unlinkFirst method internally:

public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
Copy the code

UnlinkFirst is responsible for destroying the first node and optionally setting the prev of the second node to NULL.

private E unlinkFirst(Node<E> f) {
    // assert f == first && f ! = null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
Copy the code

3) Change

The set() method can be called to update elements:

list.set(0."The Silent Five.");
Copy the code

Take a look at the set() method:

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

First check the specified subscript to see if it is out of bounds; Then find the original node according to the subscript:

Node<E> node(int index) {
    // assert isElementIndex(index);

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

Size >> 1: divide by 2. For a computer, shift is more efficient than division because the data is stored in binary.

In other words, the Node method makes a preliminary judgment on the subscript, starting at subscript 0 if it is near the top; If you’re near the end, start at the end.

It is easy to find the node with the specified subscript, just replace the elements of the original node with the new node, and leave prev and next unchanged.

4) Check

The moves I checked can be divided into two types:

  • IndexOf (Object) : Finds the location of an element
  • Get (int) : Finds elements at a location

IndexOf is divided internally into two types. If the element is null, it must be checked with ==. One is to use equals if the element is not null. Because equals cannot be used to determine null, an NPE error is thrown.

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)
                returnindex; index++; }}else {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (o.equals(x.item))
                returnindex; index++; }}return -1;
}
Copy the code

The kernel of the GET method is actually the Node method, which I’ve already explained and skipped here.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Copy the code

In fact, this check can also be evolved into other things, such as:

  • getFirst()Method is used to get the first element;
  • getLast()Method is used to get the last element;
  • poll() 和 pollFirst()Method is used to delete and return the first element (the body of the two methods is identical despite their names);
  • pollLast()Method is used to delete and return the last element;
  • peekFirst()Method is used to return but not delete the first element.

Challenge of LinkedList

To tell you the truth, I don’t like the comparison with my elder brother ArrayList very much, because we have different internal skills in our training, and no one is higher or lower.

Although my elder brother often calls me my younger brother, we are actually quite harmonious. But I know that, in the eyes of outsiders, the same master and brother are always superior to each other.

For example, we’re adding, deleting, and checking time complexity.

Perhaps this is the fate of it, from the day I entered the school, this debate has not stopped.

No matter how outsiders look at us, in my eyes, shibo will always be a brother. I respect him and he is willing to protect me.

Ok, so that’s it for LinkedList.

If you have a free mood, it is recommended to tear the linked list by hand, you can start from the one-way linked list.

I have outputted nearly a hundred series articles on Java, which are now open source on GitHub at the request of many friends.

Java core syntax, Java Collection framework, Java IO, Java concurrent programming, Java virtual machine, etc.

GitHub open source address (if you also need, welcome star) : github.com/itwanger/to…

I hope you can give me a thumbs up and give me a little motivation to update. I will also continue to improve the quality, to bring you more core technical articles, refill ~