JDK1.8ソースコード（6）-java.util.LinkedListクラス

Jdk1 8 Source Code Java

以前のブログでは、コレクションリストの典型的な実装を紹介しました 配列リスト ArrayListは配列で構成されていることがわかっています。このブログでは、リンクリストの配列で構成される別の典型的な実装LinkedList Listコレクション、リストの概要を紹介します。 このブログ また、詳細に説明されています。このブログでは、LinkedListがどのように実装されているかを紹介します。

1、LinkedListが定義されています

LinkedListリンクリストは、順序付けられた実装済み要素のコレクションであり、繰り返すことができます。

1 public class LinkedList 2 extends AbstractSequentialList 3 implements List, Deque, Cloneable, java.io.Serializable

ArrayListおよびsetasは、LinkedList Cloneableインターフェイスのコレクションであり、Serializableインターフェイス、クローニングを実装し、serializableをサポートするために使用されます。インターフェイスリストは言うまでもなく、タイプセット仕様リストのメソッドを定義します。

コレクションArrayListに関して、LinkedListは以上のコレクションを実装することに注意してください。 そして キューへの双方向インターフェースであるインターフェース、キューは双方向であり、両側を増やして操作を削除することができます。

2、フィールドプロパティ

 //The number of list elements (nodes) transient int size = 0 /** * Pointer points to the first node */ transient Node first /** * A pointer to the last node */ transient Node last

内部クラスLinkedListクラスであるNodeクラスがあり、各要素がNodeクラスオブジェクトを表すことに注意してください。LinkedListコレクションは、同様の手をつないで構成する多くのNodeオブジェクトで構成されています。

 1 private static class Node {  2 E item//The actual storage elements  3 Node next//A reference to the node point  4 Node prev//A reference point to the next node  5  6 //Constructor  7 Node(Node prev, E element, Node next) {  8 this.item = element  9 this.next = next 10 this.prev = prev 11  } 12 }

コードを見る

以下に示すように：

4つの要素のFIGLinkedList、つまりノード4オブジェクト、サイズ= 4、ヘッドは最初の要素Aを指し、テールは最後のノード要素Dを指します。

3、コンストラクター

 public LinkedList() { } public LinkedList(Collectionextends E> c) { this() addAll(c) }

LinkedListには2つのコンストラクターがあり、最初のコンストラクターはデフォルトの空のコンストラクター、2番目のインスタンスセットは既存のコレクションLinkedListに要素を追加すること、呼び出しはaddAll（）メソッドです。これについては以下で説明します。

注：LinkedListリストのサイズは初期化されたコンストラクターではありません。配列のようなリストは、定義されたサイズであるため、配列を決定する必要があります。次に、メモリスペースを割り当てる必要がありますが、リストは同じではなく、ポインターによってサイズを決定しません。割り当てられたメモリアドレスへの次のポインタに移動します。

4、要素を追加します

①、addFirst（E e）

指定した要素をリストの先頭に追加します

 1 //The specified element is attached to the head node list  2 public void addFirst(E e) {  3  linkFirst(e)  4  }  5 private void linkFirst(E e) {  6 final Node f = first//The head node is assigned to f  7 final Node newNode = new Node(null, e, f)//The element is configured to specify a new node, a reference node for the first node pointing to the next node in this  8 first = newNode//The new node to the head node, then the former head node to a second node f  9 if (f == null)//If the second node is null, that is, the original list is empty 10 last = newNode//This new node to the end node (previously set as the head node) 11 else 12 f.prev = newNode//The former head node on a node point to the new node 13 size++//The number of nodes plus 1 14 modCount++//And, like the ArrayList, iterator and listIterator method returns the iterator and list iterator implementation uses. 15 }

コードを見る

②、addLast（E e）およびadd（E e）

指定した要素をリストの最後に追加します

 1 //Adding an element to the end of the list  2 public void addLast(E e) {  3  linkLast(e)  4  }  5 //Adding an element to the end of the list  6 public boolean add(E e) {  7  linkLast(e)  8 return true  9  } 10 void linkLast(E e) { 11 final Node l = last//The set tail node l 12 final Node newNode = new Node(l, e, null)//We construct a new node, a node references to the tail node node l 13 last = newNode//The tail node to create a new node 14 if (l == null)//If the end node is empty, it represents the original list is empty 15 first = newNode//The head node to the newly created node (Node End nodes are also newly created) 16 else 17 l.next = newNode//The lower end of the original reference point of a node of the new node 18 size++//The number of nodes plus 1 19 modCount++//And, like the ArrayList, iterator and listIterator method returns the iterator and list iterator implementation uses. 20 }

コードを見る

③、add（int index、E element）

このリストの指定された位置に指定された要素

 //The specified element into the specified position in this list public void add(int index, E element) { //Index is determined in an IndexOutOfBoundsException index> = 0 && index <= size abnormality  checkPositionIndex(index) if (index == size)//If the index value is equal to the size of the list linkLast(element)//The node into tail node else linkBefore(element, node(index)) } void linkLast(E e) { final Node l = last//The set tail node l final Node newNode = new Node(l, e, null)//We construct a new node, a node references to the tail node node l last = newNode//The tail node to create a new node if (l == null)//If the end node is empty, it represents the original list is empty first = newNode//The head node to the newly created node (Node End nodes are also newly created) else l.next = newNode//The lower end of the original reference point of a node of the new node size++//The number of nodes plus 1 modCount++//And, like the ArrayList, iterator and listIterator method returns the iterator and list iterator implementation uses.  } Node node(int index) { if (index > 1)) {//If the front half portion is inserted into the index Node x = first//Let x head node for (int i = 0 i  //From the start node to all nodes inserted between the node index moved back a x = x.next return x } else {//If the node is inserted in the latter half position Node x = last//Set the last node x for (int i = size - 1 i > index i--)//Moving one from the last node to all the nodes between the index position of the insertion node forward x = x.prev return x } } void linkBefore(E e, Node succ) { final Node pred = succ.prev//Pred to the insertion of a node final Node newNode = new Node(pred, e, succ)//The new node reference to pred, under reference to succ succ.prev = newNode//A reference node to a new node on the succ if (pred == null)//If a node is a reference node is inserted null first = newNode//The new node is the first node else pred.next = newNode//The next node insert a reference node to a new node size++ modCount++ }

コードを見る

④、addAll（コレクションc）

指定されたコレクションが返される順序で、イテレータはこのリストで指定されたすべての要素を追加します。

このメソッドには、指定されたロケーションインデックスに挿入されたすべての要素cのセットであるaddAll（int index、Collection c）もあります。実際には

addAll（Collection c）== addAll（size、Collection c）

次のソース：

 1 //In the order specified collection iterator returned, all of the elements specified in the appended set the end of this list.  2 public boolean addAll(Collectionextends E> c) {  3 return addAll(size, c)  4  }  5 //C the set of all the elements inserted in place of the specified index.  6 public boolean addAll(int index, Collectionextends E> c) {  7 //Index is determined in an IndexOutOfBoundsException index> = 0 && index <= size abnormality  8  checkPositionIndex(index)  9 10 Object[] a = c.toArray()//Be converted into a set of array of type Object 11 int numNew = a.length 12 if (numNew == 0)//If you add the collection is empty, the direct return false 13 return false 14 15 Node pred, succ 16 if (index == size) {//If the inserted position is equal to the length of the list, the original collection element is appended to the end of the list 17 succ = null 18 pred = last 19 } else { 20 succ = node(index) 21 pred = succ.prev 22  } 23 24 for (Object o : a) {//Traversing element to be inserted 25 @SuppressWarnings('unchecked') E e = (E) o 26 Node newNode = new Node(pred, e, null) 27 if (pred == null) 28 first = newNode 29 else 30 pred.next = newNode 31 pred = newNode 32  } 33 34 if (succ == null) { 35 last = pred 36 } else { 37 pred.next = succ 38 succ.prev = pred 39  } 40 41 size += numNew 42 modCount++ 43 return true 44 }

コードを見る

要素LinkedListコレクションを追加するさまざまな方法を確認するために、要素LinkedListを追加するたびに、要素へのポインター参照と次のポインター参照を変更するだけで、展開がないことがわかります。 、ArrayListとは対照的に、容量が必要であり、挿入要素の途中で、2つの挿入要素の場合、すべての要素の効率の大きな違いを元に戻す必要があります。この次のブログでは、両方の効率と、どちらを選択するかを説明します。分析のための一連のケース。

また、操作を追加するたびに、modCount ++操作があります。

5、要素を削除します

ここの図に示すようにではなく、あるノードのポイントを次のノードと参照ポイントに変更するのと同じように、要素を削除して要素を追加します。

①、（）を削除してremoveFirst（）

このリストから削除され、最初の要素を返します

 1 //Removed from this list and returns the first element  2 public E remove() {  3 return removeFirst()  4  }  5 //Removed from this list and returns the first element  6 public E removeFirst() {  7 final Node f = first//f is set to the first node  8 if (f == null)  9 throw new NoSuchElementException()//If the first node is empty, then an exception is thrown 10 return unlinkFirst(f) 11  } 12 private E unlinkFirst(Node f) { 13 // assert f == first && f != null 14 final E element = f.item 15 final Node next = f.next//Next is the next node of the head node 16 f.item = null 17 f.next = null // The element node and references are set to null, to facilitate garbage collection 18 first = next //Modifying the first node to the second node 19 if (next == null)//If the second node is empty (there is only the first current list element) 20 last = null//Then the tail node is also set to null 21 else 22 next.prev = null//If the second node is not empty, then a second reference nodes is set to null 23 size-- 24 modCount++ 25 return element 26 }

コードを見る

②、removeLast（）

このリストから削除し、最後の要素を返します

 1 //Remove from this list and returns the last element  2 public E removeLast() {  3 final Node l = last  4 if (l == null)//If the end node is empty, indicating the current set is empty, an exception is thrown  5 throw new NoSuchElementException()  6 return unlinkLast(l)  7  }  8  9 private E unlinkLast(Node l) { 10 // assert l == last && l != null 11 final E element = l.item 12 final Node prev = l.prev 13 l.item = null 14 l.prev = null //The element node and references are set to null, to facilitate garbage collection 15 last = prev//Tail node penultimate node 16 if (prev == null)//If the penultimate node is null 17 first = null//Then the node is also set to null 18 else 19 prev.next = null//If the penultimate node is not empty, then the penultimate next reference node set to null 20 size-- 21 modCount++ 22 return element 23 }

コードを見る

③、remove（int index）

このリスト要素をその場所で削除します

 1 //Delete this list element at the location  2 public E remove(int index) {  3 //Index is determined in an IndexOutOfBoundsException index> = 0 && index <= size abnormality  4  checkElementIndex(index)  5 return unlink(node(index))  6  }  7 E unlink(Node x) {  8 // assert x != null  9 final E element = x.item 10 final Node next = x.next 11 final Node prev = x.prev 12 13 if (prev == null) {//If you delete a node node position reference is null (the means to delete the first element) 14 first = next//The first node is set to the first element of the next node 15 } else {//If you delete a node node position reference is not null 16 prev.next = next//The next node on a node of the deletion node is a node pointing to the next reference node deleted (deletion node is removed) 17 x.prev = null//To delete a node on a reference node is set to null 18  } 19 20 if (next == null) {//If the next node node delete references to null (represented remove the last node) 21 last = prev//The tail node is set to a node of the deletion node 22 } else {//Instead of deleting the tail node 23 next.prev = prev//The reference to a node on a node point to delete a node on the next node of the deletion node 24 x.next = null//The next node node delete references set to null 25  } 26 27 x.item = null//Delete the contents of the node is set to null, to facilitate garbage collection 28 size-- 29 modCount++ 30 return element 31 }

コードを見る

④、削除（オブジェクトo）

存在する場合は、指定された要素の最初の出現のリストから削除します

この方法では、本質的には削除（int index）に大きな違いはなく、循環要素による削除の判断に注意する必要があります。これは、すべてではなく、最初の出現を削除する要素です。

 1 public boolean remove(Object o) {  2 if (o == null) {  3 for (Node x = first x != null x = x.next) {  4 if (x.item == null) {  5  unlink(x)  6 return true  7  }  8  }  9 } else { 10 for (Node x = first x != null x = x.next) { 11 if (o.equals(x.item)) { 12  unlink(x) 13 return true 14  } 15  } 16  } 17 return false 18 }

コードを見る

6、要素を変更します

電話でset（int index、E element）メソッド。このリストで指定された要素を、指定された要素に置き換えます。

 public E set(int index, E element) { //Index is determined in an IndexOutOfBoundsException index> = 0 && index <= size abnormality  checkElementIndex(index) Node x = node(index)//Gets the element at the specified index E oldVal = x.item x.item = element//Element specifies the location of the element to be modified to replace the return oldVal//Returns the index position of the original elements }

これは主に指定されたインデックスノード（インデックス）メソッドノードによって取得され、このノードは要素の位置を変更できます。

7、要素を見つける

①、getFirst（）

このリストの最初の要素を返します

1 public E getFirst() { 2 final Node f = first 3 if (f == null) 4 throw new NoSuchElementException() 5 return f.item 6 }

コードを見る

②、getLast（）

このリストの最後の要素を返します

1 public E getLast() { 2 final Node l = last 3 if (l == null) 4 throw new NoSuchElementException() 5 return l.item 6 }

コードを見る

③、get（int index）

指定されたインデックスの要素を返します

1 public E get(int index) { 2  checkElementIndex(index) 3 return node(index).item 4 }

コードを見る

④、indexOf（Object o）

このリストに要素が含まれていない場合、または-1の場合、指定された要素の最初の出現のこのリスト内のインデックスを返します。

 1 //Returns the index in this list of the first occurrence of the specified element, if this list contains no elements or -1.  2 public int indexOf(Object o) {  3 int index = 0  4 if (o == null) {//If the element is to find null (LinkedList can allow null values)  5 for (Node x = first x != null x = x.next) {//The head node to the next node began to be traversed  6 if (x.item == null)  7 return index  8 index++  9  } 10 } else {//If the search element is not null 11 for (Node x = first x != null x = x.next) { 12 if (o.equals(x.item)) 13 return index 14 index++ 15  } 16  } 17 return -1//Can not find returns -1 18 }

コードを見る

8、コレクションを通じて

①、通常のforループ

LinkedList linkedList = new LinkedList() linkedList.add('A') linkedList.add('B') linkedList.add('C') linkedList.add('D') for(int i = 0 i ){ System.out.print(linkedList.get(i)+' ')//A B C D }

コードを見る

コードは単純で、LinkedList get（int index）メソッドを使用して、すべての要素をトラバースします。

ただし、インデックスのすべての要素をトラバースする前に、毎回get（int index）メソッドを使用するため、次の文を理解してください。

上記の例、LinkedListセット、IをA、B、C、Dに入れるのは要素です。トラバースする合計4回：

初めての印刷物A：一度だけトラバースしました。

2回目のパスプリントB：A、Bを見つけてから、プリントを見つける必要があります。

3回目の印刷C：Aを見つけ、次にB、Cを見つけ、最後に印刷を見つける必要があります。

4番目のトラバーサルプリントD：Aを見つけ、次にBを見つけ、次にCを見つけ、最後にDを見つける必要があります。

この要素のコレクションが後ろを見つけるためにもっとたくさんある場合（もちろんここでgetメソッドは前からのトラバースの前半を見つけるように最適化されています、後ろからのトラバースの後半を探してください、しかし必要な時間はまだたくさんあります）より多くの時間を費やしました。では、どのように改善しますか？

②、イテレータ

 1 LinkedList linkedList = new LinkedList()  2 linkedList.add('A')  3 linkedList.add('B')  4 linkedList.add('C')  5 linkedList.add('D')  6  7  8 Iterator listIt = linkedList.listIterator()  9 while(listIt.hasNext()){ 10 System.out.print(listIt.next()+' ')//A B C D 11 } 12 13 //Achieved by the interface adapter mode, is to print the list flashback 14 Iterator it = linkedList.descendingIterator() 15 while(it.hasNext()){ 16 System.out.print(it.next()+' ')//D C B A 17 }

コードを見る

LinkedListコレクションクラスには、要素をトラバースする前に最初から開始せずにトラバースされた各セカンダリ要素にカーソルポイントを移動することにより、実質的に同様の実装メソッドである内部ListItrもあります。その方法は、達成するのが比較的簡単です。

 1 public ListIterator listIterator(int index) {  2  checkPositionIndex(index)  3 return new ListItr(index)  4  }  5  6 private class ListItr implements ListIterator {  7 private Node lastReturned  8 private Node next  9 private int nextIndex  10 private int expectedModCount = modCount  11  12 ListItr(int index) {  13 // assert isPositionIndex(index)  14 next = (index == size) ? null : node(index)  15 nextIndex = index  16  }  17  18 public boolean hasNext() {  19 return nextIndex < size  20  }  21  22 public E next() {  23  checkForComodification()  24 if (!hasNext())  25 throw new NoSuchElementException()  26  27 lastReturned = next  28 next = next.next  29 nextIndex++  30 return lastReturned.item  31  }  32  33 public boolean hasPrevious() {  34 return nextIndex > 0  35  }  36  37 public E previous() {  38  checkForComodification()  39 if (!hasPrevious())  40 throw new NoSuchElementException()  41  42 lastReturned = next = (next == null) ? last : next.prev  43 nextIndex--  44 return lastReturned.item  45  }  46  47 public int nextIndex() {  48 return nextIndex  49  }  50  51 public int previousIndex() {  52 return nextIndex - 1  53  }  54  55 public void remove() {  56  checkForComodification()  57 if (lastReturned == null)  58 throw new IllegalStateException()  59  60 Node lastNext = lastReturned.next  61  unlink(lastReturned)  62 if (next == lastReturned)  63 next = lastNext  64 else  65 nextIndex--  66 lastReturned = null  67 expectedModCount++  68  }  69  70 public void set(E e) {  71 if (lastReturned == null)  72 throw new IllegalStateException()  73  checkForComodification()  74 lastReturned.item = e  75  }  76  77 public void add(E e) {  78  checkForComodification()  79 lastReturned = null  80 if (next == null)  81  linkLast(e)  82 else  83  linkBefore(e, next)  84 nextIndex++  85 expectedModCount++  86  }  87  88 public void forEachRemaining(Consumersuper E> action) {  89  Objects.requireNonNull(action)  90 while (modCount == expectedModCount && nextIndex < size) {  91  action.accept(next.item)  92 lastReturned = next  93 next = next.next  94 nextIndex++  95  }  96  checkForComodification()  97  }  98  99 final void checkForComodification() { 100 if (modCount != expectedModCount) 101 throw new ConcurrentModificationException() 102  } 103 }

コードを見る

ここで重要なのは、目の前にあるmodCountフィールドで、インクリメント演算子modCountになる要素を追加および削除することです。反復中に必要な場合は、組み込みメソッドのセットを操作しているときに削除または追加すると、異常がスローされるためです。 。 （イテレータを使用した追加および削除メソッドは例外をスローしません）

final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException() }

例えば：

 1 LinkedList linkedList = new LinkedList()  2 linkedList.add('A')  3 linkedList.add('B')  4 linkedList.add('C')  5 linkedList.add('D')  6  7  8 Iterator listIt = linkedList.listIterator()  9 while(listIt.hasNext()){ 10 System.out.print(listIt.next()+' ')//A B C D 11 //linkedList.remove()//Here will throw an exception 12 listIt.remove()//This delete operation 13 }

コードを見る

もう1つの形式は、foreachイテレーターループを使用することです。基になる実装イテレーターが使用されます。ここでは説明しません。

LinkedList linkedList = new LinkedList() linkedList.add('A') linkedList.add('B') linkedList.add('C') linkedList.add('D') for(String str : linkedList){ System.out.print(str + '') }

コードを見る

9、およびの反復サイクル効率の違い

 1 LinkedList linkedList = new LinkedList()  2 for(int i = 0 i <10000 i++){//Add ten thousand elements to the list  3  linkedList.add(i)  4 }  5 long beginTimeFor = System.currentTimeMillis()  6 for(int i = 0 i <10000 i++){  7  System.out.print(linkedList.get(i))  8 }  9 long endTimeFor = System.currentTimeMillis() 10 System.out.println ( 'Use common for looping through time 10000 required elements:' + (endTimeFor - beginTimeFor)) 11 12 13 long beginTimeIte = System.currentTimeMillis() 14 Iterator it = linkedList.listIterator() 15 while(it.hasNext()){ 16 System.out.print(it.next()+' ') 17 } 18 long endTimeIte = System.currentTimeMillis() 19 System.out.println ( 'iterates over time using the necessary elements 10000:' + (endTimeIte - beginTimeIte))

結果の印刷：

2つの要素間の時間差が1万の2倍以上になっている場合、10万、100万の要素の場合、速度の差は大きくなります。次の図で説明されています。

通常のforループ：各インデックスの要素をトラバースする前に、すべての訪問の間にすべてのインデックスが作成されます。

イテレータ：要素が訪問されるたびに、要素はカーソルによって現在の訪問の位置を記録し、要素をトラバースして位置を記録します。

参照ドキュメント：https：//docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#