Javaで二重リンクリストを実装するのに手助けが必要です。[最終]

Question

こんにちは、皆さん、これまでのおかげで、このプロジェクトはかなり完成しました。

ここで私のコードと私が実装しなければならなかった特別な機能について説明します。 1.私のリンクリストは、特定の量の要素から始めなければなりません。これはDLLコンストラクタ にあります。2.作成された要素に新しい値を入力するメソッド。 3.特定のノードで値を取得するgetメソッドがあります。ユーザーがリストのサイズより大きいインデックス値を呼び出す場合は、新しいノードも作成されます。 4.要素を特定の場所に挿入するinsertメソッドも作成しました。

マイノードクラスは、（小文字のクラス名を気の毒に）次のようになります。

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

EDIT ：

ここで、あなたが望むもの（二重リンクリストデータ構造の任意のインデックス付き挿入関数）を理解したので、ここであなたを助けるかもしれないコードがあります：

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を実行するのと同じです。

オリジナルのポスト：

リンクリストと配列は、2つの完全に異なるデータ構造です。実装に焦点を当てるのではなく、データ構造で何をしたいか考えてみてください。データへのランダムアクセスが必要ですか？リンクされたリスト（二重）は、読み取りと書き込みの両方に適切な要素を見つけるのにO（n）時間かかるでしょう。挿入物に実装したロジックを自分で見たことがあります。配列の場合、ランダムアクセスはO（1）一定時間操作です。リストのようなデータ構造体を書き込みランダムにアクセスする場合は、new node[n]を使用して、メモリ内の配列オブジェクト全体を非公開にしてください。

これ以上のものがある場合は、古いデータのすべてを新しい配列にコピーしてコピーするように、インデックスのサイズの2倍の新しい配列を作成します。これはO（n）オペレーションですが、リストの先頭または末尾にリンクされたリストの挿入はO（1）の一定時間です。

中間地はありますか？実際にそこにある！バランスのとれたバイナリツリーを実装すると、ノードへのO（lg（n））の挿入とO（lg（n））アクセスを得ることができます。私はあなたのデータ構造をブラッシュアップすることをお勧めします。構造がどのように感じるかを理解するまで、鉛筆と紙でそれを試してから、コードに書いてください。あなたがJavaに慣れていないか、クラスによって必要とされている場合を除いて、最初に学んだ言語に固執してください（私はあなたが書いたスタイルと物事を "ポインタ"と呼んでいるからです）。それ以外の場合は、同時に2つのことを学ぶことになります。これは、一度に1つのことを学ぶことよりも一般的に困難です。