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

This article is about how to use Java's JDK 1.8-based LinkedList source code. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Preface

Important interfaces and classes in Collection

2. I remember when I first came into contact with LinkedList when I was in the university Java, I talked about the features and application scenarios of LinkedList: based on bidirectional linked lists, LinkedList is suitable for scenarios with frequent additions and deletions and infrequent queries, thread is unsafe and suitable for single thread (much like ArrayList). Then remember that a very profound thing is that you can use LinkedList to implement stacks and queues, so let's take a look at how the source code implements these features.

2.1 Constructor

Public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {transient int size = 0; transient Node first; transient Node last; public LinkedList () {} public LinkedList (Collection c)

The source code is as follows

Public E remove (int index) {checkElementIndex (index); return unlink (node (index));} 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;} 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;} public boolean removeAll (Collection c) {Objects.requireNonNull (c); boolean modified = false; Iterator it = iterator (); while (it.hasNext ()) {if (c.contains (it.next () {it.remove (); modified = true;}} return modified;}

Line 1-4 node 6-30: first of all, according to index, through the method value node (index), it is determined that the subscript in the set is index's node. We mainly look at the unlink () method, and the code feels a lot. In fact, it just points the tail node of the current node node to the tail node of node, and the head node of node tail node to the head node of node. It may be a little round (), and you can basically understand it by looking at the code. Then leave the node with the subscript index empty for GC to recycle

Lines 32-49: first determine whether the current element o to be deleted is empty, then do a for loop to locate the node node where the current element value is equal to o, and then the logic is the unlink () method we saw above, which is also very simple, one more step than remove (int index).

Lines 51-62: because this piece involves iterator Iterator, and we use ListItr for LinkedList, we will talk about iterator together later, but the general logic can be understood. It has the same meaning as our ArrayList iterator method, and can be understood that way first.

Ok, a summary, press the button to delete, also first find the Node according to index, and then go to the linked list to unlink and drop the Node. Delete by element, will first go through the linked list to see if there is the Node, in view of the null value allowed, so will traverse twice, and then go to unlink it.

2.5 modify elements

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

There is only one method, first check whether the subscript is out of bounds, then get the current Node according to the subscript, and then modify the element value item in the node, which is super simple

2.6 find elements

Public E get (int index) {checkElementIndex (index); / / determine whether to cross the line [0Magnesize) return node (index) .item; / / call the node () method to take out the Node node,} 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;} public int lastIndexOf (Object o) {int index = size; if (o = = null) {for (Node x = last; x! = null; x = x.prev) {index--; if (x.item = null) return index;}} else {for (Node x = last; x! = null X = x.prev) {index--; if (o.equals (x.item)) return index;}} return-1;}

Getting the source code of the element is also very simple, mainly through the node (index) method to get the node, and then get the element value. The difference between indexOf and lastIndexOf is that one is traversing from beginning to end, and the other is traversing from tail to head.

2.7 iterator

Public Iterator iterator () {return listIterator ();} public ListIterator listIterator () {return listIterator (0);} public ListIterator listIterator (final int index) {rangeCheckForAdd (index); return new ListItr (index);} private class ListItr extends Itr implements ListIterator {ListItr (int index) {cursor = index;} public boolean hasPrevious () {return cursor! = 0;} public E previous () {checkForComodification (); try {int I = cursor-1; E previous = get (I) LastRet = cursor = i; return previous;} catch (IndexOutOfBoundsException e) {checkForComodification (); throw new NoSuchElementException ();}} public int nextIndex () {return cursor;} public int previousIndex () {return cursor-1;} public void set (E) {if (lastRet < 0) throw new IllegalStateException (); checkForComodification (); try {AbstractList.this.set (lastRet, e); expectedModCount = modCount } catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException ();}} public void add (E e) {checkForComodification (); try {int I = cursor; AbstractList.this.add (I, e); lastRet =-1; cursor = I + 1; expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException ();}

As you can see, in fact, the last iterator used is the ListIterator class, which is integrated from Itr, and the Itr class is the class we used internally in ArrayList yesterday, the hasNext () method is the same as before, judging that it is not equal to the size of size, and then next () gets the element is mainly E next = get (I); this line of code, so we go to the source code before we get the element, get the element value.

OK, so we've seen all the basic methods above. Let's take a look at the problems we left over. First, let's take a look at the function of the Deque interface. Let's take a look.

Deque is an abbreviation for Double ended queue (double-ended queue), pronounced like deck, eggshell.

Deque inherits from Queue, and it is directly implemented by LinkedList, ArayDeque, ConcurrentLinkedDeque and so on.

Deque supports dual-ended queues with limited capacity, as well as variable size queues. Generally speaking, the size of the double-ended queue is uncertain.

The Deque interface defines methods to access elements from the header and tail. For example, insert, delete and obtain elements in the head and tail respectively.

Public interface Deque extends Queue {void addFirst (E); / / insert header, error boolean offerFirst (E e); / / insert header, do not report error E getFirst (); / / get header, exception does not report error E peekFirst (); / / get header, exception does not report error E removeFirst (); / / remove header, exception does not report error E pollFirst (); / / remove header, exception does not report error void addLast (E) / / insert tail, exception will report boolean offerLast (E e); / / insert tail, exception will not report error E getLast (); / / get tail, exception will report error E peekLast (); / / get tail, exception will not report error E removeLast (); / / remove tail, exception will report error E pollLast (); / / remove tail, exception will not report error}

Deque is an interface, and the above is the method in the interface. Then to understand Deque, you must understand Queue.

Public interface Queue extends Collection {/ / insert elements into the queue, boolean add (E e) if an exception occurs; / / insert elements into the queue, and return false boolean offer (E e) if an exception occurs; / / remove queue elements, throw exception E remove () if an exception occurs; / / remove queue elements, return null E poll () if an exception occurs / / get the queue header element. If an exception occurs, it will throw an exception E element (); / / get the queue header element, and return null E peek () if an exception occurs;}

Then we know that LinkedList implements the Deque interface, that is, you can use LinkedList to implement stack and queue functions for writing.

Package com.ysten.leakcanarytest; import java.util.Collection;import java.util.LinkedList; / * * desc: implementation stack * time: 2018-10-31 0031 19:07 * * @ author: wangjitao * / public class Stack {private LinkedList stack; / / no-parameter constructor public Stack () {stack=new LinkedList ();} / construct a stack public Stack (Collection) that contains all the elements in the specified collection

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.