Java中实现的链表中的Get方法

Question

我需要实现一个整数链表，从零开始（不使用现有的LinkedList类）。

这是代码：

一个单独的Link类

public class Link {
    public int data;
    public Link nextLink;

    public Link(int d1) {
        data = d1;      
    }

    public void printListElements(){
        System.out.println(data);
    }
}

和LinkedList类相关

public class LinkedList {
    private Link first;
    public LinkedList(){
        first = null;
    }

    public void add(int data1){
        Link linklist = new Link(data1);
        linklist.nextLink = first;
        first = linklist;
    }

    public void printList(){
    Link current=first;
    System.out.println("List Elements are ");
    while(current!=null){
       current.printListElements();
       current=current.nextLink;
    }
  }
}

您可以看到它已经具有add和printList方法。但是，我该如何创建一个get()方法来返回特定索引位置的值呢？

这就是我的意思：

public static void main(String args[]){
    LinkedList MyList = new LinkedList();

    MyList.add(1);
    MyList.add(2);
    MyList.add(3);
    MyList.add(4);

    System.out.println("MyList.get(0)"); // should get 1
        System.out.println("MyList.get(1)"); // should get 2 etc
}

Thank You in advance.

- user1714960

Answer 1

好的，既然这是一个链表，你没有任何方法直接访问除第一个元素之外的任何元素，对吧？所以唯一的方法就是从那里开始，并通过连续跟随下一个元素的链接来步进（直到到达由索引指定的元素），然后返回该元素。最简单的方法是使用循环。

- jonvuri

Answer 2

您当前的实现无法做到这一点。因为您将每个新节点都添加为头节点。

如果您更改您的 add() 方法，使每个新节点都添加为最后一个节点，那么您可以使用传递给 get() 方法的 index 值作为循环计数器来实现该功能。

- P.P

---

请注意，最好的方法是添加一个“last”字段来跟踪列表的尾部；否则，您将不得不遍历整个列表才能在末尾添加新元素。 - jonvuri

Answer 3

在链表中，您的元素被反转。

public int get(int i) {
    int n = indexOf(first); // count-1 actually
    Link current = first;
    while (n > i) {
        --n;
        current = current.nextLink;
    }
    return current.data;
}

private int indexOf(Link link) {
    if (link == null) {
        return -1;
    }
    return 1 + indexOf(link.nextLink);
}

- Joop Eggen

Answer 4

我建议使用双向链表：

class Node<T> {
   Node<T> next;
   Node<T> prev;
   T data;
}

class LinkedList<T> {
   Node<T> head;
   Node<T> tail;
   int count;
}

您的添加方法实际上只会创建一个新节点，并将其附加到尾部的“下一个”指针上，重新分配尾部并增加计数。 （是的，如果您有一个尾指针，您也可以使用单链表来完成此操作）

采用这种方法，添加是一个常数时间操作，并保留插入顺序（与您采用的单链表方法不同，其中未保留插入顺序）。

此外，您可以优化“获取”以查看所请求的索引是否更接近头部或尾部，并从适当的端点遍历以获取所需的节点。

我假设这是作业，所以我不想完全公开代码。

- Matt