Shulou(Shulou.com)06/02 Report--

How to understand the Java LinkedList source code in the form of martial arts, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

First, the profile of LinkedList.

Hello, everyone. I am LinkedList. ArrayList and I are brothers of the same school, but our internal skills are completely different. The elder brother practiced dynamic arrays and I practiced linked lists.

Let me ask you a question. Do you know why I want to practice the inner skill of linked list?

For example, if you have to manage a bunch of bills, there may be one, or there may be 100 million.

I don't know what to do

Apply for a 10-gigabyte array and wait? What if there are only 100 bills?

Apply for an array of default size and expand as the amount of data increases? To know that expansion requires re-copying the array, which is very time-consuming.

The point is, another drawback of the array is that if you have 5 million bills now, and you want to delete one note from the middle now, you need to move 2.5 million bills forward one square.

When he encountered this kind of situation, my brother almost had an emotional breakdown and was sick to death. Master could not bear to see my brother in such pain, so the day I entered the door, master forced me to practice the inner skill of the linked watch. at first, I didn't understand it. I was afraid that master would be partial and would not teach me the most powerful internal skill of the master.

It was not until one day, when I witnessed that my brother was almost obsessed with moving data, that I understood master's good intentions. From then on, I practiced the skill of "chain watch" hard and made remarkable progress. Master and brother both praised me for my talent.

The internal work of the linked list is roughly divided into three levels:

The first layer is called an one-way linked list. I only have a back pointer that points to the next data.

The second layer is called "two-way linked list". I have two pointers, the back pointer to the next data and the front pointer to the previous data.

The third layer is called "binary tree". Remove the back pointer and replace it with the left and right pointer.

However, my current skills have not yet reached the third level, but master said that I have this potential, and it is only a matter of time before I can practice divine skills

Like first and then read: "Java programmer's way to advance" column has been open source on GitHub, there are GitHub account friends, to arrange a wave of star ah! Let's see if we can hit the trending list, please.

GitHub address: https://github.com/itwanger/toBeBetterJavaer

Second, the internal power-heart method of LinkedList

Well, after such an exposition like mine, everyone should be no stranger to me. So next, I'll show you my inner workings.

My inner core method is mainly a private static inner class called Node, that is, nodes.

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

It consists of three parts:

Elements 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 previous one and next points to the latter.

My inner work method is so simple, in fact, I have already kept it in mind. But master told me to recite it silently every morning when I woke up and every night when I went to bed. Although I was a little bored, I always obeyed master's teachings.

Third, the moves of LinkedList

Like my brother ArrayList, my moves are nothing more than "adding, deleting, changing and searching". Before that, we all have to initialize.

LinkedList list = new LinkedList ()

When initializing, the default size is 10, or you can specify the size, depending on the number of elements to be stored. I don't need it.

1) trick 1: increase

You can call the add method to add elements:

List.add (Silent King II); list.add (Silent King III); list.add (Silent King IV)

The linkLast method is actually called inside the add method:

Public boolean add (E e) {linkLast (e); return true;}

LinkLast, as its name implies, is a link at the end of a linked list:

Void linkLast (E e) {final Node l = last; final Node newNode = newNode (l, e, null); last = newNode; if (l = = null) first = newNode; else l.next = newNode; size++; modCount++;}

When you add the first element, both first and last are null.

Then create a new node, newNode, whose prev and next are also null.

Then assign both last and first to newNode.

At this point, you can't call it a linked list, because the front and rear nodes are broken.

When you add the second element, both first and last point to the first node.

Then create a new node, newNode, whose prev points to the first node, and next is null.

Then assign the next of the first node to newNode.

At this time, the linked list is not complete.

When you add the third element, first points to the first node and last points to the last node.

Then create a new node, newNode, whose prev points to the second node, and next is null.

Then assign the next of the second node to newNode.

The linked list is complete at this time.

This additional move of mine can also evolve into two other ways:

The addFirst () method adds the element to the first place

The addLast () method adds the element to the end.

LinkFirst is actually called inside addFirst:

Public void addFirst (E e) {linkFirst (e);}

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 f = first; final Node newNode = newNode (null, e, f); first = newNode; if (f = = null) last = newNode; else f.prev = newNode; size++; modCount++;}

The kernel of addLast is actually similar to that of addFirst, so it's up to everyone to understand it.

2) trick 2: delete

I have a lot of ways to delete this:

Remove (): delete the first node

Remove (int): deletes a node at a specified location

Remove (Object): deletes the node of the specified element

RemoveFirst (): delete the first node

RemoveLast (): delete the last node

RemoveFirst is called internally by remove, so these two moves have the same effect.

The unlink method is actually called inside remove (int).

Public E remove (int index) {checkElementIndex (index); return unlink (node (index));}

The unlink method is easy to understand, which is to update the next and prev of the current node, and then set the element on the current node to null.

E unlink (Node x) {/ / assert x! = null; final E element = x.item; final Node next = x.next; final Node prev = x.item; 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;}

The unlink method is also called inside remove (Object), but before that, you need to find the node where the element is located:

Public boolean remove (Object o) {if (o = = null) {for (Node x = first; x! = null; x = x.next) {if (x.item = = null) {unlink (x); return true;}} else {for (Node x = first; x! = null) X = x.next) {if (o.equals (x.item)) {unlink (x); return true;} return false;}

There are two internal types, one is that when the element is null, you must use = = to judge; the other is that when the element is non-null, use equals to judge. Equals cannot be used to judge null, and a NPE error is thrown.

The unlinkFirst method is called internally by removeFirst:

Public E removeFirst () {final Node f = first; if (f = null) throw new NoSuchElementException (); return unlinkFirst (f);}

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

Private E unlinkFirst (Node f) {/ / assert f = = first & & f! = null; final E element = f.item; final Node 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;} 3) trick 3: change

You can call the set () method to update the element:

List.set (0, Silent King 5)

Take a look at the set () method:

Public E set (int index, E element) {checkElementIndex (index); Node x = node (index); E oldVal = x.item; x.item = element; return oldVal;}

First check the specified subscript to see if it is out of bounds, and then find the original node according to the subscript:

Node node (int index) {/ / assert isElementIndex (index); if (index)

< (size >

> 1)) {Node x = first; for (int I = 0; I

< index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i >

Index; iMurt -) x = x.colors; return x;}}

Size > > 1: move one bit to the right, which is equivalent to dividing by 2. For a computer, shift is more efficient than division because data is stored in binary within the computer.

In other words, the node method makes a preliminary judgment on the subscript, traversing from subscript 0 if it is close to the first half, and traversing from the end if it is close to the second half.

It is easy to find the node with the specified subscript, just replace the elements of the original node with the new node OK, prev and next do not need to be changed.

4) style 4: check

There are two ways for me to check:

IndexOf (Object): find the location of an element

Get (int): find an element in a location

The interior of indexOf is divided into two types, one is that when the element is null, you must use = = to judge; the other is that when the element is non-null, use equals to judge. Because equals cannot be used to judge null, a NPE error will be thrown.

Public int indexOf (Object o) {int index = 0; if (o = = null) {for (Node x = first; x! = null; x = x.next) {if (x.item = = null) return index; index++;}} else {for (Node x = first; x! = null) X = x.next) {if (o.equals (x.item)) return index; index++;}} return-1;}

The kernel of the get method is actually the node method, which has been explained before and skipped here.

Public E get (int index) {checkElementIndex (index); return node (index) .item;}

In fact, checking this trick can also evolve into other tricks, such as:

The getFirst () method is used to get the first element

The getLast () method is used to get the last element

The poll () and pollFirst () methods are used to delete and return the first element (although the names of the two methods are different, the method body is exactly the same)

The pollLast () method is used to delete and return the last element

The peekFirst () method is used to return but not delete the first element.

IV. Challenges of LinkedList

To tell you the truth, I don't like to compare it with my brother ArrayList, because we each practice different internal skills, and there is no one higher or lower.

Although my brother often called me brother, there was actually a lot of harmony between us. But I know that in the eyes of outsiders, brothers of the same teacher always compete with each other.

For example, the time complexity of the two of us in adding, deleting, changing and searching.

Maybe this is fate. Since the day I entered the division, this kind of argument has never stopped.

No matter what outsiders think of us, in my eyes, elder brother will always be the first elder brother. I respect him, and he is willing to protect me.

All right, that's all for LinkedList.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.