Java 单链表添加复杂度为 O(1)

Question

我正在尝试了解 LinkedLists（准确地说是单个 LinkedList）。

我听说/读到删除和添加操作将以 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 中的添加和删除操作是O(1)但遍历要删除或添加的节点是O(N)操作

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