已实现的链表中的 Get 方法，Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12695226/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Get method in a implemented Linked List, Java
提问by user1714960
I need to implement a Linked List of integers from zero (not using existing LinkedList class).
我需要从零实现一个整数链表（不使用现有的 LinkedList 类）。
This is the code:
这是代码：
A single Link class
单个 Link 类
public class Link {
public int data;
public Link nextLink;
public Link(int d1) {
data = d1;
}
public void printListElements(){
System.out.println(data);
}
}
and the LinkedList class
和 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;
}
}
}
As you see it has already addand printListmethod. But how do i make a get() method, which returns a value of a specific index.
如您所见，它已经添加了和printList方法。但是我如何创建一个 get() 方法，它返回一个特定索引的值。
This is what i mean:
这就是我的意思：
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.
先感谢您。
回答by jrajav
Well, since it's a linked list, you don't have any way to directly access any element except the first one, right? So the only way to do it is to start there and step through (by successively following the links to the next element) until you reach the element specified by the index, and then return that. The easiest way to do that is with a loop.
好吧，既然它是一个链表，除了第一个元素之外，你没有任何方法可以直接访问任何元素，对吗？因此，唯一的方法是从那里开始并逐步执行（通过连续跟踪到下一个元素的链接），直到到达索引指定的元素，然后返回该元素。最简单的方法是使用循环。
回答by P.P
You can't do that with your current implementation. Because you are adding every new node as the head node.
你不能用你当前的实现来做到这一点。因为您将每个新节点添加为头节点。
If you change your add()so that every new node is added as the last node then you can do that using your indexvalue passed to get()as the loop counter.
如果您更改您add()以便将每个新节点添加为最后一个节点，那么您可以使用index传递给get()作为循环计数器的值来做到这一点。
回答by Joop Eggen
In LinkedList you have your elements reverted.
在 LinkedList 中，您的元素已恢复。
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);
}
回答by Matt
I would recommend using a dual linked list:
我建议使用双链表：
class Node<T> {
Node<T> next;
Node<T> prev;
T data;
}
class LinkedList<T> {
Node<T> head;
Node<T> tail;
int count;
}
Your add method would actual just create a new node, and attach it to the "next" pointer of the tail, reassign the tail, and increment the count. (yes you could do this with a single linked list as well as long as you have a tail pointer)
您的 add 方法实际上只是创建一个新节点，并将其附加到尾部的“下一个”指针，重新分配尾部，并增加计数。（是的，您可以使用单个链表执行此操作，只要您有尾指针即可）
Which this approach, add is a constant time operation and preserves insertion order (unlike the single linked list approach you were taking, where insertion order is not preserved).
在这种方法中， add 是一个恒定时间操作并保留插入顺序（与您采用的单链表方法不同，其中不保留插入顺序）。
Also, you could optimize the "get" to see if the requested index is closer to the head or tail, and traverse from the appropriate end to get the node you want.
此外，您可以优化“获取”以查看请求的索引是否更接近头部或尾部，并从适当的末端遍历以获取所需的节点。
I assume this is homework, so i don't want to give the entire code away.
我认为这是家庭作业，所以我不想泄露整个代码。
