1

カスタムリンクリストを作成しようとしていますが、これまでのところ、一般的な構造と2つの最も簡単な方法（insertFirstとdeleteFirst）を作成する方法を理解しました。次に実行したいのは、リンクのインデックスを取得し、その場所の文字列を返すgetメソッドを作成することです。各リンクにインデックスまたはアドレスが割り当てられていないため、リンクリスト内の特定の場所を参照する方法がわかりません。first.nextと書くと、2番目の項目が取得され、first.next.nextと3番目の項目が取得されることがわかります。ただし、インデックスパラメーター（getメソッドに渡されるパラメーター）の作成方法を理解する必要があります。 ）私のリスト内の適切な場所と相関させます....どうすればこれを行うことができますか？

ずさんなコードは許してください...リンクリストの構造を把握したら、必ず詳細をクリーンアップします。

これが私のコードです、ありがとうございます！

テストコード

 class LinkedListTest {
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();

        list.insertFirst("cat");
        list.insertFirst("dog");
        list.insertFirst("fish");
        list.insertFirst("cow");
        list.insertFirst("horse");
        list.insertFirst("pig");
        list.insertFirst("chicken");

        System.out.println(list.get(1));

    }
}

私のクラス 

public class LinkedList
{
    private Link first;


    public LinkedList()
    {
        first = null;
    }

    public void insertFirst(String word)
    {
        Link link = new Link(word);
        link.next = first;
        first = link;
    }

    public String deleteFirst()
    {
        Link temp = first;
        first = first.next;
        return temp.toString();
    }

    public String get(int index)
    {
        // the following is just to show that I can access different links
        // by adding more .next's after first--- but i need a way to access
        // the correct link based on the index passed in

        // String second = first.next.item;
        String third = first.next.next.item;
        // String fourth= first.next.next.next.item

        return third;
    }

}



public class Link
{
    public String item;
    public Link next;


    //Link constructor
    public Link(String theItem)
    {
        item = theItem;
    }
}
4

5 に答える 5

3

LinkedListには、要素を見つけるためのO（n）が必要です。

つまり、本質的にこれが意味するのは、n番目のインデックスに到達するまでelement.nextを実行し続ける必要があるということです。

于 2012-10-22T18:57:00.860 に答える
3

get(0)それが最初の要素を返すと仮定します：

このメソッドを内部に配置する場合public class LinkedList:

    public String get(int index)
    {
        assert( index >= 0 )
        Link current = this.first;
        while (index > 0) {
            index--;
            current = current.next;
            // Check to see if this is out of bounds of the links
            if (current == Null) {
                // Since you are returning a String, you can also return
                // some kind of a flag to say that the index is out of bounds
                return Null;
            }
        }
        return current.item;       
    }

または、これを内部に実装することもできますがpublic class Link:、呼び出しスタックのスペースを浪費するため、これはお勧めできません。

    public String get(int index)
    {
        assert ( index >= 0 )
        if ( index == 0 ) {
            return this.item;
        } else {
            index--;
            if ( next == null ) {
                return Null;
            }
            return next.get(index)
        }
    }

およびパブリッククラスLinkedList内：

    public String get(int index)
    {
         return first.get(index);
    }

お役に立てれば！

于 2012-10-22T18:57:53.303 に答える
2

まず、独自のLinkedListクラスを作成する場合は、既存のクラスを使用するのではなく、そのように名前を付ける必要がありますLinkedList。だから、むしろあなたは使うことができますMyLinkedList

次に、LinkedListの要素にインデックスでアクセスすることはできません。それはどのようLinkedListに機能するかではなく、独自に作成する場合は機能するはずです。むしろ、値に基づいてそれらを取得します。したがって、値をgetメソッドに渡し、を繰り返して、指定された値LinkedListで適切なLink値を取得する必要があります。

于 2012-10-22T18:55:04.217 に答える
0

再帰的

 public String get(int index)
        {
            assert index >= 0;
            return get(index, first);       
        }

 public String get(int index, Link cursor) {
         if (cursor == null) {
            return null;
         } else if (index == 0) {
            return cursor.toString();
         } else {
           return get(index-1, cursor.next);
         }
  }

反復

public String get(int index)
{
    assert index >= 0;
    Link cursor = first;
    while (index > 0) {
       if (cursor == null) {
            return null;
        }
        cursor = cursor.next;
        index--;
    }
    return cursor.toString();       
}
于 2012-10-22T19:02:25.197 に答える
0

これはあなたが必要とするものであなたを助けるはずです：

http://www.dreamincode.net/forums/topic/143089-linked-list-tutorial/

于 2012-10-22T19:07:12.080 に答える