在Java的双重链表中，在另一个对象之前添加对象

Question

我用Java编写了一个简单的双链表实现，包含Person-objects。

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-objects的方法:

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-object和(ii)一个包含名字的字符串变量。方法是将新对象插入到名字匹配的人之前(所有名字都是唯一的)。

public void insertBefore(Object myObject, String name)

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

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

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的previous设置为currentPerson的原始previous，以及新Person的原始previous的next。

                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

当然，您必须验证这些节点中没有一个是空的(因为您添加的新Person可能是列表中的第一个节点)。

如果这是列表的原始状态，并且你希望在"Prev"one_answers"current"之间添加一个新节点:

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

您必须设置新节点n的两个指针并更新两个指针(currrent。previous and previous .next):

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

Answer 2

在双链表中你也有一个next指针所以你要做的是:

保存current.previous例如到oldPrevious
• 设置current.previous为newNode, newNode.next为current
• 设置oldPrevious.next为newNode, newNode.previous为oldPrevious