Analyse du code source Java LinkedList (image)

Introduction générale

LinkedList implémente à la fois l'interface List et l'interface Deque, ce qui signifie qu'elle peut être considérée à la fois comme un conteneur séquentiel et une file d'attente (file d'attente), et peut également être considéré comme une pile (Stack). De ce point de vue, LinkedList est tout simplement un champion tous azimuts. Lorsque vous devez utiliser une pile ou une file d'attente, la première chose à considérer est LinkedList. Parce que Java a officiellement déclaré qu'il n'est pas recommandé d'utiliser la classe Stack, et qu'il est recommandé d'utiliser LinkedList, ce qui est encore plus regrettable, c'est qu'il n'y a pas de classe appelée Queue en Java (c'est un nom d'interface).

La couche sous-jacente de LinkedList est implémentée via une liste doublement chaînée Cette section se concentrera sur le processus de maintenance d'une liste doublement chaînée lors de l'insertion et de la suppression éléments, c'est-à-dire la solution entre les fonctions liées à l'interface List, et les connaissances liées à Queue, Stack et Deque seront abordées dans la section suivante. Chaque nœud d'une liste doublement chaînée est représenté par la classe interne Node. LinkedList fait référence à à first et last pour pointer respectivement vers le premier et le dernier élément de la liste chaînée. Notez qu'il n'y a pas d'élément dit factice ici. Lorsque la liste chaînée est vide, et first pointent vers <a href="http://www.php.cn/wiki/62.%20.html" target=" _blank">null<code>last. <a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>

//Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

L'implémentation de LinkedList détermine que toutes les opérations liées aux indices sont en temps linéaire et que la suppression d'éléments au début ou à la fin ne nécessite qu'un temps constant. Afin de rechercher l'efficacité, LinkedList n'implémente pas la synchronisation (syn

chronized). Si un accès simultané par plusieurs threads est requis, vous pouvez d'abord l'envelopper en utilisant la méthode . Collections.synchronizedList()

Method Analysis

add()

La méthode add() a deux versions, l'une est

, cette méthode insère des éléments à la fin de LinkedList car il y a add(E e)Pointe vers la fin de la liste chaînée et l'insertion d'éléments à la fin prend un temps constant. Il vous suffit de modifier quelques références pertinentes ; l'autre est last, qui consiste à insérer des éléments dans le tableau spécifié ci-dessous. Vous devez d'abord trouver l'emplacement spécifique via une recherche linéaire, puis modifier les références pertinentes pour compléter le. opération d’insertion. add(int index, E element)

Combiné avec l'image ci-dessus, nous pouvons voir que la logique de

est très simple. La logique de add(E e)

//add(E e)
public boolean add(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空，这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

est légèrement compliquée et peut être divisée en deux parties. 1. Trouvez d'abord l'emplacement à insérer en fonction de l'index 2. Modifiez la référence et terminez l'opération d'insertion ; . add(int index, E element)

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

La fonction

dans le code ci-dessus est un peu délicate, car la liste chaînée est bidirectionnelle, vous pouvez rechercher du début vers l'arrière, ou vous pouvez rechercher de la fin vers l'avant , cela dépend de la direction dans laquelle vous souhaitez rechercher. En fonction de la condition node(int index), c'est-à-dire si l'index est proche du front-end ou du back-end. La méthode index < (size >> 1)

remove()

a également deux versions. L'une consiste à supprimer le premier élément qui est égal à l'élément spécifié remove(<a href="http. :// www.php.cn/wiki/60.html" target="_blank">Object<code>remove() o), l'autre consiste à supprimer l'élément remove(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> o) à l'indice spécifié. remove(int index)

Les deux opérations de suppression nécessitent 1. Trouver d'abord la référence de l'élément à supprimer, 2. Modifier la référence pertinente pour terminer l'opération de suppression. Lors de la recherche d'une référence à un élément supprimé,

appelle la méthode remove(Object o) de l'élément, tandis que equals utilise le comptage en indice. Les deux méthodes ont une complexité temporelle linéaire. À l'étape 2, les deux méthodes remove(int index) sont complétées via la méthode revome(). Ici, vous devez considérer le cas limite lorsque l'élément supprimé est le premier ou le dernier. unlink(Node<E> x)

//unlink(Node<E> x)，删除一个Node
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    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;//let GC work
    size--;
    return element;
}

get()

Obtient la référence à l'élément à l'indice spécifié, ce qui est obtenu en appelant la méthode get(int index) mentionnée ci-dessus. La méthode node(int index)

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

modifie l'élément à l'indice spécifié à la valeur spécifiée. Elle trouve également d'abord la référence correspondant à l'élément dans le tableau ci-dessous. set(int index, E element), puis le modifie. La valeur de node(int index) dans Node. item

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!