Insertion into Doubly linked list

Question

I have a problem with addition of elements in Liked List

public class LinkedList {
    public Node first;
    public Node last;

    public LinkedList() {
        first = null;
        last = null;
    }

    public void addFirst(Student student) {
        Node f = first;
        Node newNode = new Node(student);
        first = newNode;
        if (f == null) last = newNode;
        else f.previous = newNode;
    }

    public void addLast(Student student) {
        Node l = last;
        Node newNode = new Node(student);
        last = newNode;
        if (l == null) first = newNode;
        else {
            l.next = newNode;
        }
    }


    public void display() {
        Node current = first;
        while (current != null) {
            //print...
            current = current.next;
        }
    }

My problem is when I run:

list.addLast(1);
list.addFirst(2);
list.display();

It displays just "2" 'display' method just can't see last added element.
But if I run:

list.addFirst(2);
list.addLast(1);

It will display both. What is wrong with it? Thanks.

matt b · Accepted Answer · 2011-10-25 13:50:48Z

4

If this list is doubly-linked, shouldn't you be adding a reference in newNode to the elements that come before/after it?

Your display() method traverses node.next but in addFirst() you never set .next - so if you call addFirst() several times, and only that method, what will display() print?

answered Oct 25, 2011 at 13:50

matt b

140k66 gold badges287 silver badges352 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Nikita Over a year ago

I get it, it will print just last added element.

Steven · Accepted Answer · 2011-10-25 13:53:41Z

2

in addFirst you also have to put newNode.next = f, right now you're just updating one side of the bidirectional relationship. And since the display uses the next field, it doesn't work as you expect it.

Similarly, in addLast you need to add newNode.previous = l, however since the previous field isn't used in the display method, it doesn't appear bugged when you execute it.

answered Oct 25, 2011 at 13:53

Steven

2,4775 gold badges32 silver badges41 bronze badges

Comments

Salvatore Previti · Accepted Answer · 2011-10-25 13:53:17Z

0

public void addFirst(Student student) {
    Node f = first;
    Node newNode = new Node(student);
    newNode.next = f; // this was missing
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.previous = newNode;
}

public void addLast(Student student) {
    Node l = last;
    Node newNode = new Node(student);
    newNode.previous = l; // this was missing
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
}

answered Oct 25, 2011 at 13:53

Salvatore Previti

9,11033 silver badges38 bronze badges

Collectives™ on Stack Overflow

Insertion into Doubly linked list

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related