链表操作的时间复杂度 [英] Linked List time complexity for its operations

问题描述

我正在实施一个关于股票市场程序的链表.

I am implementing a Linked list in terms of stock market program.

具有操作性-购买

购买代码是

//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用于链表显然是将给定元素添加到当前列表末尾的新位置.

This operation addLast is for a Linked list obvious adds the given element to a new position at the end of a current list.

例如，如果我有一个列表，可以说以下数据

So for example if I have a list that has lets say the following data

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

如果我 addLast 是链表，则搜索最后一个元素，然后相加，因此时间复杂度将为O(n)(仅针对Big Oh).还是索引到列表的末尾，意识到列表的末尾是 stocks [5] ，然后在列表的末尾插入引用新数据的新节点?

If I addLast is the Linked List search for the last element and then adding and therefore the time complexity would be O(n) (In terms of Big Oh only). Or is it indexing to the end of the list, realizing that the end of the list is say stocks[5] then inserting a new node referencing the new data at the end of the list?

所以我的问题是， addLast()操作是否为O(n)或O(1)的链表时间复杂度?

So my question is, is addLast() operation for a linked list time complexity of O(n) or O(1)?

在下面发布任何澄清内容

Post below for any clarifications

推荐答案

如果您阅读了

If you read the javadoc for the LinkedList class, it states: "All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index."

这意味着它是O(1)

修改

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

If you want a better implementation of your Stock name, price list, I think it would be better to create a class containing the description of the stocks:

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

    // other methods, properties, constructor
}

然后创建一个 LinkedList< Stock>

这篇关于链表操作的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！