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 trial

Computer Science Introduction to Data Structures Building a Linked List Removing a Node

I 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
alastair cooper
30,617 Points

If 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.

Thank you, so inserting operation takes constant time, traversing the list takes linear time

alastair cooper
alastair cooper
30,617 Points

Although 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
alastair cooper
30,617 Points

Hi

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

Thank 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
Mason Millsap
1,581 Points

One 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.