https://www.youtube.com/watch?v=htzJdKoEmO0&list=PLD4CAE0D1D2EEF760

In the link above, he discusses linked lists and their advantages and disadvantages. In the 19th minute, he says that inserting in the middle of a linked list takes constant time as long as you have a reference to the node before it.

In the 33rd min, he says that finding the nth item in a linked list would take O(n) time if you don't have a reference to the item you want to look at.

I don't understand why and how you would and you wouldn't have a reference to the item?

For inserting:

Calling the above code with say Object3.insert(10) would insert an item after 10 and change the pointers appropriately.

Why would it not work for search like that in constant time? If you knew you wanted the 100th item, why wouldn't Object100.search() not work in constant time?

the search method could have something like

I know I am missing something basic, but please help me understand this.

Prasanna Raman wrote:

Calling the above code with say Object3.insert(10) would insert an item after 10 and change the pointers appropriately.

The argument to insert is a value you want to store in a node, it is not an index. There are no indexes in a linked list. The only way to know if you are inserting a value after the 10th node is that you already have 10 nodes in the list and next points to the end of the list. If all you are doing is building a list by inserting values, then next is always going to be pointing to the end of the list. In this case, if you want to insert a node in the middle of the list someplace, say at the 500th node out of 1000 nodes, how you going to insert it if next points at the end of the list? You can't go directly to that node without starting at the head node and traversing the list 499 times.

Prasanna Raman wrote:

Why would it not work for search like that in constant time? If you knew you wanted the 100th item, why wouldn't Object100.search() not work in constant time?

How do you get to the 100th node? There is no index to get there. If you want the item in the 100th node, you have to start at head and traverse 99 next times to get there--which is 99 operations of a counter. That is some fraction of the number of nodes in your list, c x n where c is between 0 and 1 and n is the number of nodes in your list. That is O(n).

Prasanna Raman wrote:

the search method could have something like

This code has nothing to do with getting to node 99.

If you treat a linked list like an array, you have to count nodes equal to the number of your index minus 1 in the worst case, depending on where your last reference was in the list and if you kept track of the node number it was in, otherwise you search for a value and you still have to traverse some c x n number of nodes before you find the value, which is still O(n).

Prasanna Raman wrote:Thank you for replying, Mack. I understand how search will take O(n) time, but I don't understand how inserting in the middle takes constant time, or does it?

Yes, if you are already in the middle of the list at a point where you want to insert a new node, it is constant time because you just change the reference to next where you insert it and make the insertion node's next point to the one after it. Compare that to an array, even though you can jump directly to index 100 in an array to read the value, you have to make a new array bigger than the first and copy the first 100 valued into it, then the value you want to insert in cell 101 and then copy the rest of the values into the new array.

**if**I am already in the middle of the list... So, if not is it O(n) just like search?

If so, why do we generally say that insertion/deletion takes constant time and search linear time in a linked list in Java?

Prasanna Raman wrote:OK, so

ifI am already in the middle of the list... So, if not is it O(n) just like search?

If so, why do we generally say that insertion/deletion takes constant time and search linear time in a linked list in Java?

Actually it is only constant time O(1) at the beginning or end, it is O(n) + O(1) in the middle because you always have to get to where you want to insert a node first.

As shown in the chart here: http://en.wikipedia.org/wiki/Linked_list

Prasanna Raman wrote:OK, so

ifI am already in the middle of the list... So, if not is it O(n) just like search?

If so, why do we generally say that insertion/deletion takes constant time and search linear time in a linked list in Java?

There are two different things in play here: Inserting and searching.

As already said, the actual act of inserting takes constant time,

*providing you are already correctly positioned*. Thus, adding with LinkedList's ListIterator

*may*only only take O(1) time (providing you're in the right place), but inserting with LinkedList.add(n)

__always__takes O(n) time.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

And, in Java LinkedList class, if asked a general question, what would we say the run times are?

Thanks,

Prasanna

So, searching is an O(n) operation, and inserting itself takes O(1) time, but to get to the point of insertion takes O(n) time unless you're already there with head or tail or by means of a pointer to that location. Is my understanding right?

And, in Java LinkedList class, if asked a general question, what would we say the run times are?

Thanks,

Prasanna

On the other hand, the Iterator and ListIterator returned by the iterator() and listIterator() methods on LinkedList all have O(1) performance for all methods, inlcuding add(E) and remove(). So, you get O(1) performance if you can use the Iterator, while iterating. Of course the iteration itself is O(n). But once you're doing that anyway, you don't need to make things worse by calling an O(n) method from

*within*the iteration. Stick to O(1) wherever possible.

It is sorta covered in the JavaRanch Style Guide. |