La création d'une classe LinkedList à partir de zéro

Si vous êtes réellement à la construction d'un système réel, alors oui, vous devez généralement utiliser juste les trucs de la bibliothèque standard, si ce que vous avez besoin est disponible. Cela dit, ne pas penser à cela comme inutile. Il est bon de comprendre comment les choses fonctionnent, et la compréhension des listes liées est une étape importante vers la compréhension plus complexe des structures de données, dont beaucoup n'existent pas dans les bibliothèques standard.

Il y a quelques différences entre la façon dont vous êtes en train de créer une liste, et la manière dont les collections Java API t-il. Les Collections de l'API est en train d'essayer d'adhérer à une plus compliqué de l'interface. Les Collections de l'API liste chaînée est aussi une liste doublement chaînée, alors que vous êtes en train de construire une seule liste liée. Ce que vous faites est plus approprié pour un devoir en classe.

Avec votre LinkedList classe, une instance sera toujours une liste d'au moins un élément. Avec ce type d'installation que vous souhaitez utiliser null pour quand vous avez besoin d'une liste vide.

Pense next comme étant "le reste de la liste". En fait, beaucoup de semblables utiliser le nom de "queue" au lieu de "suivant".

Voici un schéma d'un LinkedList contenant 3 éléments:

Noter que c'est un LinkedList objet de pointage à un mot ("Bonjour") et une liste de 2 éléments. La liste de 2 éléments a un mot ("Stack") et une liste de 1 élément. Cette liste de 1 élément a d'un mot ("Overflow") et une liste vide (null). Vous pouvez donc traiter next comme une autre liste qui se trouve être l'un des éléments les plus courtes.

Vous voudrez peut-être ajouter un autre constructeur qui prend juste une Chaîne de caractères, et de jeux à côté de null. Ce serait pour la création d'un 1-élément de la liste.

À ajouter, vous vérifiez si next est null. Si il est, créer une nouvelle liste d'éléments et de définir next pour que.

next = new LinkedList(word);

Si le prochain n'est pas null, puis ajouter à next à la place.

next.append(word);

C'est l'approche récursive, qui est le montant minimum de code. Vous pouvez le transformer en un processus itératif de la solution qui serait la plus efficace en Java^*, et ne serait pas le risque d'un débordement de la pile avec de très longues listes, mais je devine que le niveau de complexité n'est pas nécessaire pour la durée de votre affectation.

---

^{* Certaines langues ont la queue appel à l'élimination, qui est une optimisation qui permet à la langue de mise en œuvre de convertir en "queue d'appels" (un appel à une autre fonction comme la dernière étape avant le retour) en (efficacement) un "goto". Cela rend le code d'éviter complètement à l'aide de la pile, ce qui le rend plus sûr (vous ne pouvez pas le débordement de la pile si vous n'utilisez pas la pile) et généralement plus efficace. Le schéma est probablement le plus bien connu l'exemple d'une langue à l'aide de cette fonctionnalité.}

Comment sur un entièrement fonctionnel de la mise en œuvre d'un non-récursive Liste chaînée?

J'ai créé pour mon Algorithmes j'ai la classe comme un tremplin pour mieux comprendre avant de passer à l'écriture d'un doublement lié classe de file d'attente pour une mission.

Voici le code:

import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedList<T> implements Iterable<T> {
private Node first;
private Node last;
private int N;
public LinkedList() {
first = null;
last = null;
N = 0;
}
public void add(T item) {
if (item == null) { throw new NullPointerException("The first argument for addLast() is null."); }
if (!isEmpty()) {
Node prev = last;
last = new Node(item, null);
prev.next = last;
}
else {
last = new Node(item, null);
first = last;
}
N++;
}
public boolean remove(T item) {
if (isEmpty()) { throw new IllegalStateException("Cannot remove() from and empty list."); }
boolean result = false;
Node prev = first;
Node curr = first;
while (curr.next != null || curr == last) {
if (curr.data.equals(item)) {
//remove the last remaining element
if (N == 1) { first = null; last = null; }
//remove first element
else if (curr.equals(first)) { first = first.next; }
//remove last element
else if (curr.equals(last)) { last = prev; last.next = null; }
//remove element
else { prev.next = curr.next; }
N--;
result = true;
break;
}
prev = curr;
curr = prev.next;
}
return result;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
public Iterator<T> iterator() { return new LinkedListIterator(); }
private class LinkedListIterator implements Iterator<T> {
private Node current = first;
public T next() {
if (!hasNext()) { throw new NoSuchElementException(); }
T item = current.data;
current = current.next;
return item;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
}
@Override public String toString() {
StringBuilder s = new StringBuilder();
for (T item : this)
s.append(item + " ");
return s.toString();
}
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
while(!StdIn.isEmpty()) {
String input = StdIn.readString();
if (input.equals("print")) { StdOut.println(list.toString()); continue; }
if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
break;
}
}
}

Note: C'est une jolie base de la mise en œuvre d'un seul-liste liée. Le " T " de type est un type générique de l'espace réservé. En fait, cette liste devrait fonctionner avec n'importe quel type qui hérite de l'Objet. Si vous l'utilisez pour les types primitifs assurez-vous d'utiliser la classe nullable équivalents (ex 'Integer' pour l'int type). La "dernière" de la variable n'est pas vraiment nécessaire, sauf qu'il raccourcit les insertions de O(1) fois. Les absorptions sont très lents, car ils s'exécuter en O(N) le temps, mais il permet de supprimer la première occurrence d'une valeur dans la liste.

Si vous le souhaitez, vous pouvez aussi consulter dans la mise en œuvre:

• addFirst() - ajoute un nouvel élément au début de la LinkedList
• removeFirst() - supprimer le premier élément de la LinkedList
• removeLast() - supprimer le dernier élément de la LinkedList
• addAll() - ajout d'une liste ou un tableau d'éléments à la LinkedList
• removeAll() - supprimer une liste ou un tableau d'éléments de la LinkedList
• contient() - vérifier pour voir si la LinkedList contient un élément
• contient() - effacer tous les éléments de la LinkedList

Honnêtement, il ne prend que quelques lignes de code pour faire une liste à double liaison. La principale différence entre cela et une double liaison-liste, c'est que le Nœud cas d'une liste à double liaison besoin d'un surplus de référence qui pointe vers l'élément précédent dans la liste.

L'avantage de cette de plus un appel récursif à la mise en œuvre est que c'est plus rapide et vous n'avez pas à vous inquiéter au sujet de l'inondation de la pile lorsque vous traverser de grandes listes.

Il y a 3 commandes pour tester cela dans le débogueur/console:

• Préfixant une valeur par un " + " ajouter à la liste.
• Préfixant par un '-' va supprimer la première occurrence de la liste.
• Tapant "imprimer" permet d'imprimer la liste de valeurs séparées par des espaces.

Si vous n'avez jamais vu de l'intérieur comment l'une de ces œuvres, je vous suggère de parcourir les différentes dans le débogueur:

• ajouter() - punaises d'un nouveau nœud à l'extrémité ou initialise la première/dernière valeur si la liste est vide
• remove() - parcourt la liste à partir du début à la fin. S'il trouve une correspondance, il supprime cet élément et relie les liens rompus entre le précédent et le suivant maillons de la chaîne. Des exceptions sont ajoutés lorsqu'il n'existe aucun lien suivant ou précédent.
• toString() - utilise le foreach itérateur pour simplement marcher sur la liste de la chaîne du début à la fin.

Alors qu'il y a de mieux et de plus efficace approches pour les listes de type array-listes, la compréhension de la façon dont l'application traverse via références/pointeurs est essentielle pour comprendre comment beaucoup plus de données au niveau des structures de travail.

Sûr, une Liste chaînée est un peu déroutant pour la programmation des n00bs, beaucoup, la tentation est de le regarder comme des Poupées russes, parce que c'est ce qu'il semble, une LinkedList Objet dans une LinkedList Objet. Mais c'est une touche difficile à visualiser, au lieu de le regarder comme un ordinateur.

LinkedList = Données + Membres Suivant

Où il est le dernier membre de la liste si la prochaine est NULL

Donc 5 membres LinkedList serait:

LinkedList(Data1, LinkedList(Data2, LinkedList(Data3, LinkedList(Données4, LinkedList(Data5, NULL)))))

Mais vous pouvez la considérer comme simplement:

Data1 -> Données2 -> Data3 -> Data4 -> Data5 -> NULL

Alors, comment pouvons-nous trouver la fin de cette? Eh bien, nous savons que la valeur NULL est la fin donc:

public void append(LinkedList myNextNode) {
LinkedList current = this; //Make a variable to store a pointer to this LinkedList
while (current.next != NULL) { //While we're not at the last node of the LinkedList
current = current.next; //Go further down the rabbit hole.
}
current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List!
return; //and we're done!
}

C'est très simple code de cours, et il sera infiniment boucle si vous lui donnez une liste chaînée circulaire! Mais c'est l'essentiel.

Comment ai-je créé une linkedlist comme ça. Comment cela fonctionne?
Tout ceci est une liste chaînée est. Un article avec un lien vers l'élément suivant de la liste. Tant que vous gardez une référence à l'élément au début de la liste, vous pouvez parcourir l'ensemble de la chose à l'aide de chaque référence ultérieure à la valeur suivante.

À ajouter, tout ce que vous devez faire est de trouver la fin de la liste, et faire le prochain élément de la valeur ajoutée, donc, si cette non nulle suivant, vous devez appeler ajouter sur l'élément suivant jusqu'à ce que vous trouver la fin de la liste.

this.next.Append(word);

Moyens trouver ci-dessous le Programme de

class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListManual {
Node node;
public void pushElement(int next_node) {
Node nd = new Node(next_node);
nd.next = node;
node = nd;
}
public int getSize() {
Node temp = node;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public void getElement() {
Node temp = node;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public static void main(String[] args) {
LinkedListManual obj = new LinkedListManual();
obj.pushElement(1);
obj.pushElement(2);
obj.pushElement(3);
obj.getElement(); //get element
System.out.println(obj.getSize());  //get size of link list
}
}