Ajout d'éléments à la fin de la liste chaînée

J'étudie pour un examen, et c'est un problème à partir d'un vieux test:

Nous avons une seule liste, avec une liste tête avec la déclaration suivante:

class Node {
    Object data;
    Node next;
    Node(Object d,Node n) {
        data = d;
        next = n;
    }
}

Écrire une méthode void addLast(Node header, Object x) qui ajoute x à la fin de la liste.

Je sais que si j'avais quelque chose comme:

LinkedList someList = new LinkedList();

Je pourrais juste ajouter des éléments à la fin en faisant:

list.addLast(x);

Mais comment puis-je faire ici?

Pourquoi avez-vous besoin de passer par le Nœud d'en-tête pour ajouter quelque chose à la fin de la liste?
écrivez votre propre mise en œuvre pour addLast(Node header, Object x) that adds x at the end of the list google pour ajouter l'élément à la fin de individuellement linkedlist en java
probablement demander à son professeur.
c'est la question exacte, idk.
Essayez juste de l'ajout de la méthode à la classe de Nœud comme une méthode statique, et la boucle à la fin de l'en-tête du Nœud, puis l'ajout d'un nouveau nœud à la fin de la liste.

OriginalL'auteur John | 2011-03-08

java linked-list

11
```
class Node {
    Object data;
    Node next;
    Node(Object d,Node n) {
        data = d ;
        next = n ;
       }

   public static Node addLast(Node header, Object x) {
       //save the reference to the header so we can return it.
       Node ret = header;

       //check base case, header is null.
       if (header == null) {
           return new Node(x, null);
       }

       //loop until we find the end of the list
       while ((header.next != null)) {
           header = header.next;
       }

       //set the new node to the Object x, next will be null.
       header.next = new Node(x, null);
       return ret;
   }
}
```
Oui, il y a toujours un moyen de la boucle récursive. Utiliser l'en-tête == null comme le cas de base (où vous vous arrêterez) et d'appeler addLast avec en-tête.prochaine.
Je voudrais donc faire la si statemtn juste de retour, Et le dernier en-tête.ensuite d'en-tête.next=addLast(en-tête,null)?
Sorte de, vous avez besoin pour passer de x à travers la boucle récursive: addLast(en-tête, x) et puis si l'en-tête == null, créer le nouveau nœud, ajouter X à elle, et de renvoyer le nouveau nœud. Si ce n'est dans le cas de base, vous devez retourner le résultat de addLast
Votre code s'exécute en O(n) fois, mais cette opération doit être O(1). Si vous gardez une trace de la queue nœud, vous n'avez pas besoin d'une boucle sur chaque élément de la liste. Tout ce que vous faire est de mettre à jour la queue pour pointer vers le nouveau nœud.
Le problème énoncé indique que nous devons prendre comme entrée le nœud de tête tout en ajoutant à la fin de la liste.

OriginalL'auteur therin
8

Vous voulez naviguer à travers l'ensemble de la liste liée à l'aide d'une boucle et de la vérification de la "prochaine" de la valeur de chaque nœud. Le dernier nœud sera celui dont la valeur est null. Simplement faire de ce nœud suivant la valeur d'un nouveau nœud que vous créez avec les données d'entrée.
```
node temp = first; //starts with the first node.

    while (temp.next != null)
    {
       temp = temp.next;
    }

temp.next = new Node(header, x);
```
C'est l'idée de base. C'est bien sûr, le pseudo-code, mais il devrait être assez simple à mettre en œuvre.

La partie la plus importante est le cas de base, où la première est nulle. Doivent être traitées en conséquence (c'est à dire ne pas lancer une exception NullPointerException)

OriginalL'auteur Benjamin S

Ici est une solution partielle à votre liste liée de classe, j'ai laissé le reste de la mise en œuvre afin de vous et aussi de gauche la bonne idée d'ajouter une queue noeud dans le cadre de la liste liée à vous.

Le nœud du fichier :

public class Node 
{
    private Object data; 
    private Node next; 

    public Node(Object d) 
    { 
        data = d ;
        next = null;
    }

    public Object GetItem()
    {
        return data;
    }

    public Node GetNext()
    {
        return next;
    }

    public void SetNext(Node toAppend)
    {
        next = toAppend;
    }
}

Et voici une Liste Liée fichier :

public class LL
{
    private Node head;

    public LL()
    {
        head = null;
    }

    public void AddToEnd(String x)
    {
        Node current = head;

        //as you mentioned, this is the base case
        if(current == null) {
            head = new Node(x);
            head.SetNext(null);
        }

        //you should understand this part thoroughly :
        //this is the code that traverses the list.
        //the germane thing to see is that when the 
        //link to the next node is null, we are at the 
        //end of the list.
        else {
            while(current.GetNext() != null)
                current = current.GetNext();

            //add new node at the end
        Node toAppend = new Node(x);
            current.SetNext(toAppend);
        }
    }
}

OriginalL'auteur Literati Insolitus

0

boucle le dernier élément de la liste chaînée qui ont à côté du pointeur à null alors modifier la prochaine pointeur sur un nœud qui a le data=objet et à côté du pointeur = null

OriginalL'auteur Ahmed Elmorsy
0

Voici un indice, vous avez un graphe de nœuds dans la liste liée, et que vous gardez toujours une référence à la tête, qui est le premier nœud dans la linkedList.

suivant pointe vers le nœud suivant dans la linkedlist, donc lors de la prochaine est nul vous êtes à la fin de la liste.

OriginalL'auteur crowne

La addLast() a besoin de quelques optimisations comme la boucle while à l'intérieur de addLast() a O(n) la complexité. Ci-dessous est ma mise en œuvre de la LinkedList. Exécutez le code avec ll.addLastx(i) une fois et l'exécuter avec ll.addLast(i) encore une fois , vous pouvez voir leur, c'est beaucoup de différence dans le temps de traitement de addLastx() avec addLast().

Node.java

package in.datastructure.java.LinkedList;

/**
* Created by abhishek.panda on 07/07/17.
*/
public final class Node {
    int data;
    Node next;

    Node (int data){
       this.data = data;
    }
    public String toString(){
      return this.data+"--"+ this.next;
    }
}

LinkedList.java

package in.datastructure.java.LinkedList;
import java.util.ArrayList;
import java.util.Date;
public class LinkedList {
Node head;
Node lastx;
/**
* @description To append node at end looping all nodes from head
* @param data
*/
public void addLast(int data){
if(head == null){
head = new Node(data);
return;
}
Node last = head;
while(last.next != null) {
last = last.next;
}
last.next = new Node(data);
}
/**
* @description This keep track on last node and append to it
* @param data
*/
public void addLastx(int data){
if(head == null){
head = new Node(data);
lastx = head;
return;
}
if(lastx.next == null){
lastx.next = new Node(data);
lastx = lastx.next;
}
}
public String toString(){
ArrayList<Integer> arrayList = new ArrayList<Integer>(10);
Node current = head;
while(current.next != null) {
arrayList.add(current.data);
current = current.next;
}
if(current.next == null) {
arrayList.add(current.data);
}
return arrayList.toString();
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
/**
* @description Checking the code optimization of append code
*/
Date startTime = new Date();
for (int i = 0 ; i < 100000 ; i++){
ll.addLastx(i);
}
Date endTime = new Date();
System.out.println("To total processing time : " + (endTime.getTime()-startTime.getTime()));
System.out.println(ll.toString());
}
}

OriginalL'auteur Abhishek Panda

Les programmes ci-dessus peut vous donner une NullPointerException. C'est un moyen facile d'ajouter un élément à la fin de la linkedList.

public class LinkedList {
Node head;
public static class Node{
int data;
Node next;
Node(int item){
data = item;
next = null;
}
}
public static void main(String args[]){
LinkedList ll = new LinkedList();
ll.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
ll.head.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
ll.printList();
System.out.println("Add element 100 to the last");
ll.addLast(100);
ll.printList();
}
public void printList(){
Node t = head;
while(n != null){
System.out.println(t.data);
t = t.next;
}
}
public void addLast(int item){
Node new_item = new Node(item);
if(head == null){
head = new_item;
return;
}
new_item.next = null;
Node last = head;
Node temp = null;
while(last != null){
if(last != null)
temp = last;
last = last.next;
}   
temp.next = new_item;   
return;
}
}

OriginalL'auteur user7420004

0

Si vous gardez une trace de la queue nœud, vous n'avez pas besoin d'une boucle sur chaque élément de la liste.

Tout ce que vous faire est de mettre à jour la queue pour pointer vers le nouveau nœud:
```
AddValueToListEnd(value) {
var node = new Node(value);
if(!this.head) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
```
En anglais:
- Créer un nouveau nœud avec la valeur donnée, et de l'ensemble de la queue = null
- Si la liste est vide, la tête et la queue à la fois pour le nouveau nœud
- Si la liste n'est pas vide, l'ensemble de la vieille queue.ensuite pour le nouveau nœud
- Dans les deux cas, la mise à jour de l'indicateur de queue pour être le nouveau nœud
OriginalL'auteur TomDane

Vous devez vous connecter pour publier un commentaire.