Saturday, 7 September 2013

Linked List time complexity for it's operations

Linked List time complexity for it's operations

I am implementing a Linked list in terms of stock market program.
It has and operation - Buy
For Buy the code is
//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
}
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]
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?
So my question is, is addLast() operation for a linked list time
complexity of O(n) or O(1)?
Post below for any clarifications

No comments:

Post a Comment