Add Object Before Another in a Doubly Linked List in Java

Question

I have written a simple implementation of a doubly linked list in Java, holding Person-objects.

class Node {
 Node next, previous;
 Object data;
 Node() {
 next = null;
 previous = null;
 data = null;
 }
}

I also have a Person-class with the code:

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

I then have a PersonList-class where I define methods for inserting and searching for 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;
 }
 }
}

So here is my QUESTION: I am trying to write a method that takes two parameters: (i) A new Person-object and (ii) a String variable holding a name. The method is to insert the new object BEFORE the person whose name matches (all names are unique).

public void insertBefore(Object myObject, String name)

I have tested the method by writing it such that it correctly finds the objects that are to be before and after the new Person, after the method has been implemented. Now, my problem is changing the nodes so that they point to the right objects.

I have the following logic: If no people are in the list, do as with the first part of the simple insert()-method. Otherwise, loop through the people searching for the Person whose name matches the given name. If that person is found, change its current previous Node pointer to point to the newPerson, the newPerson's next pointer must point to the current person, and lastly, the current person must be the new person.

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

Any help with this is highly appreciated. I'm trying to teach myself lists, and this problem has had me stuck for some time. Thanks!

• msrd0: If you say current = n, this only changed in your method, not in the nodes. You dont have pointers there. Try current.data = n.data and so on

Answer 1

It's not enough to set the next of the new Person to currentPerson and the previous of currentPerson to the new Person. You also have to set the previous of the new Person to the original previous of currentPerson, and the next of that original previous to the new 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

Of course you have to validate that none of these Nodes is null (since the new Person you are adding might be the first Node in the list).

So if this is the original state of the list, and you wish to add a new node between "Prev" and "current" :

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

You have to set the two pointers of the new node n and update two pointers (currrent.previous and Prev.next) :

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

Answer 2

In a doubly-linked list you also have a next pointer so what you have to do is:

• save current.previous e.g. to oldPrevious
• set current.previous to newNode and newNode.next to current
• set oldPrevious.next to newNode and newNode.previous to oldPrevious

• Thomas: @northener you're welcome :) As a hint: if you're dealing with pointers/references - especially when implementing collections - it often helps to draw some small usecases on paper since it's easier to keep a genera overview.
• yulai: Absolutely @Thomas ! Did a lot of the logic on paper first, but missed the current.previous as having to become the old previous and then setting it to the new's previous. Cheers!