Java 单个 LinkedList 添加复杂度为 O(1)

Question

我正在尝试理解链表(准确地说是单链表)。

我听说/读到删除和添加操作将以 O(1) 的复杂度执行，但我仍然不知道如何以 O(1) 的复杂度实现这两个操作。下面是我在java中的实现(注意:我不会c，c++编码，所以我最近开始了解数据结构)。

public class Node
{
    private Integer data    = null;
    private Node    next    = null;
    private int     size    = 0;

    public Node()
    {

    }

    private Node(Integer data)
    {
        this.data = data;
    }

    public boolean add(Integer data)
    {
        if (null == data) return false;
        if (null == this.data)
        {
            this.data = data;
        }
        else
        {
            if (null == this.next)
            {
                this.next = new Node(data);
            }
            else
            {
                this.next.add(data);
            }
        }
        size += 1;
        return true;
    }

    public Integer getDataAt(int index)
    {
        if (index == 0)
        {
            return this.data;
        }
        else
        {
            return this.next.getDataAt(index - 1);
        }
    }

    public int getSize()
    {
        return size;
    }
}

请建议我从现在开始编辑 add(data) 以使其复杂度为 O(1)。

Answer 1

只有LinkedList的Adding和Removing操作是O(1)，但是遍历到要删除或添加的节点是O(N)操作

如果保留对最后添加的元素的引用，则可以实现 O(1) 的复杂度，这样您就可以将添加新节点添加到最后遍历的元素的下一个节点。