Добавление элементов в конец связанного списка

Question

Я учусь на экзамен, и это проблема старого теста:

У нас есть односвязный список с заголовком списка со следующим объявлением:

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

Напишите метод void addLast(Node header, Object x), который добавляет x в конец списка.

Я знаю, что если бы у меня действительно было что-то вроде:

LinkedList someList = new LinkedList();

Я мог бы просто добавить элементы в конец, выполнив:

list.addLast(x);

Но как я могу сделать это здесь?

Answer 1

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

Answer 2

Вы хотите перемещаться по всему связанному списку, используя цикл и проверяя «следующее» значение для каждого узла.Последний узел будет тем, чье следующее значение равно нулю.Просто сделайте следующее значение этого узла новым узлом, который вы создадите с входными данными.

node temp = first; // starts with the first node.

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

temp.next = new Node(header, x);

Это основная идея.Это, конечно, псевдокод, но он должен быть достаточно простым для реализации.

Answer 3

Вот частичное решение для вашего класса связанного списка, я оставил вам остальную часть реализации, а также оставил хорошее предложение добавить вам хвостовой узел как часть связанного списка.

Файл узла:

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

А вот и файл связанного списка:

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

Answer 4

Если вы отслеживаете хвостовой узел, вам не нужно перебирать каждый элемент в списке.

Все, что вам нужно сделать, это обновить хвост, чтобы он указывал на новый узел:

AddValueToListEnd(value) {
    var node = new Node(value);

    if(!this.head) {
        this.head = node;
    } else {
        this.tail.next = node;
    }

    this.tail = node;
}

На простом английском:

• Создать новый узел с заданным значением и установить tail = null
• Если список пуст, голова и хвост оба указывают на новый узел
• Если список не пустой, задайте для старого tail.next новый узел
• В любом случае обновите указатель хвоста, чтобы он стал новым узлом

Answer 5

addLast () нуждается в некоторой оптимизации, поскольку цикл while внутри addLast () имеет сложность O (n). Ниже моя реализация LinkedList. Запустите код с помощью ll.addLastx (i) один раз и снова запустите его с ll.addLast (i), вы увидите, что во время обработки addLastx () с помощью 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());
    }

}

Answer 6

Вышеуказанные программы могут дать вам исключение NullPointerException. Это более простой способ добавить элемент в конец связанный список.

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

Answer 7

Вот подсказка: у вас есть график узлов в связанном списке, и вы всегда сохраняете ссылку на заголовок, который является первым узлом в списке связанных списков. next указывает на следующий узел в связанном списке, поэтому, когда next равно нулю, вы находитесь в конце списка.

Answer 8

цикл до последнего элемента связанного списка, который имеет следующий указатель на нуль, затем изменяет следующий указатель, чтобы указывать на новый узел, который имеет объект data = и следующий указатель = null