添加元素到一個雙向鏈接列表保留一個訂單

Question

我試圖添加節點到一個雙向鏈接列表中，這個值是一個音樂，但我想保持它們的位置順序，就像在播放列表中一樣。 當我嘗試訪問music.head.next時，它返回一個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 1

你的addMusic版本沒有處理一個元素被添加到列表的末尾一個非空列表的情況。你也可以跳出while循環當元素列表中插入，防止一些不必要的檢查：

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

這裏是我的測試代碼的其餘部分（我確實添加了一些toString()方法，所以它更容易檢查方法做了什麼，我改名類myList的東西，是在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; 
    } 
}