Kapitel zur Java-Verbesserung (32) ----- Listenzusammenfassung-javaLernprogramm-php.cn

Zuvor hat LZ den Großteil des Wissens über die List-Schnittstelle, wie ArrayList, LinkedList, Vector und Stack, vollständig eingeführt. Durch diese Wissenspunkte können Sie ein tieferes Verständnis der List-Schnittstelle erlangen. Nur durch Induktion zusammengefasstes Wissen ist Ihr Wissen. Daher wird LZ im Folgenden eine Zusammenfassung der List-Schnittstelle erstellen. Empfohlene Lektüre:

Java Improvement Chapter (21)---- - ArrayList

> Java-Verbesserungskapitel (29)-----Vektor

Java Improvement Chapter (Sanyi) -----Stack

1. Übersicht über die Listenschnittstelle

Die Listenschnittstelle wird zu einer geordneten Sammlung, also einer Sequenz. Diese Schnittstelle kann die Einfügeposition jedes Elements in der Liste präzise steuern, und Benutzer können auf Elemente basierend auf ihrem ganzzahligen Index (Position in der Liste) zugreifen und nach Elementen in der Liste suchen. Das folgende Bild ist das Rahmendiagramm der Listenschnittstelle:

Mit dem Im Rahmendiagramm können Sie die Struktur von List klar verstehen. Die Klassen und Schnittstellen lauten wie folgt:

Die Stammschnittstelle in der Sammlung Hierarchie. Es stellt eine Menge von Objekten dar, die auch Elemente einer Sammlung genannt werden. Für Collection wird keine direkte Implementierung bereitgestellt, und alle Implementierungen liegen in der Verantwortung ihrer Unterklassen.

AbstractCollection:

Stellt eine Backbone-Implementierung der Collection-Schnittstelle bereit, um die Notwendigkeit der Implementierung dieser Schnittstellenarbeit zu minimieren. Damit wir eine unveränderliche Sammlung implementieren können, müssen wir nur diese Klasse erweitern und Implementierungen der Iterator- und Größenmethoden bereitstellen. Um jedoch eine änderbare Sammlung zu implementieren, muss die Add-Methode dieser Klasse überschrieben werden (andernfalls wird UnsupportedOperationException ausgelöst), und der von der Iterator-Methode zurückgegebene Iterator muss auch seine Remove-Methode implementieren.

Terator:

Iterator.

Liste und ruft die aktuelle Position des Iterators in der Liste ab.

. Es stellt eine geordnete Warteschlange dar.

AbstractList: Backbone-Implementierung der List-Schnittstelle, um die Implementierung der Datenspeicherung mit „wahlfreiem Zugriff“ (z. B als Array) ist erforderlich, um mit der Unterstützung dieser Schnittstelle arbeiten zu können.

Warteschlange: Warteschlange. Stellt grundlegende Einfüge-, Abruf- und Prüfvorgänge für die Warteschlange bereit.

Deque: Eine lineare Sammlung, die das Einfügen und Entfernen von Elementen an beiden Enden unterstützt. Die meisten Deque-Implementierungen haben keine feste Begrenzung der Anzahl der Elemente, die sie enthalten können, aber diese Schnittstelle unterstützt sowohl Deques mit einer Kapazitätsbeschränkung als auch Deques ohne feste Größenbeschränkung.

Die für den Zugriff auf diese Schnittstelle erforderlichen Arbeiten, die von einem Datenspeicher wie einer verknüpften Liste unterstützt werden. In gewissem Sinne ist diese Klasse dasselbe wie die Implementierung einer „Random Access“-Methode für einen Listeniterator einer Liste.

LinkedList: Verknüpfte Listenimplementierung der >Listenschnittstelle. Es implementiert alle optionalen Listenoperationen.

Es implementiert alle optionalen Listenoperationen und lässt alle Elemente einschließlich Null zu. Zusätzlich zur Implementierung der List-Schnittstelle stellt diese Klasse auch Methoden zur Verfügung, um die Größe des Arrays zu manipulieren, das intern zum Speichern der Liste verwendet wird.

Vector:

implementiert ein erweiterbares Objektarray. Wie ein Array enthält es Komponenten, auf die über ganzzahlige Indizes zugegriffen werden kann.

Stapel:

Last-in-first-out (LIFO) Objektstapel. Es erweitert die Klasse Vector um fünf Operationen, die es ermöglichen, Vektoren als Stapel zu behandeln.

Enumeration:

Enumeration, ein Objekt, das diese Schnittstelle implementiert. Es generiert eine Reihe von Elementen, eines nach dem anderen ein Mal eins. Kontinuierliche Aufrufe der nextElement-Methode geben eine Folge aufeinanderfolgender Elemente zurück.

2. Nutzungsszenarien

Der grundlegende Zweck des Wissenslernens besteht darin, es zu nutzen. Jeder Wissenspunkt hat seinen Anwendungsbereich. Das Gleiche gilt für Sammlungen. Die Sammlungsfamilie in Java ist sehr groß und jedes Mitglied verfügt über das am besten geeignete Verwendungsszenario. Als ich zum ersten Mal mit List in Kontakt kam, sagte LZ: Wenn es sich um Vorgänge wie „Stapel“, „Warteschlange“ und „verknüpfte Liste“ handelt, geben Sie bitte der Verwendung von List Vorrang.

Die Liste, um die es sich handelt, ist wie folgt unterteilt:

1. Wenn Sie schnell Elemente einfügen und löschen müssen, müssen Sie verwenden LinkedList.

2. Wenn Sie schnell auf Elemente zugreifen müssen, müssen Sie ArrayList verwenden.

3. Für „Single-Thread-Umgebung“ oder „Multi-Thread-Umgebung, aber List wird nur von einem Thread betrieben“ müssen Sie die Verwendung von Asynchronität in Betracht ziehen Klassen Wenn es sich um eine „Multithread-Umgebung“ handelt und List von mehreren Threads gleichzeitig betrieben werden kann, sollten Sie die Verwendung einer synchronisierten Klasse (z. B. Vector) in Betracht ziehen.

2.1 ArrayList, LinkedList-Leistungsanalyse

Wir haben auch etwas über die Nutzungsszenarien und die Unterschiede zwischen ihnen erfahren.

插入 100000元素ArrayList花费 3900 毫秒
插入 100000元素LinkedList花费 15 毫秒
插入 100000元素Vector花费 3933 毫秒
--------------------------------------
读取100000元素ArrayList花费 0 毫秒
读取100000元素LinkedList花费 8877 毫秒
读取100000元素Vector花费 16 毫秒
--------------------------------------
删除100000元素ArrayList花费 4618 毫秒
删除100000元素LinkedList花费 16 毫秒
删除100000元素Vector花费 4759 毫秒

Nach dem Login kopieren

从上面的运行结果我们可以清晰的看出ArrayList、LinkedList、Vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, E element),delete、get方法各位如有兴趣可以研究研究。

首先我们先看三者之间的源码：

ArrayList

public void add(int index, E element) {
        rangeCheckForAdd(index);   //检查是否index是否合法

        ensureCapacityInternal(size + 1);  //扩容操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);    //数组拷贝
        elementData[index] = element;   //插入
        size++;
    }

Nach dem Login kopieren

rangeCheckForAdd、ensureCapacityInternal两个方法没有什么影响，真正产生影响的是System.arraycopy方法，该方法是个JNI函数，是在JVM中实现的。声明如下：

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

Nach dem Login kopieren

目前LZ无法看到源码，具体的实现不是很清楚，不过System.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着ArrayList的add(int index, E element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。

LinkedList

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)     //插入位置在末尾
            linkLast(element);
        else                   
            linkBefore(element, node(index));
    }

Nach dem Login kopieren

该方法比较简单，插入位置在末尾则调用linkLast方法，否则调用linkBefore方法，其实linkLast、linkBefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：

Node<E> node(int index) {
        if (index < (size >> 1)) {    //如果index 小于 size/2 则从头开始查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {   //如果index 大于 size/2 则从尾部开始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

Nach dem Login kopieren

所以linkedList的插入动作比ArrayList动作快就在于两个方面。1：linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

Vector

Vector的实现机制和ArrayList一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：

public void add(int index, E element) {
        insertElementAt(element, index);
    }
    
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

Nach dem Login kopieren

上面是针对ArrayList、LinkedList、Vector三者之间的add（int index,E element)方法的解释，解释了LinkedList的插入动作要比ArrayList、Vector的插入动作效率为什么要高出这么多！至于delete、get两个方法LZ就不多解释了。

同时LZ在写上面那个例子时发现了一个非常有趣的现象，就是linkedList在某些时候执行add方法时比ArrayList方法会更慢！至于在什么情况？为什么会慢LZ下篇博客解释，当然不知道这个情况各位是否也遇到过？？

2.2、Vector和ArrayList的区别

四、更多

java提高篇（二一）-----ArrayList

java提高篇（二二）-----LinkedList

java提高篇（二九）-----Vector

Java-Verbesserungskapitel (1. März)-----Stack

und Oben Dies ist der Inhalt, der in Kapitel 32 zur Java-Verbesserung zusammengefasst ist. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (m.sbmmt.com).