0

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!

1
  • 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 Commented Aug 4, 2014 at 12:45

2 Answers 2

3

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 -----------
Sign up to request clarification or add additional context in comments.

Comments

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

2 Comments

@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.
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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.