java - 在 Java 的双向链表中将对象添加到另一个对象之前

Question

我用 Java 编写了一个双向链表的简单实现，其中包含 Person 对象。

class Node {
    Node next, previous;
    Object data;

    Node() {
        next = null;
        previous = null;
        data = null;
    }
}

我还有一个 Person 类，代码如下:

class Person {
    String name;

    Person(String name) {
        this.name = name;
    }
    //Other methods
}

然后我有一个 PersonList 类，我在其中定义插入和搜索 Person 对象的方法:

class PersonList {
    Node first, last, previous;

    public void insert(Object myObject) {
        Node n = new Node();
        n.data = myObject;

        //If list is empty
        if(first == null) {
            first = n;
            last = n;
        }
        else {
            n.previous = last;  
            last.next = n;    
            last = n;
        }
    }
}

所以这是我的问题:我正在尝试编写一个带有两个参数的方法:(i)一个新的 Person 对象和(ii)一个保存名称的字符串变量。方法是将新对象插入到名字匹配的人之前(所有名字都是唯一的)。

public void insertBefore(Object myObject, String name)

我已经通过编写该方法来测试该方法，以便在该方法实现后，它可以正确找到新 Person 之前和之后的对象。现在，我的问题是更改节点，以便它们指向正确的对象。

我有以下逻辑:如果列表中没有人，则执行简单 insert() 方法的第一部分。否则，循环遍历人员，搜索名称与给定名称匹配的人员。如果找到了该人，则将其当前的前一个节点指针更改为指向newPerson，newPerson的next指针必须指向当前人，最后，当前人必须是新人。

public void insertBefore(Object myObject, String beforeThisName) {
        Node n = new Node();
        Node current = first;
        n.data = myObject;

        //If no people in list (I already have code for this one)

        //Else, if the list contains people
        else {

            //Iterate through list
            while(current != null) {
                Person currentPerson = (Person) current.data;
                String currentName = currentPerson.getName();

                //If the Person is found
                if(currentName.equalsIgnoreCase(beforeThisName)) {
                    //This is simply a check to see whether loop finds the right position
                    System.out.println(current.previous.data.toString());   //After this person
                    System.out.println(current.data.toString());    //Before this person

                    /* Here is where the inserting before happens. */
                    current.previous = n;   //The current person's previous person is the new person
                    n.next = current;   //new person's next pointer is the current person 
                    current = n;  //current person is the new person
                    return;
                }
                current = current.next;
            }
        }
    } 

对此的任何帮助都将受到高度赞赏。我正在尝试自学列表，这个问题已经让我陷入困境一段时间了。谢谢!

Answer 1

将新 Person 的下一个设置为 currentPerson，将 currentPerson 的上一个设置为新 Person 是不够的。您还必须将新 Person 的前一个设置为 currentPerson 的原始前一个，并将原始前一个的下一个设置为新 Person。

                n.previous = current.previous;
                n.previous.next = n;
                current.previous = n;   //The current person's previous person is the new person
                n.next = current;   //new person's next pointer is the current person 
                current = n;  //current person is the new person

当然，您必须验证这些节点都不为空(因为您要添加的新人员可能是列表中的第一个节点)。

因此，如果这是列表的原始状态，并且您希望在“Prev”和“current”之间添加一个新节点:

       --------  next ----> -----------
       - Prev -             - current -
       --------  <---- prev ----------- 

你必须设置新节点n的两个指针并更新两个指针(当前.上一个和上一个.下一个):

       --------  next ----> ----------- next ----> -----------
       - Prev -             -    n    -            - current -
       --------  <---- prev ----------- <---- prev -----------