LinkedList（从头开始构建）add（）不起作用

Question

我正在做一个 class 作业，我必须从头开始构建一个单链表 class。我的问题是，当我遍历一系列项目并将它们添加到链表时，我的 add() 方法无法正常工作。更具体地说，1) 它复制系列中的第一个，2) 不添加系列中的最后一个。我在 ManualLinkedList class 中的 add() 方法有什么问题？

public class test {
    static class ManualLinkedList<T> {
        private static class Node<T> {
            T item;
            Node<T> next;
            Node<T> prev;

            public T getItem() {
                    return item;
                }
            public ManualLinkedList.Node<T> getNext() {
                    return next;
                }

            Node(Node<T> prev, T element, Node<T> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

        Node<T> head;
        Node<T> tail;
        int size = 0;

        public void add(T t) {
            final Node<T> l = tail;
            final Node<T> newNode = new Node<>(l, t, null);
            tail = newNode;
            if (l == null) {
                head = newNode;
            }
            else {
                l.next = newNode;
            }
            size++;
        }

        public int size() { return size; }

        public T getContentFromPosition(int position) {
            Node<T> np = head;
            T result = head.getItem();

            if (position == size) {
                result = tail.getItem();
            }
            for (int i = 1; i < size; i++) {
                if (i == position) {
                    result = np.getItem();
                }
                np = np.getNext();
            }
            return result;
        }
    } //end ManualLinkedList class


    public static void main(String[] args) {
        ManualLinkedList<Integer> test = new ManualLinkedList<>();
        test.add(1);
        test.add(2);
        test.add(3);
        test.add(4);
        test.add(5);
        test.add(6);
        test.add(7);
        test.add(8);

        for (int i =0; i < test.size; i++){
            System.out.println(test.getContentFromPosition(i));
        }
    }
}

预期输出：

实际输出：

1
1  // notice the duplicate first item
2
3
4
5
6
7  // notice the missing 8, or the last input

Answer 1

你的 add 函数实际上没问题。

但是，您的 getContentFromPosition 函数几乎是正确的，但还需要一些工作。您应该决定列表中的位置是从 0 还是从 1 开始计数。例如，如果列表中有 3 个元素，它们是位置 0、1、2 还是位置 1、2、3？

当您在 main 中使用 getContentFromPosition 函数时，您假设位置从 0 开始计数，但在编写该函数时，您似乎假设它们从 1 开始计数。

如果将 getContentFromPosition 修改为从 0 开始计数，那么您就可以摆脱检查 position==size 的特殊情况，然后您将从 0 而不是 1 开始循环。另外，为了提高效率，为什么不 return 找到结果而不是让循环继续运行?

Answer 2

您需要初始化 int size=1 而不是 0

并在循环的主要方法中更改为 int i=1 而不是 0

Answer 3

主要问题

索引在调用期间用作0..size-1
for getContentFromPosition 中的循环应该来自 0..size-1
大小 == 位置的用法与 getContentFromPosition

代码

        public T getContentFromPosition(int position) {
            if (position >= size) {
                return null;
            }
            Node<T> np = head;
            T result = head.getItem();
            if (position == size - 1) {
                result = tail.getItem();
            }
            for (int i = 0; i < size; i++) {
                if (i == position) {
                    result = np.getItem();
                    break;
                }
                np = np.next;
            }
            return result;
        }
    } //end ManualLinkedList class


    public static void main(String[] args) {
        ManualLinkedList<Integer> test = new ManualLinkedList<>();
        test.add(1);
        test.add(2);
        test.add(3);
        test.add(4);
        test.add(5);
        test.add(6);
        test.add(7);
        test.add(8);

        for (int i = 0; i < test.size; i++){
            System.out.println(test.getContentFromPosition(i));
        }
    }

Answer 4

在 getContentFromPosition 方法中，你的 for 循环应该从 0 开始。休息没问题。

for (int i = 0; i < size; i++)

LinkedList（从头开始构建）add（）不起作用

LinkedList (built from scratch) add() not working

java

linked-list

add

doubly-linked-list

主要问题

代码