在Java中需要幫助實現雙向鏈表[最終]

Question

你好，感謝所有幫助到目前爲止，我已經完成了這個項目。

現在生病了解釋我的代碼和我必須實現的特殊功能。 1.我的鏈表必須以特定數量的元素開始，你會在dll的構造函數中看到這一點。2.一種將新值輸入到創建的元素中的方法。 3.我有一個get方法來獲取某個節點的值。如果用戶調用的索引值大於列表大小 ，也會創建新節點4.我還創建了一個將元素插入到特定位置的插入方法。

我的節點類看起來像這樣（對不起，小寫的類名）：

public class node { 

private int _value; 

public node(int v){ 
    _value = v; 
} 

public node(){ 

} 

public int get(){ 
    return _value; 
} 

public void set(int v){ 
    _value = v; 
} 

public node next = null; 
public node prev = null; 
} 

我的DLL類（奇怪的名字，我知道這個項目只是標題）：

public class BetterArray{ 

private int _size; 
private node _head; 
private node _tail; 

public BetterArray(int n){ 
    _head = null; 
    _tail = null; 
    _size = n; 

    if(_head == null){ 
     _head = new node(0); 
     _tail = _head; 
    } 

    for(int i = 1; i < n; i++){ 
     node current = _head; 
     for(int j = 1; j < i; j++){ 
      current = current.next; 
     } 
     node newNode = current.next; 
     current.next = new node(0); 
     current.next.next = newNode; 
     current.next.prev = current; 
     _tail = current.next; 
    } 
} 

public BetterArray(){   
} 

public int get(int index){ 
    int value = 0; 
    node temp = _head; 
    if(index < _size){ 
     for(int loc = 0; loc < index; loc++){ 
      temp = temp.next; 
     } 
     value = temp.get(); 
    } 
    else{ 
     for(int i = _size; i <= index; i++){ 
      node current = temp; 
      for(int j = _size; j < i; j++){ 
       current = current.next; 
      } 
      node newNode = current.next; 
      current.next = new node(0); 
      _size++; 
      current.next.next = newNode; 
      current.next.prev = current; 
      _tail = current.next; 
     } 
    } 
    return value; 
} 

public void put(int value, int index){ 
    node temp = _head; 
    if(index < _size){ 
     for(int loc = 0; loc < index; loc++){ 
      temp = temp.next; 
     } 
     temp.set(value); 
    } 
    else{ 
     for(int i = _size; i < index; i++){ 
      node current = temp; 
      for(int j = _size; j < i; j++){ 
       current = current.next; 
      } 
      node newNode = current.next; 
      current.next = new node(value); 
      _size++; 
      current.next.next = newNode; 
      current.next.prev = current; 
      _tail = current.next;   
     } 
    } 
} 

public void insert(int value,int index){ 
    node current = _head; 

     for(int loc = 0; loc < index - 1; loc++){ 
      current = current.next; 
     } 

     node temp = current.next; 
     current.next = new node(value); 
     _size++; 
     current.next.next = temp; 
     current.next.prev = current; 
     _tail = current.next; 
    } 
} 

public void delete(int index){ 
    node pre = _head; 

    for(int loc = 0; loc < index; loc++){ 
     pre = pre.next; 
    } 
    node current = pre.next; 
    pre.next = current.next; 
    _size--; 
} 
public int getSize(){ 
    return _size; 
} 

Answer 1

編輯：

現在，我更好地理解你想要什麼（雙鏈表數據結構的任意索引插入函數），下面是一些代碼可以幫助你：

public class BetterArray{ 

    public node _head = null; 
    public node _tail = null; 

    public BetterArray(){ 
     _head = _tail = new node(); 
    } 

    public node insert(int val, int index) { 
     if (index < 0) { 
      throw new IllegalArgumentException("You must provide an index which is not negative"); 
     } 
     node current = _head; 
     for (int i = 0; i < index; i++) { 
      if (current.next == null) { 
       current.next = new node(); 
       current.next.prev = current; 
       _tail = current; 
      } 
      current = current.next; 
     } 
     current.set(val); 
     return current; 
    } 
} 

public class node { 

    private int _value; 
    private boolean _initialized; 

    public node(int v){ 
     _value = v; 
     _initialized = true; 
    } 

    public node(){ 
     _initialized = false; 
    } 

    public int get(){ 
     if (!_initialized) { 
      throw new IllegalArgumentException("This node has not been set with any value"); 
     } 
     return _value; 
    } 

    public void set(int v){ 
     _value = v; 
     _initialized = true; 
    } 

    public node next = null; 
    public node prev = null; 
} 

您也可以嘗試一下。只是做這樣的事情：

BetterArray whatever = new BetterArray(); 
whatever.insert(5,3); 
System.out.println(whatever._head.next.next.next.get()); 

只是你知道，也有標準的Java數據結構已經實現。你可能想看看LinkedList。基本上我所做的與添加節點相同，直到它的大小阻止它獲得IllegalArgumentException，然後執行set。

ORIGINAL POST：

鏈表和陣列是兩個完全不同的數據結構。不要關注實現，而是想想你想要用數據結構做什麼。需要隨機訪問數據？一個（雙重）鏈接列表將花費O（n）時間來爲讀取和寫入找到正確的元素;你已經用你在插入中實現的邏輯自己看過了。對於數組，隨機訪問是O（1）常量時間操作。如果要編寫像List這樣的數據結構以進行隨機訪問，請嘗試使用new node[n]，並將整個數組對象私有地保存在內存中。

如果有更大的事情，標準做法是創建一個新索引的索引大小的兩倍，並將所有舊數據複製到新數組中。這是一個O（n）操作，而列表開頭或末尾的鏈接列表的插入是O（1）個常量時間。

有一箇中間地帶嗎？其實有！如果實現平衡二叉樹，則可以獲得O（lg（n））插入和O（lg（n））訪問節點的權限。我建議你刷一下你的數據結構。嘗試用鉛筆和紙做出來，直到你理解結構的感覺，然後把它寫入代碼。除非你對Java感到滿意，或者你的課程需要它，否則請堅持使用你首先學習的任何語言（因爲你寫的風格和你稱之爲「指針」的方式，我假定C語言）。否則，你會同時學習兩件事，這通常比一次學習一件事更困難。