• Post Reply Bookmark Topic Watch Topic
  • New Topic

Linked Lists  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

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.
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, so 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?
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:OK, so 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?


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
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:OK, so 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?

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
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Mack and Winston. 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
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mack Wilmot wrote: . . . it is O(n) + O(1) . . .
There is no such thing as O(n) + O(1). That is O(n) time.
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Mack Wilmot wrote: . . . it is O(n) + O(1) . . .
There is no such thing as O(n) + O(1). That is O(n) time.


There is such a thing, I just wrote it.

And yes, it still boils down to O(n) time.
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mack Wilmot wrote: . . . There is such a thing, I just wrote it. . . .


That was a good explanation of why you find items in a linked list in linear time earlier, too.
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Mack Wilmot wrote: . . . There is such a thing, I just wrote it. . . .


That was a good explanation of why you find items in a linked list in linear time earlier, too.



Thank you.
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you all.

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
 
Mack Wilmot
Ranch Hand
Posts: 88
Linux Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You would need to ask the person that asked the question to qualify what they mean by insertion time.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would say that LinkedList.add(int, E) and LinkedList.remove(int) are both O(d), where d is the distance from whichever end of the list is closest. In general those are O(n), the length of the list - unless you have a use case where you stay close to the ends.

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.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!