Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

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
28,204 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
28,204 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
28,204 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,580 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.