Java 链表 - 添加（add）方法

Question

数据结构课程，实现带有头、尾和当前节点的单向链表。在一个方法上遇到了麻烦，需要指导朝正确的方向努力。

根据任务要求编写方法：

add( item ) ：在当前节点后添加项目（字符串），并将当前指针设置为指向新节点。

我的尝试：

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

我的add方法似乎只在向列表中间添加项目时有效，而不是在任何一端添加。如果我使用它添加几个项目然后打印列表，只有我添加的第一个项目会显示在列表中，而我的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;
    }
}

- dysania

---

其他代码呢？ - fge

你如何测试输出？find方法只查找当前节点，不从头开始。因此可能无法获取所有节点... 另外：你的empty()方法可以简单地写成return head==null; - Chnoch

@Andy，你可以在Java中为多个变量赋值。这意味着head和tail指向同一个对象。 - Chnoch

是的，我的一些方法还没有完成，我还没有处理完它们所有；感谢您提醒我关于 empty() 方法的事情。 - dysania

@Daniel - 在下面，@Chnoch和我几乎同时指出了add中的错误。 - Wayne

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

这是因为append依赖的tail继续指向第二个add操作执行后的第一个Node。

- Wayne

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;

}

- vextorspace

---

这是我第一次使用提供的驱动程序文件来测试我的代码，所以问题可能出在那里。不过还是谢谢你的关注。 - dysania

感谢帮助，但是我已经停止删除操作，因为我意识到添加操作没有进行适当的测试，而且我还没有完成查找方法的测试。 - dysania

add中肯定有错误，请看我的答案（或@Chnoch的）。 - Wayne

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()方法一旦到达尾部就停止，因此“第二个添加”以及“第五个添加”和“第六个添加”都丢失了。如果在末尾添加新节点，则需要始终更新尾部。

希望这有所帮助。 祝好，Chnoch

- Chnoch

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;

- Bhesh Gurung

---

我认为这会使节点指向自身而不是下一个节点。 - vextorspace

不，那将会断开列表，当前的 curr 将不会指向插入的节点。 - Daniel Fischer

如果你这样做，你会失去元素之间的链接...因为节点都只会指向自己。我认为他的代码很好：首先将当前变量的下一个值分配给新节点，然后让新节点成为当前节点。对我来说很有道理。 - Chnoch

我也是这么想的，但是我已经盯着这个问题看了很久，开始怀疑和反复思考我所写的一切。 - dysania