This week's book giveaway is in the Cloud/Virtualization forum.
We're giving away four copies of Learning OpenStack Networking: Build a solid foundation in virtual networking technologies for OpenStack-based clouds and have James Denton on-line!
See this thread for details.
Win a copy of Learning OpenStack Networking: Build a solid foundation in virtual networking technologies for OpenStack-based clouds this week in the Cloud/Virtualization forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

A time complexity question  RSS feed

 
Ranch Hand
Posts: 69
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What's the time complexity to remove an element from a sorted and unsorted linked list? I have heard different answers. I mean for remove, do we need to concern with the "find" part? Because in an unsorted linked list, you need to find it first, which takes O(n), though the remove action itself just takes 1. So do we say N or 1? Sorted and unsorted have the same time complexity I think. Insert also has to do with "find".

Thanks!
 
Java Cowboy
Sheriff
Posts: 16084
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In a linked list, the elements are only accessible by walking through the list (i.e. no random-access by index as in an array). It doesn't matter if the list is sorted or not, you'll have to walk the list until you find the element to remove, which takes O(N).
 
Marshal
Posts: 60105
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In an ArrayList, however, it would be O(logn) if it is already sorted and O(n) if not sorted. If you already know the index, it would be constant time. To obtain the logarithmic time you would need a binary search to find the element to remove.
 
author and iconoclast
Sheriff
Posts: 24220
40
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:In an ArrayList, however, it would be O(logn) if it is already sorted and O(n) if not sorted. If you already know the index, it would be constant time. To obtain the logarithmic time you would need a binary search to find the element to remove.



Actually, no. Removing an element from an ordered array or ArrayList takes linear time, because after you remove the element, you then have to move an average of N/2 elements down to fill the "hole". If order doesn't matter, then you can just move the last element, and that does take constant time; of course, then you might as well have been using a Set rather than a List in the first place.

Removing from a linked list does, indeed, always take constant time.
 
Cheryl Scodario
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ernest Friedman-Hill wrote:
Removing from a linked list does, indeed, always take constant time.



Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24220
40
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Cheryl Scodario wrote:

Ernest Friedman-Hill wrote:
Removing from a linked list does, indeed, always take constant time.



Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.



Finding an object takes linear time; subsequently removing it takes constant time. For an array, finding takes linear time for unsorted, and logarithmic time for a sorted list; and removing takes linear time.

Removing does not always imply finding. For example, consider removing the first element of a list. For a linked list, it's done in constant time, and for an array or ArrayList, it takes linear time.
 
Campbell Ritchie
Marshal
Posts: 60105
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, you are correct about linear time, and I was mistaken. Sorry.
 
Cheryl Scodario
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ernest Friedman-Hill wrote:

Cheryl Scodario wrote:

Ernest Friedman-Hill wrote:
Removing from a linked list does, indeed, always take constant time.



Hi Ernest, why removing from a linked list always takes constant time? Because I kinda agree with Jesper that it will have to find the element to remove first, then actually do the remove action.



Finding an object takes linear time; subsequently removing it takes constant time. For an array, finding takes linear time for unsorted, and logarithmic time for a sorted list; and removing takes linear time.

Removing does not always imply finding. For example, consider removing the first element of a list. For a linked list, it's done in constant time, and for an array or ArrayList, it takes linear time.



I see...How about insert in a sorted list? I always think of remove and insert very similar. But is insert implying find for sure? Because you need to find the right position to insert it. Then it would be N, linear time?
 
lowercase baba
Bartender
Posts: 12627
50
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not if you are inserting in the first position.
 
Cheryl Scodario
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:Not if you are inserting in the first position.



I am not talking about any special(best) case. So let's just say sorted list: insert and find (average case).
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24220
40
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For sorted lists, for find/insert, both linked lists and array(list)s will give linear performance. For the linked list, the time is dominated by the find; for the array(list)s, it's dominated by the insert.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!