Chapitre d'amélioration Java (22) -----LinkedList

1. Présentation

LinkedList implémente l'interface List tout comme ArrayList, sauf qu'ArrayList est une implémentation d'un tableau de taille variable de l'interface List et LinkedList est une implémentation d'une liste chaînée de l'interface Liste. Basé sur l'implémentation de la liste chaînée, LinkedList est meilleur que ArrayList lors de l'insertion et de la suppression, tandis que l'accès aléatoire est inférieur à ArrayList.

 LinkedList implémente toutes les opérations de liste facultatives et autorise tous les éléments, y compris null.

En plus d'implémenter l'interface List, la classe LinkedList fournit également une méthode de dénomination unifiée pour obtenir, supprimer et insérer des éléments au début et à la fin de la liste. Ces opérations permettent d'utiliser des listes chaînées comme piles, files d'attente ou deques.

Cette classe implémente l'interface Deque, fournissant des opérations de file d'attente premier entré, premier sorti pour l'ajout et l'interrogation, ainsi que d'autres piles et files d'attente à double extrémité opérations.

 Toutes les opérations sont effectuées comme requis pour les listes doublement chaînées. L'indexation dans une liste parcourra la liste depuis le début ou la fin (depuis la fin la plus proche de l'index spécifié).

De plus, comme ArrayList, cette implémentation n'est pas synchronisée.

(ce qui précède est extrait de l'API JDK 6.0).

2. Analyse du code source

2.1.

 Tout d'abord, regardons la définition de LinkedList :

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

 À partir de ce code, nous pouvons clairement voir que LinkedList hérite de AbstractSequentialList et implémente List, Deque, Cloneable et Seriallessly. AbstractSequentialList fournit l'implémentation principale de l'interface List, minimisant ainsi le travail requis pour implémenter cette interface prise en charge par les magasins de données à « accès séquentiel » (tels que les listes chaînées), réduisant ainsi la complexité d'implémentation de l'interface List. Deque un linéaire Collection prend en charge l'insertion et la suppression d'éléments aux deux extrémités et définit le fonctionnement d'une file d'attente à double extrémité.

                                                                                                                                                                                                                       

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

 

où la taille représente la taille de la LinkedList , Header représente l'en-tête de la liste chaînée et Entry est l'objet nœud.

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;
        }
    }

Ce qui précède est le code source du Objet Entry, Entry est la classe interne de LinkedList, qui définit les éléments stockés. L'élément précédent et l'élément suivant de cet élément sont les méthodes typiques de définition de liste doublement chaînée.

<<>

2.3, la méthode constructive

linkedList a augmenté les deux méthodes constructives : linkedLis() et linkedList (collection & lt ? étend E> ;

 

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

LinkedList() construit une liste vide. Il ne contient aucun élément, il pointe simplement l'élément précédent et l'élément suivant du nœud d'en-tête vers lui-même.

LinkedList(Collection c) : Construit une liste contenant les éléments de la collection spécifiée tels que renvoyés par l'itérateur de sa collection. Organiser dans l'ordre . Le constructeur appelle d'abord LinkedList() pour construire une liste vide, puis appelle la méthode addAll() pour ajouter tous les éléments de la Collection à la liste. Voici le code source de 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;
    }

Dans la méthode addAll(), deux méthodes sont impliquées. L'une est Entry(int index), qui est une méthode privée de LinkedList et est principalement utilisée pour trouver l'élément de nœud à la position d'index.

/**
     * 返回指定位置(若存在)的节点元素
     */
    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(Collection c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。

addAll(int index, Collection 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(Entry e)，remove(Entry 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() : supprime et renvoie le dernier élément de cette liste.

removeLastOccurrence(Object o) : Supprime la dernière occurrence de l'élément spécifié de cette liste (lors du parcours de la liste de la tête à la queue).

                                                                                                                                               Comparez, puis renvoyez la valeur actuelle.

      get(int index) : renvoie l'élément à la position spécifiée dans cette liste.

    getFirst() : renvoie le premier élément de cette liste.

    getLast() : Renvoie le dernier élément de cette liste.

 indexOf(Object o) : renvoie l'index de la première occurrence de l'élément spécifié dans cette liste, ou -1 si l'élément n'est pas inclus dans cette liste. liste.

 lastIndexOf(Object o) : Renvoie l'index du dernier élément spécifié qui apparaît dans cette liste, ou -1 si cet élément n'est pas inclus dans cette liste .

C'est tout Chapitre sur l'amélioration de Java (22) ----- Contenu de LinkedList, veuillez faire attention au site Web PHP chinois (www.php.cn) pour plus de contenu connexe !