JDK1.8 lähtekood (kuus) - java.util.LinkedList klass

Jdk1 8 Source Code Java



Eelmises blogis tutvustasime kollektsioonide loendi tüüpilisi rakendusi ArrayList Me teame, et ArrayList koosneb massiivist, selles blogis tutvustame veel ühte tüüpilist rakenduse LinkedList List kogumit, mis koosneb lingitud loendite massiivist, loendi sissejuhatusest, See ajaveeb Meid on ka üksikasjalikult kirjeldatud, see ajaveeb näitame teile, kuidas LinkedListi rakendatakse.

1, LinkedList määratletud

LinkedList lingitud loend on järjestatud elementide kogu, mida saab korrata.



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



ArrayList ja Set as, LinkedList Cloneable liidese kogu ning rakendab ka Serializable liidest, kloonimist ja neid kasutatakse jadatavuse toetamiseks. Ütlematagi selge, et liidese loend, määratleme meetodi tüübikomplekti Spetsifikatsioonide loend.



Pange tähele, et seoses kogumikuga ArrayList rakendab LinkedList rohkem kui ja Liides, mis on kahesuunaline liides järjekorda, järjekord on kahesuunaline mõlemad pooled saab suurendada ja kustutada toiminguid.

2, välja omadused

 //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

Pange tähele, et on olemas Node klass, mis on sisemine klass LinkedList klass, kus iga element tähistab Node klassi objekte, LinkedListi kogu koosneb paljudest Node objektidest, mis on sarnased käsikäes.

 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 }
Kuva kood

Nagu allpool näidatud:



Joonis LinkedList neljal elemendil, st sõlmel neli objekti, suurus = 4, pea osutab esimesele elemendileA, saba osutab viimasele sõlmeelemendileD.

3, konstruktorid

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

LinkedListil on kaks konstruktorit, millest esimene on vaikimisi tühi konstruktor, teine ​​eksemplaride kogum on elementide lisamine olemasolevale Collection LinkedList-ile, kõne on addAll () meetod, mida me selgitame allpool.

Märkus: LinkedListi loendi suurus ei ole lähtestusdisainer, kuna loendid nagu massiiv, tuleb massiiviks määrata määratletud suurus ja seejärel mäluruumi eraldamiseks, kuid loend pole sama, see ei määra kursori järgi liikumine järgmise osuti juurde eraldatud mäluaadressile.

4, lisage elemendid

① 、 addFirst (E e)

Lisab määratud elemendi loendi päisesse

 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 }
Kuva kood

② 、addLast (E e) ja lisa (E e)

Lisage määratud element loendi lõppu

 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 }
Kuva kood

③ 、lisa (int indeks, E element)

Määratud element selles loendis määratud positsiooni

 //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++ }
Kuva kood

④ 、addAll (kogu c)

Määratud järjestuses määrab kogu tagastatud iteraator kõik elemendid, mis on selles loendis lisatud.

Sellel meetodil on ka addAll (int indeks, kogu c), kõigi elementide komplekt, mis on sisestatud määratud asukoha indeksisse. Tegelikult

addAll (kogu c) == addAll (suurus, kogu c)

Allikas järgmine:

 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 }
Kuva kood

LinkedListi kollektsiooni elementide lisamise erinevate võimaluste nägemiseks leiame, et iga kord, kui lisate elemente, muudab LinkedList iga kord lihtsalt kursori viidet elemendile ja järgmist kursori viidet ning laiendust ei toimu. , Erinevalt ArrayList'ist on vaja mahtu ja sisestuselementide keskel peavad kõik elemendid suure tõhususe erinevuse tagasi viima, kui kaks sisestuselementi see järgmine ajaveeb mõlema tõhusust ja kuidas valida juhtumite kogum analüüsimiseks.

Samuti on igal operatsiooni lisamisel modCount ++ operatsioon,

5, eemaldage elemendid

Elementide kustutamine ja elementide lisamine, nagu ühe sõlme punkti vahetamine järgmise sõlme ja võrdluspunktiga, mitte nii, nagu siin graafika näitab.

①, eemaldage () jaremoveFirst ()

Eemaldatud sellest loendist ja tagastab esimese elemendi

 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 }
Kuva kood

② 、removeLast ()

Eemalda sellest loendist ja tagastab viimase elemendi

 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 }
Kuva kood

③ 、eemalda (int indeks)

Kustutage see loendi element asukohast

 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 }
Kuva kood

、 、 Eemalda (objekt o)

Kui on, kustutage määratud elemendi esmakordse loendist

Selle meetodi sisuliselt ja eemaldage (int indeks) ei ole palju erinevusi, tuleb märkida kustutades ringluse elementide järgi, on element esimese esinemise kustutamiseks, mitte kõik.

 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 }
Kuva kood

6, muutke elemente

Helistadesset (int indeks, E element) meetod, asendades selles loendis määratud elemendid määratud elementidega.

 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 }

Selle omandab peamiselt määratud indekssõlme (indeksi) meetodi sõlm, see sõlm saab seejärel muuta elemendi positsiooni.

7, leidke elemendid

① 、 getFirst ()

Tagastab selle loendi esimese elemendi

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

② 、 getLast ()

Tagastab loendi viimase elemendi

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

③ 、 saada (int indeks)

Tagastab elemendi määratud indeksis

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

④ 、 indexOf (objekt o)

Tagastab selles loendis oleva indeksi määratud elemendi esmakordsest esinemisest, kui selles loendis pole elemente või -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 }
Kuva kood

8, kogu kaudu

①, tavaline silmuseks

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 }
Kuva kood

Kood on lihtne, me kasutame LinkedList get (int index) meetodit, läbides kõik elemendid.

Pange siiski tähele, et get (int index) meetod on iga kord enne kõigi indeksi elementide läbimist, nii et mõistke seda lauset:

Ülaltoodud näide: LinkedList-komplekt I, A, B, C, D on element. Kokku neli korda läbimiseks:

Esimene kord trükise A kaudu: lihtsalt üks kord läbitud.

Teise passi print B: peate leidma A, B ja seejärel leidma print.

Kolmanda passi printimine C: Pean leidma A ja seejärel leidma B, C ja lõpuks leidma print.

Neljas läbitav trükk D: peate leidma A, seejärel leidma B ja seejärel leidma asukoha C ja lõpuks leidma D.

Kui see elementide kogumik on tagakülje leidmiseks palju rohkem (loomulikult on siin meetod meetod optimeeritud, et leida eestpoolt läbisõitmise esimene pool, otsige läbimise teine ​​pool tagantpoolt, kuid vajalik aeg on siiski palju ) rohkem aega kulutatud. Kuidas siis seda parandada?

②, kordajad

 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 }
Kuva kood

LinkedListi kogumisklassil on ka sisemine ListItr, rakendatud meetod, mis on põhimõtteliselt sarnane, liigutades kursoripunkti igale teisele elemendile, mis on läbitud, alustamata nullist enne elemendi läbimist. Selle meetodi saavutamine on suhteliselt lihtne:

 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 }
Kuva kood

Siinkohal on oluline märkida, et väli modCount lisab ja eemaldab meie ees elemendid, mis on operaatori modCount inkrement, sest kui soovite iteratsiooni ajal kustutada või lisada sisseehitatud meetodi kasutamisel, viskab see . (Lisamiste ja kustutuste meetod iteraatori abil ei tee erandit)

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

Näiteks:

 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 }
Kuva kood

Teine vorm on kasutada foreach iteraatori tsüklit, kasutatakse aluseks olevat iteratorit, me ei tee seda siin.

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

9 ja tsükli iteratiivne efektiivsuse erinevus

 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))

Prinditulemused:

Olete kahe elemendi kümne tuhande, kui sada tuhat, üks miljon, ajavahe rohkem kui kahekordistanud, siis kiiruse vahe suureneb. Seda selgitatakse järgmise graafikaga:

Tavaline tsükli jaoks: enne iga indeksi elementide läbimist kõik külastuse vahel olevad indeksid.

Iteraator: pärast elemendi iga külastust registreerib kursor elemendi praeguse külastuse asukoha, läbides elemendi, rekordi asukoha.

Viitedokument: https: //docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#