How to insert String data in a sorted doubly linked list?

Question

I have a sorted doubly linked list in which the first and last elements are null. This means when I insert the values a, b, c. The result should look as follows: {null, a, b, c, null}

The empty sorted doubly linked list should look like this: {null, null} in which the first and last elements are always are null.

The problem is that when I insert data in the sorted doubly linked list, the data is not sorted correctly and the 2 null values are always at the end of the list. How can I fix this?

Here is my current insert method:

    public void addElement(String element) {
    // new node which will be inserted in the list
    Node newNode = new Node();
    newNode.data = element;

    // if the list is empty
    if (size == 0) {
        last = newNode;
        newNode.next = first;
        first = newNode;

        size++;

    } else {
        Node current = first;

        // if the element should be at the beginning of the list
        if (current.data.compareTo(element) > 0) {
            newNode.next = current;
            newNode.previous = null;
            current.previous = newNode;

            first = newNode;
        } else {

            while (current != null) {
                if (current.data.compareTo(element) <= 0) {
                    if (current.next == null) {
                        newNode.next = current.next;
                        newNode.previous = current;
                        current.next = newNode;

                        break;
                    }

                    newNode.next = current.next;
                    newNode.previous = current;
                    current.next.previous = newNode;
                    current.next = newNode;

                    break;

                } else {
                    current = current.next;
                }
            }
        }
        size++;
    }
}

Please, provide Node class implementation, first last initialization, and actual output that you are getting. Take a look at this stackoverflow.com/help/mcve — Sergei Sirik
– Sergei Sirik, Commented Nov 13, 2018 at 23:28

Sergei Sirik · Accepted Answer · 2018-11-13 23:24:18Z

It is not so clear what you are doing in your code, so I modified it a bit and made more OO style, so here it is:

class Node {

  String data;
  Node next, previous;
}

public class SortedDLL {

  private Node first;
  private Node last;
  private int size = 0;

  public SortedDLL() {
    size = 0;
    first = new Node();
    last = new Node();
    first.next = last;
    last.previous = first;
  }

  public void addElement(String element) {
    Node newNode = new Node();
    newNode.data = element;

    if (size == 0) {
      first.next = newNode;
      newNode.previous = first;
      newNode.next = last;
      last.previous = newNode;
    } else {
      Node node = first;
      while (node.next.data != null && node.next.data.compareTo(newNode.data) < 0) {
        node = node.next;
      }
      newNode.next = node.next;
      node.next.previous = newNode;
      node.next = newNode;
      newNode.previous = node;
    }

    size++;
  }

  public void print() {
    Node node = first;
    while (node != null) {
      System.out.print(node.data != null ? node.data + " " : "null ");
      node = node.next;
    }
  }

  public void printReverse() {
    Node node = last;
    while (node != null) {
      System.out.print(node.data != null ? node.data + " " : "null ");
      node = node.previous;
    }

  }

  public static void main(String[] args) {
    SortedDLL sortedDLL = new SortedDLL();
    sortedDLL.addElement("c");
    sortedDLL.addElement("a");
    sortedDLL.addElement("b");
    sortedDLL.addElement("c");

    System.out.println("list: ");
    sortedDLL.print();

    System.out.println("\nlist reverse: ");
    sortedDLL.printReverse();
  }

Output:

list: 
null a b c c null 
list reverse: 
null c c b a null

Liad Saubron · Accepted Answer · 2018-11-13 21:11:10Z

0

the problem starts at the first call when size == 0

you push the first null to the end.. and the first node becomes the new node.

then, if you fix this you will get null pointer exception at the row :

if (current.data.compareTo(element) > 0) {

because the current will be null and the will not have data.

you should ignore the first null in the first insert and every insert after that.

answered Nov 13, 2018 at 21:11

Liad Saubron

794 bronze badges

1 Comment

Liad Saubron Over a year ago

you should initialize the first 2 null's as nodes with null data where the first one points to second and the second points to null. then, you should check in the first insert if the node has null value, and set the new node as its successor and the 2nd null as predecessor. do the same for the logic of size !=0

Ghork · Accepted Answer · 2018-11-13 22:48:46Z

Depending on implementation I think you're just doing the right thing in the wrong place.

        while (current != null) {
            if (current.next == null) {
                newNode.next = null;
                newNode.previous = current;
                current.next = newNode;

                break;
            }

            if (current.next.data.compareTo(element) > 0) {
                newNode.next = current.next;
                newNode.previous = current;
                current.next.previous = newNode;
                current.next = newNode;
                break;

            } else {
                current = current.next;
            }
        }

Instead of checking if the currently selected node is smaller you need to check if the node after is bigger because then you can place the node. And checking if current.next is null needs to be done outside of that comparison.

Collectives™ on Stack Overflow

How to insert String data in a sorted doubly linked list?

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related