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

Question

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

我 heard/read 删除和添加操作将以 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) 的复杂度，这样您就可以将添加新节点添加到最后遍历的元素的下一个节点。

Answer 2

在 linkedList 中，如果你有头指针和尾指针指向节点链表的第一个和最后一个，那么在恒定时间内，你可以在 node.If 的第一个或最后一个位置添加和删除你想要删除的元素必须找到那个元素，在最坏的情况下，该元素将在最后。在双链表中，您可以从开始和结束开始，因此您必须遍历直到在最坏的情况下它将是 O(n)。

Answer 3

感谢大家的支持，作为数据结构的菜鸟，我想了解 ds 是如何工作的，而不是从别人的实现中复制粘贴。

Neeraj Jain 和 Gati Sahu 的 explanations/answer 帮助我在复杂度为 O(1) 的 LinkedList 中实现了我正在寻找的添加（数据）。

所以我所做的是“分离普通节点 class 并通过操作创建 LinkedList class。

class Node
{
    private Integer data    = null;
    private Node    next    = null;

    public Node(Integer data)
    {
        super();
        this.data = data;
    }

    public Integer getData()
    {
        return data;
    }

    public Node getNext()
    {
        return next;
    }

    public void setData(Integer data)
    {
        this.data = data;
    }

    public void setNext(Node next)
    {
        this.next = next;
    }

}

public class LinkedList
{
    Node    head;
    Node    end;

    public Node getHead()
    {
        return head;
    }

    public boolean add(Integer data)
    {
        if (null == head)
        {
            head = new Node(data);
            end = head;
        }
        else
        {
            addAtEnd(data);
        }
        return true;
    }

    public void addAtEnd(Integer data)
    {
        end.setNext(new Node(data));
        end = end.getNext();
    }

    public void addAtFirst(Integer data)
    {
        Node tmpNode = head;
        head = new Node(data);
        head.setNext(tmpNode);
    }
}

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

Java single LinkedList add with O(1) complexity

java

data-structures

singly-linked-list