在已实现的链接列表中获取方法，Java

我需要从零（不使用现有的LinkedList类）实现链接列表中的整数。在已实现的链接列表中获取方法，Java

这是代码：

单链路级

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; 
    } 
    } 
}

正如你看到它已经添加和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 
}

预先感谢您。

来源

2012-10-02 user1714960

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

来源

2012-10-02 17:31:10 jrajav

你不能用你当前的实现做到这一点。因为您将每个新节点添加为头节点。

如果您改变add()让每一个新的节点被添加作为最后一个节点，那么你可以做到这一点使用传递给get()作为循环计数器的值index。

来源

2012-10-02 17:32:54

请注意，最好的方法是通过添加'last'字段来跟踪列表的尾部;否则，您将不得不遍历整个列表，以便在结尾添加新元素。 – jrajav

在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); 
}

来源

2012-10-02 17:43:38

我会建议使用双链表：

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

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

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

这种方法添加的是一个常量时间操作并保留了插入顺序（与您正在使用的单链表方法不同，其中未保留广告订单）。另外，您可以优化“get”以查看请求的索引是否更接近头部或尾部，并从适当的末端遍历以获得所需的节点。

我认为这是家庭作业，所以我不想给整个代码。

来源

2012-10-02 18:53:15 Matt

在已实现的链接列表中获取方法，Java

回答

相关问题