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 回答