6

我正在根据股票市场计划实施链接列表。

它具有和操作 - 购买

购买代码是

//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]

如果 IaddLast是链表搜索最后一个元素，然后添加，则时间复杂度将为 O(n)（仅就 Big Oh 而言）。或者它是索引到列表的末尾，意识到列表的末尾是说stocks[5]然后在列表的末尾插入一个引用新数据的新节点？

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

在下面发布任何澄清

4

3 回答 3

5

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

这意味着它是 O(1)

编辑

如果您想要更好地实现您的股票名称、价格表，我认为创建一个包含股票描述的类会更好：

public class Stock {
    private int stockName;
    private int stockPrice;

    // other methods, properties, constructor
}

然后创建一个LinkedList<Stock>

于 2013-09-08T00:42:36.587 回答
2

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

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

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

于 2013-09-08T00:42:24.533 回答
1

查看 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)。

于 2013-09-08T00:48:31.683 回答