Java-Verbesserungskapitel (22)-----LinkedList

1. Übersicht

LinkedList implementiert die List-Schnittstelle genau wie ArrayList, mit der Ausnahme, dass ArrayList eine Implementierung eines Arrays variabler Größe der List-Schnittstelle ist und LinkedList eine Implementierung einer verknüpften Liste ist der List-Schnittstelle. Basierend auf der Implementierung der verknüpften Liste ist LinkedList beim Einfügen und Löschen besser als ArrayList, während der wahlfreie Zugriff ArrayList unterlegen ist.

 LinkedList implementiert alle optionalen Listenoperationen und lässt alle Elemente einschließlich Null zu.

Zusätzlich zur Implementierung der List-Schnittstelle bietet die LinkedList-Klasse auch eine einheitliche Benennungsmethode zum Abrufen, Entfernen und Einfügen von Elementen am Anfang und Ende der Liste. Diese Operationen ermöglichen die Verwendung verknüpfter Listen als Stapel, Warteschlangen oder Deques.

Diese Klasse implementiert die Deque-Schnittstelle und stellt First-In-First-Out-Warteschlangenoperationen für Add und Poll sowie andere Stack- und Double-Ended-Warteschlangen bereit Operationen.

 Alle Vorgänge werden nach Bedarf für doppelt verknüpfte Listen ausgeführt. Bei der Indizierung in einer Liste wird die Liste vom Anfang oder Ende aus durchlaufen (vom Ende, das näher am angegebenen Index liegt).

Außerdem ist diese Implementierung wie ArrayList nicht synchronisiert.

(das Obige stammt aus der JDK 6.0-API).

2. Quellcode-Analyse

2.1

 Schauen wir uns zunächst die Definition von LinkedList an:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

 Aus diesem Code können wir deutlich erkennen, dass LinkedList AbstractSequentialList erbt und List, Deque, Cloneable und Serializable implementiert. AbstractSequentialList stellt die Backbone-Implementierung der List-Schnittstelle bereit und minimiert dadurch den Arbeitsaufwand für die Implementierung dieser Schnittstelle, die von Datenspeichern mit „sequentiellem Zugriff“ (z. B. verknüpften Listen) unterstützt wird, wodurch die Komplexität der Implementierung der List-Schnittstelle verringert wird. Deque a linear Die Sammlung unterstützt das Einfügen und Entfernen von Elementen an beiden Enden und definiert den Betrieb einer doppelendigen Warteschlange.

                                                                                                                                                                                                                 

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

 

wobei size die Größe der LinkedList darstellt , Header stellt den Header der verknüpften Liste dar und Entry ist das Knotenobjekt.

private static class Entry<E> {
        E element;        //元素节点
        Entry<E> next;    //下一个元素
        Entry<E> previous;  //上一个元素

        Entry(E element, Entry<E> next, Entry<E> previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }

Das Obige ist der Quellcode des Entry-Objekt, Entry ist die interne Klasse von LinkedList, die die gespeicherten Elemente definiert. Das vorherige Element und das folgende Element dieses Elements sind die typischen Definitionsmethoden für doppelt verknüpfte Listen.

2.3, die konstruktive Methode

linkedList hat die beiden konstruktiven Methoden LinkedInLis () und LinkedList (Sammlung) erweitert & lt; erweitert E>

 

/**
     *  构造一个空列表。
     */
    public LinkedList() {
        header.next = header.previous = header;
    }
    
    /**
     *  构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

LinkedList() erstellt eine leere Liste. Es enthält kein Element, es zeigt nur das vorherige Element und das nächste Element des Header-Knotens auf sich selbst.

LinkedList(Collection9924f57fa862942192503acf9581b0a5 c): Erstellt eine Liste mit den Elementen in der angegebenen Sammlung, wie sie vom Iterator ihrer Sammlung zurückgegeben werden. In der Reihenfolge anordnen . Der Konstruktor ruft zunächst LinkedList() auf, um eine leere Liste zu erstellen, und ruft dann die Methode addAll() auf, um alle Elemente in der Sammlung zur Liste hinzuzufügen. Das Folgende ist der Quellcode von addAll():

/**
     *  添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    
    /**
     * 将指定 collection 中的所有元素从指定位置开始插入此列表。其中index表示在其中插入指定collection中第一个元素的索引
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        //若插入的位置小于0或者大于链表长度，则抛出IndexOutOfBoundsException异常
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        Object[] a = c.toArray();
        int numNew = a.length;    //插入元素的个数
        //若插入的元素为空，则返回false
        if (numNew == 0)
            return false;
        //modCount:在AbstractList中定义的，表示从结构上修改列表的次数
        modCount++;
        //获取插入位置的节点，若插入的位置在size处，则是头节点，否则获取index位置处的节点
        Entry<E> successor = (index == size ? header : entry(index));
        //插入位置的前一个节点，在插入过程中需要修改该节点的next引用：指向插入的节点元素
        Entry<E> predecessor = successor.previous;
        //执行插入动作
        for (int i = 0; i < numNew; i++) {
            //构造一个节点e，这里已经执行了插入节点动作同时修改了相邻节点的指向引用
            //
            Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
            //将插入位置前一个节点的下一个元素引用指向当前元素
            predecessor.next = e;
            //修改插入位置的前一个节点，这样做的目的是将插入位置右移一位，保证后续的元素是插在该元素的后面，确保这些元素的顺序
            predecessor = e;
        }
        successor.previous = predecessor;
        //修改容量大小
        size += numNew;
        return true;
    }

An der addAll()-Methode sind zwei Methoden beteiligt. Eine davon ist enter(int index), eine private Methode von LinkedList, die hauptsächlich zum Suchen des Knotenelements an der Indexposition verwendet wird.

/**
     * 返回指定位置(若存在)的节点元素
     */
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
                    + size);
        //头部节点
        Entry<E> e = header;
        //判断遍历的方向
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

       从该方法有两个遍历方向中我们也可以看出LinkedList是双向链表，这也是在构造方法中为什么需要将header的前、后节点均指向自己。

       如果对数据结构有点了解，对上面所涉及的内容应该问题，我们只需要清楚一点：LinkedList是双向链表，其余都迎刃而解。

由于篇幅有限，下面将就LinkedList中几个常用的方法进行源码分析。

       2.4、增加方法

       add(E e): 将指定元素添加到此列表的结尾。

public boolean add(E e) {
    addBefore(e, header);
        return true;
    }

       该方法调用addBefore方法，然后直接返回true，对于addBefore()而已，它为LinkedList的私有方法。

private Entry<E> addBefore(E e, Entry<E> entry) {
        //利用Entry构造函数构建一个新节点 newEntry，
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
        //修改newEntry的前后节点的引用，确保其链表的引用关系是正确的
        newEntry.previous.next = newEntry;
        newEntry.next.previous = newEntry;
        //容量+1
        size++;
        //修改次数+1
        modCount++;
        return newEntry;
    }

       在addBefore方法中无非就是做了这件事：构建一个新节点newEntry，然后修改其前后的引用。

       LinkedList还提供了其他的增加方法：

       add(int index, E element)：在此列表中指定的位置插入指定的元素。

       addAll(Collection2d4902c92e1e7bfd574f59708c57776a c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。

       addAll(int index, Collection2d4902c92e1e7bfd574f59708c57776a c)：将指定 collection 中的所有元素从指定位置开始插入此列表。

       AddFirst(E e): 将指定元素插入此列表的开头。

       addLast(E e): 将指定元素添加到此列表的结尾。

       2.5、移除方法

       remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）。该方法的源代码如下：

public boolean remove(Object o) {
        if (o==null) {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }

       该方法首先会判断移除的元素是否为null，然后迭代这个链表找到该元素节点，最后调用remove(Entry1a4db2c2c2313771e5742b6debf617a1 e)，remove(Entry1a4db2c2c2313771e5742b6debf617a1 e)为私有方法，是LinkedList中所有移除方法的基础方法，如下：

private E remove(Entry<E> e) {
        if (e == header)
            throw new NoSuchElementException();

        //保留被移除的元素：要返回
        E result = e.element;
        
        //将该节点的前一节点的next指向该节点后节点
        e.previous.next = e.next;
        //将该节点的后一节点的previous指向该节点的前节点
        //这两步就可以将该节点从链表从除去：在该链表中是无法遍历到该节点的
        e.next.previous = e.previous;
        //将该节点归空
        e.next = e.previous = null;
        e.element = null;
        size--;
        modCount++;
        return result;
    }

       其他的移除方法：

       clear()： 从此列表中移除所有元素。

       remove()：获取并移除此列表的头（第一个元素）。

       remove(int index)：移除此列表中指定位置处的元素。

       remove(Objec o)：从此列表中移除首次出现的指定元素（如果存在）。

       removeFirst()：移除并返回此列表的第一个元素。

       removeFirstOccurrence(Object o)：从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。

 removeLast(): Entfernt das letzte Element dieser Liste und gibt es zurück.

removeLastOccurrence(Object o): Entfernen Sie das letzte Vorkommen des angegebenen Elements aus dieser Liste (beim Durchlaufen der Liste von Kopf bis Ende).

                                                                                                                                              Vergleichen Sie und geben Sie dann den aktuellen Wert zurück.

      get(int index): Gibt das Element an der angegebenen Position in dieser Liste zurück.

    getFirst(): Gibt das erste Element dieser Liste zurück.

    getLast(): Gibt das letzte Element dieser Liste zurück.

 indexOf(Object o): Gibt den Index des ersten Vorkommens des angegebenen Elements in dieser Liste zurück, oder -1, wenn das Element nicht darin enthalten ist Liste.

 lastIndexOf(Object o): Gibt den Index des zuletzt angegebenen Elements zurück, das in dieser Liste erscheint, oder -1, wenn dieses Element nicht in dieser Liste enthalten ist .

Das ist es Kapitel zur Java-Verbesserung (22) ----- Inhalt von LinkedList. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!