Java Linked List - добавить метод

Question

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

Из задания напишите метод:

add (item): добавляет элемент (String) после текущего узла в списке и устанавливает текущий указатель для ссылки на новый узел.

Моя попытка:

public void add(String item)
{
    if(curr != null)
    {
        Node newNode = new Node(item, curr.next);
        curr.next = newNode;
        curr = newNode;
    }
    else
    {
        head = tail = new Node(item, null);
        curr = head;
    }
}

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

Есть ли явные проблемы с моим кодом? Я чувствую, что упускаю что-то очевидное.

Все:

public class LinkedList {
    Node head = null; /* Head of the list */
    Node tail = null; /* Tail of the list */
    Node curr = null; /* Current node in the list */

    public void prepend(String item) {
        if (head == null) {
            head = tail = new Node(item, null);
            curr = head;
        } else {
            head = new Node(item, head);
            curr = head;
        }
    }

    public void append(String item) {
        if (head == null) {
            head = tail = new Node(item, null);
            curr = tail;
        } else {
            tail.next = new Node(item, null);
            tail = tail.next;
            curr = tail;
        }
    }

    public void add(String item) {
        if (curr != null) {
            Node newNode = new Node(item, curr.next);
            curr.next = newNode;
            curr = newNode;
        } else {
            head = tail = new Node(item, null);
            curr = head;
        }
    }

    public void delete() {
        if (curr.next == null) {
            Node temp = head;
            while (temp.next != curr) {
                System.out.println(temp.item);
                temp = temp.next;
            }
            temp.next = null;
            curr = head;
        }
    }

    public void find(String item) {
        Node temp = new Node(curr.item, curr.next);
        if (item.equals(temp.item))
            curr = temp;
        else {
            temp = temp.next;
            while (temp.next != null && temp != curr) {
                if (item.equals(temp.item))
                    curr = temp;
            }
        }
    }

    public String get() {
        if (curr != null)
            return curr.item;
        else
            return "";
    }

    public boolean next() {
        if (curr != tail) {
            curr = curr.next;
            return true;
        } else
            return false;
    }

    public void start() {
        curr = head;
    }

    public void end() {
        curr = tail;
    }

    public boolean empty() {
        if (head == null)
            return true;
        else
            return false;
    }
}

Node класс:

class Node {
    Node next;
    String item;

    Node(String item, Node next) {
        this.next = next;
        this.item = item;
    }
}

Answer 1

В add действительно есть проблема: он не обновляет tail, когда узлы уже существуют.Рассмотрим следующую последовательность действий:

LinkedList list = new LinkedList(); 
list.add("one");
list.add("two");
list.append("three");

Если бы вы затем распечатали ее, используя это:

public void print() {
    Node curr = this.head;
    while(curr != null) {
        System.out.println(curr.item);
        curr = curr.next;
    }
}

Примерно так:

list.print();

Вы получитеследующий вывод:

one
three

Это происходит потому, что tail - на который опирается append - продолжает указывать на первый Node после выполнения второй операции add.

Answer 2

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

Хорошо, единственная проблема, которую я вижу, это удаление:

public void delete()
{
    Node temp = head;

    while(temp != null && temp.next != curr) {
         System.out.println(temp.item);
         temp=temp.next;

    }

    if (temp != null && temp.next != null) {
        temp.next = temp.next.next;
    }
    curr = head;

}

Answer 3

Я думаю, что нашел вашу проблему.Если вы используете append (), вы добавляете его сразу после хвоста.Но когда вы добавили предыдущие узлы после хвоста, вы не устанавливаете свой хвост в новый узел.Это означает, что после двойного вызова append () вы теряете все узлы, добавленные после первого append ().

Краткий пример:

public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.add("First add");
    list.append("First Append");
    list.add("Second add");
    list.prepend("First prepend");
    list.add("Third add");
    list.prepend("Second prepend");
    list.add("fourth add");
    list.append("Second Append");
    list.add("Fifth add");
    list.add("Sixth add");

    list.start();
    do {
        System.out.println(list.get().toString());

    } while (list.next());
}

Вывод:

Second prepend
fourth add
First prepend
Third add
First add
First Append
Second Append

Вывод: «Второе добавление» потеряно, равно как и «Пятое добавление» и «Шестое добавление», потому что ваш метод next () останавливается, как только достигает хвоста.Вам нужно всегда обновлять хвост, если вы добавляете новый узел в конце.

Надеюсь, это поможет.Ура, чноча

Answer 4

Я думаю, проблема в

if (curr != null) {
    Node newNode = new Node(item, curr.next); //<-- here (curr.next)

//and

Node(String item, Node next) {
    this.next = next; //<-- here

Попробуйте ( Отредактировано ):

Node newNode = new Node(item, curr); // pass curr to the constructor of Node
curr = newNode;