PsiDoN PsiDoN - 3 months ago 15
Java Question

Adding elements to a doubly linked list keeping an order

I'm trying to add nodes to a doubly linked list which value is a music, but I want to keep the order of their position, just like in a playlist.
When I try to access to the music.head.next it returns a java.lang.NullPointerExecption.

class Music {
String title;
int position;
}
class Node {
Music value;
Node next;
Node prev;
}

class myList {
Node head;
Node tail;
}

class Main {

static void addMusic (myList musics, Music music) {

Node node = new Node();
node.value = music;

if (musics.head == null) {
musics.head = node;
musics.tail = node;
} else {
Node current = musics.head;
Node previous = current;
while (current != null) {
if (current.value.position > music.position) {
node.next = current;
current.prev = node;
node.prev = previous;
previous.next = node;
}
previous = current;
current = current.next;
}

}
}

public static void main (String[] args) {

}

}

Answer Source

Your version of addMusic did not handle the case that an element is added to the end of the list for a non empty list. You could also jump out of the while loop when the element was inserted in the list to prevent some unnecessary checks:

public void addMusic (MusicList musics, Music music)
{
  Node node = new Node();
  node.value = music;

  if (musics.head == null)
  {
    // list is empty
    musics.head = node;
    musics.tail = node;
  }
  else if (music.position > musics.tail.value.position)
  {
    // add at the end

    // update "pointers"
    musics.tail.next = node;
    node.prev = musics.tail;

    // add the new element at the end of the list
    musics.tail = node;
  }
  else
  {
    // search for the insertion position
    Node current = musics.head;
    Node previous = current;
    while (current != null)
    {
      if (current.value.position > music.position)
      {
        node.next = current;
        current.prev = node;
        node.prev = previous;
        previous.next = node;
        break;
      }
      previous = current;
      current = current.next;
    }
  }
}

Here is the rest of my test code (I did add some toString() methods so it is easier to check what the method did. And I renamed the class myList to something that is a valid class name in Java:

public void test()
{
  MusicList myMusic = new MusicList();
  addMusic(myMusic, new Music("Title1", 1));
  addMusic(myMusic, new Music("Title3", 3));
  addMusic(myMusic, new Music("Title2", 2));
  addMusic(myMusic, new Music("Title4", 4));
  System.out.println(myMusic.toString());
}

public class Music
{
  String title;
  int position;

  public Music (String title, int position)
  {
    this.title = title;
    this.position = position;
  }

  @Override
  public String toString()
  {
    return "#" + position + " " + title;
  }
}


public class Node
{
  Music value;
  Node next;
  Node prev;

  @Override
  public String toString()
  {
    return value.toString();
  }
}

public class MusicList
{
  Node head;
  Node tail;

  @Override
  public String toString()
  {
    String result = "My List:";
    Node current = head;
    while (current != null)
    {
      result += "\r\n   " + current;
      current = current.next;
    }
    return result;
  }
}