从头开始创建LinkedList类

Question

我们被赋予了从头开始创建LinkedList的任务,并且绝对没有给出读数来指导我们这个由migrane引起的任务.此外,所有在线似乎只使用Java内置的LinkedList方法和东西.无论如何,链接列表在使用Java的默认内容时非常有意义,但是从头开始创建它没有任何意义.可以说我有

public class LinkedList {
  private LinkedList next;  
  private final String word;
  // constructor
  public LinkedList(String word, LinkedList next) {
    this.word = word;
    this.next = next;
  }

因此神奇地我们有一个链表.到底是怎么回事？我是如何创建这样的链接列表的？这是如何运作的？我应该编写一个append方法,将给定的String word参数添加到thislinkedlist的末尾.我试着看看内置java链接列表类的addLast内置方法,但它对我没有帮助,因为我真的不明白发生了什么.任何人都在乎帮助我:)

Answer 1

如果您实际上正在构建一个真实的系统,那么是的,如果您需要的话,那么您通常只需使用标准库中的内容.也就是说,不要认为这是毫无意义的运动.了解事物是如何工作的很好,理解链表是了解更复杂数据结构的重要一步,其中许多数据结构在标准库中不存在.

您创建链接列表的方式与Java集合API执行方式之间存在一些差异.Collections API试图遵循更复杂的界面.Collections API链表也是一个双向链表,而您正在构建一个单链表.你正在做什么更适合课堂作业.

对于您的LinkedList类,实例将始终是至少一个元素的列表.通过这种设置,您null可以在需要空列表时使用.

认为next是"列表的其余部分".实际上,许多类似的实现使用名称"tail"而不是"next".

这是一个LinkedList包含3个元素的图表:

请注意,它是LinkedList指向单词("Hello")的对象和2个元素的列表.2个元素的列表有一个单词("Stack")和一个1元素的列表.1个元素的列表有一个单词("溢出")和一个空列表(null).因此,您可以将其next视为另一个恰好是一个元素更短的列表.

您可能希望添加另一个只接受String的构造函数,并设置旁边的null.这将用于创建1元素列表.

要追加,你是否next是null.如果是,则创建一个新的元素列表并设置next为该列表.

next = new LinkedList(word);

如果接下来没有null,则next改为追加.

next.append(word);

这是递归方法,这是最少量的代码.您可以将其转换为在Java ^*中更高效的迭代解决方案,并且不会冒很长列表的堆栈溢出的风险,但我猜测您的分配不需要复杂程度.

^{*有些语言有尾调用消除,这是一种优化,它允许语言实现将"尾调用"(在返回之前调用另一个函数作为最后一步)转换为(有效地)"goto".这使得这样的代码完全避免使用堆栈,这使得它更安全(如果不使用堆栈,则不能溢出堆栈)并且通常更有效.Scheme可能是具有此功能的语言中最着名的示例.}

Answer 2

你编码的不是LinkedList,至少不是我认识的那个.对于此分配,您要创建两个类:

LinkNode
LinkedList

阿LinkNode具有用于它包含的数据中的一个成员字段,以及LinkNode到下一个基准LinkNode在LinkedList.是的,它是一个自引用数据结构.一个LinkedList只是有一个特殊的LinkNode引用列表中的第一项参考.

当您在其中添加项目时LinkedList,您将遍历所有项目,LinkNode's直到到达最后一项.这LinkNode's接下来应该为空.然后LinkNode在这里构造一个新的,设置它的值,并将其添加到LinkedList.

public class LinkNode { 

    String data;
    LinkNode next;

    public LinkNode(String item) { 

       data = item;

    }

}

public class LinkedList { 

    LinkNode head;

    public LinkedList(String item) { 

       head = new LinkNode(item);

    }

    public void add(String item) { 

       //pseudo code: while next isn't null, walk the list
       //once you reach the end, create a new LinkNode and add the item to it.  Then
       //set the last LinkNode's next to this new LinkNode

    }


}

Answer 3

如何实现非递归链表的全功能实现？

我为我的Algorithms I类创建了这个作为跳板的基石,以便在为编配编写双向链接队列类之前获得更好的理解.

这是代码:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<T> implements Iterable<T> {
    private Node first;
    private Node last;
    private int N;

    public LinkedList() {
        first = null;
        last = null;
        N = 0;
    }

    public void add(T item) {
        if (item == null) { throw new NullPointerException("The first argument for addLast() is null."); }
        if (!isEmpty()) {
            Node prev = last;
            last = new Node(item, null);
            prev.next = last;
        }
        else {
            last = new Node(item, null);
            first = last;
        }
        N++;
    }

    public boolean remove(T item) {
        if (isEmpty()) { throw new IllegalStateException("Cannot remove() from and empty list."); }
        boolean result = false;
        Node prev = first;
        Node curr = first;
        while (curr.next != null || curr == last) {
            if (curr.data.equals(item)) {
                // remove the last remaining element
                if (N == 1) { first = null; last = null; }
                // remove first element
                else if (curr.equals(first)) { first = first.next; }
                // remove last element
                else if (curr.equals(last)) { last = prev; last.next = null; }
                // remove element
                else { prev.next = curr.next; }
                N--;
                result = true;
                break;
            }
            prev = curr;
            curr = prev.next;
        }
        return result;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Iterator<T> iterator() { return new LinkedListIterator(); }

    private class LinkedListIterator implements Iterator<T> {
        private Node current = first;

        public T next() {
            if (!hasNext()) { throw new NoSuchElementException(); }
            T item = current.data;
            current = current.next;
            return item;
        }

        public boolean hasNext() { return current != null; }

        public void remove() { throw new UnsupportedOperationException(); }
    }

    @Override public String toString() {
        StringBuilder s = new StringBuilder();
        for (T item : this)
            s.append(item + " ");
        return s.toString();
    }

    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        while(!StdIn.isEmpty()) {
            String input = StdIn.readString();
            if (input.equals("print")) { StdOut.println(list.toString()); continue; }
            if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
            if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
            break;
        }
    }
}

注意:这是单链表的非常基本的实现.'T'类型是通用类型占位符.基本上,此链接列表应该适用于从Object继承的任何类型.如果将它用于基本类型,请确保使用可等级的等价类(对于'int'类型,请使用'Integer').'last'变量不是必需的,只是它将插入时间缩短为O(1).删除速度很慢,因为它们在O(N)时间运行,但它允许您删除列表中第一次出现的值.

如果你想要,你也可以考虑实施:

• addFirst() - 将新项添加到LinkedList的开头
• removeFirst() - 从LinkedList中删除第一个项目
• removeLast() - 从LinkedList中删除最后一项
• addAll() - 将项目列表/数组添加到LinkedList
• removeAll() - 从LinkedList中删除列表/数组项
• contains() - 检查LinkedList是否包含项目
• contains() - 清除LinkedList中的所有项目

老实说,它只需要几行代码就可以使它成为一个双向链表.这与双链表之间的主要区别在于双链表的节点实例需要一个指向列表中前一个元素的附加引用.

这对于递归实现的好处是它更快,并且您在遍历大型列表时不必担心泛滥堆栈.

在调试器/控制台中有3个命令可以测试它:

• 将值加上'+'将其添加到列表中.
• 使用' - '进行前缀将从列表中删除第一个匹配项.
• 键入'print'将打印出列表,其中的值以空格分隔.

如果您从未见过其中一个如何工作的内部建议,我建议您在调试器中逐步执行以下操作:

• add() - 将新节点添加到末尾,或者如果列表为空则初始化第一个/最后一个值
• remove() - 从开始到结束遍历列表.如果找到匹配项,则会删除该项,并连接链中上一个和下一个链接之间的断开链接.如果没有上一个或下一个链接,则会添加特殊例外.
• toString() - 使用foreach迭代器简单地从头到尾遍历列表链.

虽然对于像列表这样的列表有更好和更有效的方法,但了解应用程序如何通过引用/指针遍历是了解有多少高级数据结构工作的必要条件.

Answer 4

提示1:阅读http://en.wikipedia.org/wiki/Linked_list上链接列表的说明

提示2:LinkedList的Java实现是一个双向链表.你的是一个单独的链表.算法不直接适用.

也:

...但是从头开始创建[链表类]没有任何意义.

这取决于工作所需的结果.如果目标是生成满足某些功能/非功能要求的代码,那么您是对的.如果真正的目标是让您学习如何编程/设计API /实现非平凡的数据结构,那么最终产品的实用性几乎完全无关紧要.

因此神奇地我们有一个链表

你实际拥有的是一个开放数据类型,可用于构建(某种)列表.但这不是你老师想要的.它肯定不会被认为是一个有用的列表抽象.一个有用的抽象包括:

• 方法来做程序员不想一遍又一遍地重复的事情,以及

• 一个抽象层,阻止程序员"破坏"列表; 例如,意外地创建一个循环,或意外地将子列表拼接在两个列表中以创建倒置树.

Answer 5

当然,链接列表对编程n00bs有点困惑,几乎所有的诱惑都是将它看作俄罗斯玩偶,因为它看起来像是LinkedList对象中的LinkedList对象.但这很难想象,而是像计算机一样看待它.

LinkedList =数据+下一个成员

如果next是NULL,它是列表的最后一个成员

所以5个成员的LinkedList将是:

LinkedList(Data1,LinkedList(Data2,LinkedList(Data3,LinkedList(Data4,LinkedList(Data5,NULL)))))

但你可以简单地想到它:

Data1 - > Data2 - > Data3 - > Data4 - > Data5 - > NULL

那么,我们如何找到这个结束？好吧,我们知道NULL是结束所以:

public void append(LinkedList myNextNode) {
  LinkedList current = this; //Make a variable to store a pointer to this LinkedList
  while (current.next != NULL) { //While we're not at the last node of the LinkedList
    current = current.next; //Go further down the rabbit hole.
  }
  current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List!
  return; //and we're done!
}

这当然是非常简单的代码,如果你给它一个循环链表,它将无限循环!但这是基础知识.