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

This article focuses on "how to understand the LinkedList source code", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the LinkedList source code.

LinkedList is also a very common collection class, and LinkedList is a collection based on linked list implementation. It has the characteristics of the List collection:

Access order

With index

Allow repeating elements

It also has the characteristics of the Deque collection:

First in, first out

Double-ended operation

Its own characteristics are:

To insert or delete an element, you only need to change some data and do not need to move the element.

It's still through source code to see how LinkedList implements its own features.

Doubly-linked list implementation of the {@ code List} and {@ code Deque} interfaces. Implements all optional list operations,and permits all elements (including {@ code null}).

Double-linked list implementation of List interface and Deque interface. Implement the operation of all List interfaces and store all elements.

Public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

You can see that LinkedList implements a Deque interface, which means that LinkedList has not only the features of List, but also the features of Deque, so what is Deque?

Public interface Deque extends Queue public interface Queue extends Collection

It turns out to be another interface that inherits the Collection collection.

Queue is what we often call a queue. Its feature is FIFO (First In First Out) first-in-first-out (FIFO). It has only two operations:

Save the element at the end of the queue

Remove the element from the head

It's like waiting in line to do something.

In addition to these two operations, its subinterface Deque can have more functions than Queue queue.

You can add elements either to the end of the queue or to the head of the queue

Elements can be taken either from the end of the team or from the head of the team

In this way, it looks like both sides can be the head and tail of the line, so Deque is also called double-ended queue.

Of course, LinkedLisk also implements these features and has Doubly-linked (double linked list features).

So what is a linked list?

In fact, the linked list is a linear storage structure, which means that the data to be stored is stored in a storage unit, which not only stores the data to be stored, but also stores the address of the next storage unit.

As the name implies, a storage unit stores not only the address of its next storage unit, but also the address of the previous storage unit. Each time the data is looked up, it is searched through the address information stored in the storage unit.

Member variables:

Transient int size = 0transient Node first;transient Node last

There are only three, and size represents the number of elements stored by LinkedList. So what is this Node?

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 is the data structure Node within LinkedList. As the basic storage unit of LinkedList, it can best reflect the characteristics of LinkedList double-linked list.

Like this.

Where prev stores the reference (address) of the previous node, next stores the reference of the next unit, and item is the specific data to be stored.

First and Last are used to mark the head and end of the line.

Add data:

Public boolean add (E e) {linkLast (e); return true;} 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++;}

The default is to call the method added to the tail. As mentioned earlier, the basic storage unit of LinkedList is Node, so the added data will be encapsulated in the item attribute of Node, and the prev of this new Node will point to the previous Node, and the next of the previous Node will point to this new Node.

Similar to this, but note that underlining is only a visual expression, as mentioned above, the prev property and next property in Node are used to store references, through which you can find the previous Node or the next Node.

Public void addFirst (E e) {linkFirst (e);} 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++ } public void addLast (E e) {linkLast (e);} public boolean offerLast (E e) {addLast (e); return true;}

In fact, LinkedList has many methods with different names, but the implementation methods are similar, because we may use LinkedList to express different data structures. Although we all add elements to the head / end of the line, a clear description is good for the readability of the code. For example, if you want to use LinkedList to represent Stack (stack) data structure, use push () / pop () / peek () to describe it, and use add () / offer () to describe Queue (queue) data structure with LinkedList. (of course, a better way to do this is polymorphism.)

Delete data:

/ / delete header Nodepublic E removeFirst () {final Node f = first; if (f = null) throw new NoSuchElementException (); return unlinkFirst (f);} / delete operation private E unlinkFirst (Node f) {/ / assert f = = first & & f! = null; final E element = f.item; final Node next = f.nextt; f.item = null F.next = null; / / help GC first = next; if (next = = null) last = null; else next.prev = null; size--; modCount++; return element;} / / delete tail Nodepublic E removeLast () {final Node l = last; if (l = = null) throw new NoSuchElementException () Return unlinkLast (l);} / / delete operation private E unlinkLast (Node l) {/ / assert l = = last & & l! = null; / / get the data stored in the last element final E element = l.item; / / get the reference to the element before prev of the last element final Node prev = l.prev / / assign them to null l.item = null; l.prev = null; / / help GC / / now the former element is list (the last Node) last = prev; / / if the former element is already null, then there is no Node if (prev = = null) first = null Else / / indicates that there is an element before it, so the next of the previous element will store null prev.next = null; size--; modCount++; return element;}.

First, take a look at the simple deletion. Here you specify the element that comes first and the last after deletion, so as long as you judge whether the prev or next of the deleted Node still has a value, it means that there is also Node, and if not, the LinkedList is empty.

How to delete the header / tail Node, as long as its next/prev is empty, which means there is no reference to it, then we think it has been removed from the LinkedList, because we cannot find the Node through the reference to the storage unit, so GC will soon recycle the Node.

This is just deleting the head and tail Node, what if you delete the middle Node? This should be seen with the search and insertion below.

Find elements:

Public E get (int index) {checkElementIndex (index); return node (index) .item;} Node node (int index) {/ / assert isElementIndex (index); / / if the index is less than half the number of elements, traverse if (index) before

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

The array has a subscript by default, and you can take out the elements in its location at one time, but the underlying LinkedList does not maintain such an array, so how do you know what the element is?

Stupid method, I have size element, I don't know where the index you specified is, so I'll just find it one by one. After all, my storage unit Node remembers the reference (address) of the unit next to it.

If your index is more than half of my size, I will find it from behind, because I am a double-ended queue with a reference to Last (address), so I can swap both ends.

Therefore, it is not easy to find elements in LinkedList. You may have to look for size/2 at most to find them.

As long as you find the location you want, it's easy to insert and delete the specified Node.

Public E remove (int index) {checkElementIndex (index); return unlink (node (index));} E unlink (Node x) {/ / assert x! = null; / / get the item final E element of the Node to be deleted = x.item; / / the latter Node final Node next = x.next; / / the previous Node final Node prev = x.prev / / if the previous Node is null (the description is the first Node) if (prev = = null) {/ / then the next Node as first first = next;} else {/ / otherwise, the next Node reference of the previous Node becomes the next Node prev.next = next / / the current previous reference becomes null x.prev = null;} / / if the latter Node is null (indicating that it is the last Node) if (next = = null) {/ / then the previous Node is last last = prev } else {/ / otherwise there is a Node / / then the next Node reference of the latter Node becomes the previous Node next.prev = prev; / / the current post-reference becomes null x.next = null;} / / the saved element is also set to null x.item = null; / / element-1 size-- / / modify + 1 modCount++; return element;} public void add (int index, E element) {checkPositionIndex (index); if (index = = size) linkLast (element); else linkBefore (element, node (index));} void linkBefore (E e, Node succ) {/ / assert succ! = null / / the previous Node final Node pred = succ.prev; / / new Node to be inserted, the previous reference is the previous Node, and the back reference is the Node final Node newNode = newNode (pred, e, succ) of the current location; / / the previous reference of the latter Node becomes the new Node succ.prev = newNode / / if there is no previous Node if (pred = = null) / / what is added is the first Node first = newNode; else// means that there is a Node / / change the post-reference of the previous Node into this new Node pred.next = newNode; / / element + 1 size++; modCount++;}

By simply changing the prev and next in the memory cell Node, we can assume that the Node has been inserted / deleted.

The comments of the code with the following figure, it will be easy to understand a lot, among which pay attention to distinguish between the names in the source code, it is best to take notes to make it easier to distinguish.

If you are inserting an element, just look backwards.

About traversing:

We can see that the biggest performance consumption of LinkedList is at the step of node (index), which requires a large number of elements to be found. But as long as you find the Node where this element is located, it will be very convenient to insert and delete.

So for the get (index) method, we need to be very careful to use it. If you only want to look at the elements in this location, you can use this method, but if you are traversing the LinkedList, you must not write this:

For (int I = 0; I

< linkedList.size(); i++) { linkedList.get(i).equals(Obj);} 这样对于每次循环,get总会从前或者从后走i次，不考虑get方法中>

If the optimization is > 1, this is an O (n ^ 2) time complexity method, and the efficiency is very low.

So LinkedList provides an internal Iterator iterator for us to use:

Private class ListItr implements ListIterator {private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount; ListItr (int index) {/ / assert isPositionIndex (index); next = (index = = size)? Null: node (index); nextIndex = index;} public boolean hasNext () {return nextIndex < size;} public E next () {checkForComodification (); if (! hasNext ()) throw new NoSuchElementException (); lastReturned = next; next = next.next; nextIndex++ Return lastReturned.item;}

In fact, it is to get the Node by constantly calling the next () method, and then operate on the Node, so the time complexity is O (n), and there will not be a lot of repetitive and useless traversal.

At this point, I believe you have a deeper understanding of "how to understand the LinkedList source code". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.