Partagez le code source de plusieurs méthodes courantes dans ArrayList

jdk1.7.0_79

Ce qui précède explique les ArrayList - "Analyse du code source des méthodes courantes dans ArrayList" , cet article décrira brièvement les méthodes courantes de LinkedList Analyser .

LinkedList

est implémenté sur la base d'une liste chaînée, ce qui signifie qu'elle présente les avantages et les inconvénients d'une liste chaînée, avec un accès aléatoire lent et des vitesses d'insertion et de suppression rapides. Puisqu'il s'agit d'une liste chaînée, elle a une structure de données de nœuds et il n'y a aucun problème de capacité. Ajoutez-en simplement une à la fin.

//LinkedList$Nodeprivate 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;
    }
}

Le premier constructeur qui ne prend aucun paramètre par défaut construit une liste chaînée vide.

//1.LinkedList，默认构造方法public LinkedList() {
}

Le deuxième constructeur peut passer une collection en tant que paramètre, et les éléments de la collection doivent être une sous-classe de

LinkedList.

//2.LinkedList，能将一个集合作为参数的构造方法public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

Les deux méthodes de construction sont relativement simples. Examinons ensuite l'insertion et la suppression d'éléments.

public boolean add(E e) {
    linkLast(e);    //将元素添加到链表尾部return true;
}

//LinkedList#linkLastvoid linkLast(E e) {final Node<E> l = last;    //链表尾指针引用暂存final Node<E> newNode = new Node<>(l, e, null);    //构造新节点last = newNode;    //将链表的尾指针指向新节点if (l == null)    //此时为第一次插入元素first = newNode;elsel.next = newNode;    
    size++;    //链表数据总数+1modCount++;    //modCount变量在《有关ArrayList常用方法的源码解析》提到过，增删都会+1，防止一个线程在用迭代器遍历的时候，另一个线程在对其进行修改。}

Les étudiants qui ont étudié la « Structure des données » pensent que le fonctionnement des listes chaînées ne sera pas étranger. Jetons un coup d'œil à la suppression. la position spécifiée. Méthode Element

remove(int).

//LinkedList#removepublic E remove(int index) {
    checkElementIndex(index);    //检查是否越界 index >= 0 && index <= sizereturn unlink(node(index));    //调用node方法查找并返回指定索引位置的Node节点}

//LinkedList#node，根据索引位置返回Node节点Node<E> node(int index) {if (index < (size >> 1)) {    //size >> 1 = size / 2，如果索引位于链表前半部分，则移动fisrt头指针进行查找Node<E> x = first;for (int i = 0; i < index; i++)
            x = x.next;return x;
    } else {    //如果索引位于链表后半部分，则移动last尾指针进行查找Node<E> x = last;for (int i = size - 1; i > index; i--)
            x = x.prev;return x;
    }
}

Rechercher

index Après Node, appelez la méthode unlink pour supprimer le nœud .

//LinkedList#unlink，一看即懂E unlink(Node<E> x) {// assert x != null;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;
    size--;
    modCount++;return element;
}

Vous pouvez voir dans le code les avantages de

LinkedList et ArrayList Inconvénient , puisqu'il s'agit uniquement d'une simple structure de données de liste chaînée, les autres méthodes ne seront pas analysées.

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!