Welcome to the Treehouse Community
Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.
Start your free trialMoatazBellah Ghobashy
9,518 PointsI feel confused a little bit about linked list
I noticed all the functions we have created takes linear time O(n) (except add function), so why anyone interested in building a LinkedList data structure?
4 Answers
alastair cooper
30,617 PointsIf you insert by prepending or appending (adding to the start or finish) it is constant time as you only have to change references on 2 nodes. But if you insert in the middle of the list or delete from the middle, then although the actual operation to change references is still in constant time, the only way to get to the right node is to iterate through (traverse the list), which at worst case is the whole list, so that is why it is linear time.
alastair cooper
30,617 PointsAlthough it is more expensive computationally, sometimes it is the best solution to manage the data you have to manage.
In the same way that a plane takes more fuel to use than a car, but sometimes the journey you are taking requires the use of a plane. If for instance you are traversing a set of islands, and taking the car would involve 10 separate ferry journeys as well as the driving, a plane would end up as the most efficient form of travel. In code that analogy might translate as using the less efficient LinkedList, instead of using reference arrays or some other way of maintaining the links between the data in the more efficient Lists.
Hope this helps
alastair cooper
30,617 PointsHi
I re-read my answer and I guess it doesn't help much.
Below I have pasted the transcript from Pasan's video with the relevant statements which answer your question. This might be a better answer.
Arrays are particularly good at accessing and reading values which happens in constant time. But arrays are pretty bad at inserting and deleting, both of which run in linear time. Linked lists, on the hand, are somewhat better at this, although there are some caveats. And if we're trying to solve a problem that involves far more inserts and deletes than accessing, a linked list can be a better tool than an array.
Hope this helps more than the last answer did
MoatazBellah Ghobashy
9,518 PointsThank you for your help:), but the thing that really confused me is, the insterting and deleting function we created takes also linear time
Mason Millsap
1,581 PointsOne benefit of inserting and deleting with Linked Lists is that the Linked Lists are not stored continuously in memory, like Arrays -- Arrays need to be resized after enough insertions and deletions whereas Linked Lists do not.
MoatazBellah Ghobashy
9,518 PointsMoatazBellah Ghobashy
9,518 PointsThank you, so inserting operation takes constant time, traversing the list takes linear time