1

我正在尝试制作一个自定义链表，到目前为止，我已经弄清楚了如何制作一般结构和两种最简单的方法（insertFirst 和 deleteFirst）。我想做的下一件事是创建一个获取链接索引的 get 方法，然后返回该位置的字符串。我没有为每个链接分配任何索引或地址，因此我看不到如何引用链接列表中的特定位置。我看到如果我写 first.next 我得到第二项，first.next.next 我得到第三项....但我需要弄清楚如何制作我的索引参数（传递给 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) 来查找元素。

所以本质上这意味着你需要继续做 element.next 直到你到达第 n 个索引。

于 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 回答