在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语言）。否则，你会同时学习两件事，这通常比一次学习一件事更困难。