0 
public class A<E> extend AbstractList<E>{

private SLNode<E> Head = new SLNode<E>
private int length = 0;     // length of the list

 // I will skip the class of SLNode<E>
 // Head's element and successor is initialized as null in the class SLNode<E>

     public void add(int index, E element)  // insert an element in the list 
     {
         // if index is less than 0 or greater than the length
          if( (index < 0) || (index > length ) )
               throw new IndexOutOfBoundsException();

          if(index ==0)
          {
              SLNode<E> newnode = new SLNode<E>(element, null);  // make new node
              newnode.setSuccessor(Head.getSuccessor());  
              Head.setSuccessor( newnode);
              length++;
          }
       }

Q1. リストの先頭に要素を追加するこの正しい方法はありますか? (ダミーのヘッダー ノードを使用しますが、テールは使用しません) Q2. リストが空であっても空でなくても同じでしょうか?

4

4 に答える 4

0

これは悪い方法ではありませんが、「頭」に「ダミー」ノードを使用するのは少し珍しいことです。

ただし、「Head」を「current」に置き換え、それを「Head」に初期化してから、リストindexノードを「クロール」して挿入できるという利点があり、ゼロケースを特別にケース化する必要はありません.

 public void add(int index, E element)  // insert an element in the list 
 {
     // if index is less than 0 or greater than the length
      if( (index < 0) || (index > length ) ) {
           throw new IndexOutOfBoundsException();
      }

      // Find insertion point
      SLNode<E> current = Head;
      for (int i = 0; i < index; i++) {
          current = current.getSuccessor();
      }

      // Create & insert new node
      SLNode<E> newnode = new SLNode<E>(element, null);
      newnode.setSuccessor(current.getSuccessor());  
      current.setSuccessor( newnode);
      length++;
  }

(ただし、標準の命名規則では、クラス名の最初が大文字の名前を予約することに注意してください。)

于 2012-10-25T03:02:50.310 に答える
0

これがヘッドメソッドでの挿入であると仮定すると、なぜインデックスを渡す必要があるのか​​ わかりません。理想的には、挿入用のメソッドを1つだけにしたいと思います。しかし、あなたは具体的に頭に挿入を求めているので。

public void addToHead(E element)  // insert an element at head
     {
         if(length==0)
             throw new Exception("head does not exist");

         element.setSuccessor(head);
         head = element;


         length++;

       }
于 2012-10-25T03:13:10.253 に答える
0

Q1. リストの先頭に要素を追加するこの正しい方法はありますか? (ダミーのヘッダー ノードを使用しますが、テールは使用しません)

編集:あなたの質問を読み直し、あなたのコードを試した後、私はそう言うでしょう.

Q2. リストが空であっても空でなくても同じでしょうか?

編集: はい、空のリストで動作するようです。

dummy_header_list<String> theList = new dummy_header_list<String>();
System.out.println(theList);
theList.add(0,"first add");
System.out.println(theList);
theList.add(0,"second add");
System.out.println(theList);
theList.add(0,"third add");
System.out.println(theList);

与えます：

[]
[first add]
[second add,first add]
[third add,second add,first add]

このtoStringで：

public String toString()
{
   String output = "[";
   SLNode<E> temp = Head.getSuccessor();
   while ( temp != null ) {
      if ( output.length() == 1 ) {
         output = output + temp.toString();
      }
      else {
          output = output + "," + temp.toString(); 
      }
      temp = temp.getSuccessor();
   }
   output = output + "]";
   return output;
}
于 2012-10-25T03:33:31.893 に答える
0

リストの先頭に挿入するための特別なケースが本当に必要だとは思いません。このリストの先頭に挿入することは、リストの他の場所に挿入することと同じです。

public void add(int index, E element)
{
    // if index is less than 0 or greater than the length
    if ((index < 0) || (index > length))
        throw new IndexOutOfBoundsException();

    SLNode<E> previousNode = head;
    for ( int i = 0; i < index; i++ ) {
        previousNode = previousNode.getSuccessor();
    }

    SLNode<E> newNode = new SLNode<E>(element, previousNode.getSuccessor());
    previousNode.setSuccessor(newNode);
    length++;
}

基本的に、これはリストをトラバースして、後に挿入する正しいノードを見つけるだけです。インデックスが 0 の場合、すぐに先頭で停止します。挿入するノードを取得したら、次の 3 つの手順を実行します。

  1. 新しいノードを作成し、その後続ノードを前のノードの後続ノードに設定します
  2. 前のノードの後続ノードを新しいノードに設定します
  3. リストの長さに 1 を加える

これについていくつかの小さなテストを実行しましたが、うまく機能しているように見えました。

このアプローチは、 head が実際にリスト内の要素と見なされることはほとんどないと想定していることに注意してください。それは本当にリストを開始する場所です。つまり、head.getElement() は常にnull を返すということです。これは実際にはリストの一部ではありません。それがあなたが望んでいた実装かどうかはわかりませんが、リストが空であるはずの場合でも、ヘッド要素でリストを開始すると言ったときが最も理にかなっているように見えました。

于 2012-10-25T03:34:35.783 に答える