其操作的链表时间复杂度

Question

我正在根据股票市场程序实施链表。

它有和操作 - 购买

对于购买代码是

//Stocks is a linked List like so 
//LinkedList<Integer> stocks = new LinkedList<Integer>();
public void buy(int q, int p) {
    stocks.addLast(q); //add number of stocks
    stocks.addLast(p); //for i stocks i +1 = price of stock
}

此操作 addLast 是针对链表的，显然将给定元素添加到当前列表末尾的新位置。

因此，例如，如果我有一个列表，其中包含以下数据

//Stock, price, stock, price etc...
[100, 50, 5000, 30, 8000, 60]

如果我addLast是链表搜索最后一个元素，然后添加，因此时间复杂度将是 O（n）（仅就大哦而言）。还是索引到列表的末尾，意识到列表的末尾是stocks[5]然后在列表末尾插入引用新数据的新节点？

所以我的问题是，链表addLast()操作的时间复杂度是 O（n） 还是 O（1）？

在下面发布任何说明

Answer 1

如果你阅读 LinkedList 类的 javadoc，它会指出："所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引为准。

这意味着它是 O（1）

编辑

如果你想更好地实现你的股票名称，价目表，我认为最好创建一个包含股票描述的类：

public class Stock {
    private int stockName;
    private int stockPrice;
    // other methods, properties, constructor
}

然后创建一个LinkedList<Stock>

Answer 2

add()或addLast()的复杂性O(1)在列表的长度上。 从阅读LinkedList源代码中可以明显看出这一点。

（由于 javadoc¹ 中没有精确指定行为的这一方面，因此可以更改...理论上。 但是，我们可以自信地排除这种可能性。 即使它有意义（它没有！），这样的更改也会破坏许多现有的应用程序。 仅此一点就足以排除它不可信的可能性。

---

^{1 - 我认为javadoc句子"索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引为准"并明确适用于此方法。 您可能会争辩说add/addLast方法没有索引到列表中。}

Answer 3

查看 LinkedList 类的源代码，似乎addLast实际上调用了一个名为 linkLast 的方法，该方法是：

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

相关部分是在类中声明last的位置，transient Node<E> last;类似乎持有指向最后一个节点的"指针"。 然后，它使用给定的新节点进行更新。 因此，无论列表的大小如何，它都应该是 O（1）。