Dans l'article précédent, nous avons analysé la mise en œuvre sous-jacente de ArrayList et savions que l'implémentation sous-jacente de ArrayList est basée sur les Arrays, il a donc les caractéristiques de la recherche et de la modification rapides pendant l'insertion et la suppression lente. La liste Linked introduite dans cet article est une autre implémentation de l'interface de liste. Sa couche sous-jacente est basée sur une liste liée bidirectionnelle. Par conséquent, il a les caractéristiques de l'insertion et de la suppression rapides lors de la recherche et de la modification lentes. De plus, les fonctions des files d'attente et des piles peuvent être réalisées grâce à la fonction de la liste liée bidirectionnelle. La structure sous-jacente de la liste liée est illustrée dans la figure ci-dessous.
F représente la référence du nœud de tête, L représente la référence du nœud de queue, et chaque nœud dans la liste liée a trois éléments, à savoir la référence du nœud avant (P), la valeur de l'élément de nœud (E) et la référence de nœud suivante (n). Le nœud est représenté par le nœud de classe interne, regardons sa structure interne.
// nœud classe interne de classe statique privée nœud <e> {e item; // Node d'élément <e> Suivant; // Node du nœud suivant <E> PREV; // Node de nœud précédent (nœud <e> prev, élément e, nœud <e> suivant) {this.item = élément; this.next = suivant; this.prev = prev; }}Le nœud de classe interne est en fait très simple, avec seulement trois variables membre et un constructeur. L'élément représente la valeur du nœud, ensuite est la référence au nœud suivant, et Pré prévu est la référence au nœud précédent. Ces trois valeurs sont passées par le constructeur. Ensuite, jetons un coup d'œil aux variables membre et aux constructeurs de LinkedList.
// Le nombre d'éléments définis est traduit int size = 0; // Le nœud d'en-tête fait référence au nœud transitoire <e> d'abord; // le nœud de queue fait référence au nœud transitoire <e> dernier; // le constructeur sans paramètre Public LinkedList () {} // Le constructeur a transmis dans la collection externe publique LinkedList (collection <? Étend E> C) {this (); addall (c);}LinkedList détient une référence au nœud d'en-tête et une référence au nœud de queue. Il a deux constructeurs, l'un est un constructeur sans paramètre, et l'autre est un constructeur transmis à la collection externe. Contrairement à ArrayList, LinkedList ne spécifie pas le constructeur de taille initiale. Découvrez ses méthodes d'ajout, de supprimer, de modifier et de rechercher.
// ajouter (add) public booléen add (e e) {// ajouter linkLast (e); return true;} // add (insert) public void add (int index, e élément) {checkPositionIndex (index); if (index == size) {// ajouter linkLast (élément); } else {// insérer linkefore (élément, node (index)); }} // delete (donner l'index) public e supprime (int index) {// Vérifiez si l'indice est légal CheckElementIndex (index); return Unlink (node (index));} // delete (élément donné) public booléen disover (objet o) {if (o == null) {for (node <e> x = first; x! = null; x = x.next) {if (x.item == null) {Unlink (x); Retour Vrai; }}} else {// Liste de liaison de transmission pour (nœud <e> x = premier; x! = null; x = x.next) {if (o.equals (x.item)) {// delete Unlink (x); Retour Vrai; }}} return false;} // Modifier le public e set (int index, e élément) {// Vérifiez si l'indice est légal checkElementIndex (index); // Obtenez la référence du nœud de l'indice spécifié nœud <e> x = nœud (index); // Obtenez la valeur du nœud d'indice spécifié E OldVal = X.Item; // Définissez l'élément de nœud sur la nouvelle valeur x.item = élément; // Renvoie la valeur précédente return oldVal;} // vérifier le public e get (int index) {// Vérifiez si l'indice est légal CheckElementIndex (index); // renvoie la valeur du nœud du nœud de retour indiqué spécifié (index) .item;}La méthode d'ajout d'éléments dans LinkedList est principalement d'appeler les deux méthodes LinkLast et LinkBefore. La méthode LinkLast consiste à lier un élément derrière la liste liée, et la méthode LinkBefore consiste à insérer un élément au milieu de la liste liée. La méthode de suppression de LinkedList supprime un élément de la liste liée en appelant la méthode non link. Jetons un coup d'œil au code de base des opérations d'insertion et de suppression de la liste liée.
// Avant de lier au nœud spécifié void linkBefore (e e, nœud <e> succ) {// Obtenez la référence du nœud précédente du nœud final du nœud donné <e> pred = suc.prev; // Créer un nouveau nœud, la référence du nœud précédente du nouveau nœud pointe vers le nœud précédent du nœud donné // La référence du nœud suivant du nouveau nœud pointe vers le nœud final du nœud donné <E> newNode = nouveau nœud <> (Pred, E, SCCH); // pointer la référence du nœud précédent du nœud donné au nouveau nœud suc.prev = newNode; // Si le nœud précédent du nœud donné est vide, cela signifie que le nœud donné est le nœud d'en-tête if (pred == null) {// pointer la référence du nœud d'en-tête au nouveau nœud d'abord = newNode; } else {// Sinon, pointez la référence du nœud suivant au nouveau nœud pred.next = newNode; } // Ajouter le nombre d'éléments définis une taille ++; // Ajouter le nombre de modifications un modCount ++; } // Déchargez le nœud spécifié E Unlink (nœud <e> x) {// Obtenez l'élément du nœud Final E élément = x.item; // Obtenez la référence au nœud suivant du nœud final du nœud donné <e> next = x.next; // Obtenez la référence au nœud précédent du nœud final du nœud donné <e> prev = x.prev; // Si le nœud précédent du nœud donné est vide, explication: le nœud donné est un nœud d'en-tête if (prev == null) {// pointer la référence du nœud d'en-tête au nœud suivant du nœud donné d'abord = suivant; } else {// référence le nœud successeur du nœud précédent pointant vers le nœud suivant du nœud donné prev.Next = next; // Référence le nœud précédent du nœud donné x.prev = null; } // Si le nœud suivant du nœud donné est vide, cela signifie que le nœud donné est un nœud de queue if (next == null) {// pointer la référence du nœud de queue au nœud précédent du nœud donné last = prev; } else {// référence le nœud avant du nœud suivant pointant vers le nœud précédent du nœud donné next.prev = prev; x.next = null; } // vide l'élément du nœud donné x.item = null; // soustrayez le nombre d'éléments définis par taille--; // ajouter modCount ++; élément de retour;} LinkBefore et Unlink sont des opérations représentatives des nœuds de liaison et des nœuds désinstallés. D'autres méthodes de liaison et de désinstallation des nœuds aux deux extrémités sont similaires, nous nous concentrons donc sur les méthodes LinkBefore et non.
Diagramme de processus de la méthode LinkBefore:
Diagramme de processus de la méthode de non-link:
Grâce à l'illustration ci-dessus, la complexité temporelle des opérations d'insertion et de suppression de la liste liée est O (1), et les opérations de recherche et de modification de la liste liée nécessitent la traversée de la liste liée pour localiser les éléments. Les deux opérations sont appelées méthode Node (INT INDEX) pour localiser les éléments pour voir comment il localise les éléments via des indices.
// Obtenez le nœud nœud <e> nœud (int index) {// Si l'index est dans la première moitié de la liste liée, vérifiez depuis le début if (index <(size> 1)) {node <e> x = premier; pour (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// Si l'index est dans la seconde moitié de la liste liée, vérifiez à partir du nœud final <e> x = dernier; pour (int i = size - 1; i> index; i--) {x = x.prev; } return x; }} Lorsque vous positionnez l'indice, déterminez d'abord s'il se trouve dans la moitié supérieure ou la moitié inférieure de la liste liée. Si c'est dans la moitié supérieure, commencez depuis le début, et s'il s'agit de la moitié inférieure, commencez à partir de la fin. Par conséquent, la complexité temporelle du fonctionnement de la recherche et de la modification de l'indice est O (n / 2). Grâce au fonctionnement de la liste liée bidirectionnelle, les fonctions des files d'attente à un seul élément, des files d'attente bidirectionnelles et des piles peuvent également être réalisées.
Fonctionnement de la file d'attente à sens unique:
// Obtenez le nœud d'en-tête public e peek () {nœud final <e> f = premier; retour (f == null)? null: f.item;} // Obtenez le nœud d'en-tête public e élément () {return getFirst ();} // apparaît le nœud d'en-tête publique E Poll () {nœud final <e> f = premier; retour (f == null)? NULL: UnlinkFirst (f);} // Supprimez le nœud d'en-tête publique E Remove () {return demoveFirst ();} // ajouter le nœud à la fin de la file d'attente Boolean Offre (e e) {return add (e);}Fonctionnement de la file d'attente bidirectionnelle:
// Ajouter une offre booléenne publiqueFirst (e e) {addFirst (e); return true;} // Ajouter un Boolean Offre (E E) {e e) {addLast (e); return true;} // Obtenez le nœud d'en-tête public e peekFirst () {nœud final <e> f = premier; retour (f == null)? NULL: F.Item; } // Obtenez le nœud de queue publique e peeklast () {Node final <e> l = dernier; return (l == null)? null: l.item;}Fonctionnement de la pile:
// Mettez la pile publique void push (e e) {addFirst (e);} // met la pile publique e pop () {return doamFirst ();} Qu'il s'agisse d'une file d'attente à sens unique, d'une file d'attente bidirectionnelle ou d'une pile, ils fonctionnent en fait sur les nœuds de tête et de queue de la liste liée. Leurs implémentations sont basées sur les quatre méthodes: addFirst (), addLast (), re SupportFirst () et Removelast (). Leurs opérations sont similaires à LinkBefore () et Unlink (), sauf que l'une doit fonctionner aux deux extrémités de la liste liée, et l'autre doit fonctionner au milieu de la liste liée. On peut dire que ces quatre méthodes sont des cas particuliers de méthodes LinkBeFore () et Unlink (), il n'est donc pas difficile de comprendre leurs implémentations internes, donc je ne les présenterai pas ici. À ce stade, notre analyse de LinkedList est sur le point de se terminer, et nous résumerons les points clés de tout le texte:
1. LinkedList est implémenté en fonction d'une liste liée à double sens. Qu'il s'agisse de la méthode d'addition, de suppression, de modification et de recherche ou de l'implémentation des files d'attente et des piles, il peut être implémenté via des nœuds de fonctionnement.
2. LinkedList n'a pas besoin de spécifier la capacité à l'avance, car sur la base des opérations de liste liée, la capacité de la collection augmentera automatiquement avec l'ajout d'éléments.
3. La mémoire occupée par la collection après la suppression de LinkedList est automatiquement réduite, et il n'est pas nécessaire d'appeler la méthode trimtoSize () comme ArrayList
4. Toutes les méthodes de lisme lié ne sont pas synchronisées, il n'est donc pas en file d'attente et doit être évité dans des environnements multi-thread.
5. L'analyse ci-dessus est basée sur JDK1.7, et d'autres versions auront quelques différences, il ne peut donc pas être généralisé.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.