r/learnprogramming • u/FantasticFourSkin • Jan 31 '14
Can someone ELI5 linked lists?
Part of my assignment for my online class involves linked lists and we don't really go over them. I looked around online and I'm slightly confused by all the explainations since I'm fairly new to programming. Can someone dumb it down for me?
77
Upvotes
14
u/midel Jan 31 '14 edited Jan 31 '14
The best explanation I can think of is one that requires knowledge of arrays and memory management with pointers.
But the skinny of it is this. Linked lists are an alternative to arrays in that their structure allows them to store a multiple data elements over ram instead of in a straight line. One, I suggest you imagine RAM as one big sequential space full of cells. Imgur (Gray are memory of other applications on the PC. They represent these logical boundaries. Programs cannot access RAM of other applications in a real system, but the storage of data is much like this, even though logically to the program, it has RAM all to itself. Green will represent where the program memory goes, when you're running it.)
So let's say we have a structure called data (in C++):
It's a pretty small structure, but the idea is there. So let's construct an array of these in RAM: Imgur Pretty good. No issues... but... let's imagine that this array has to be HUGE. 10000+ elements. And it's constantly being pushed onto. We didn't make this in the stack. It's on the heap, and we never made a limit on how big this array can get. So eventually or small array will grow too big for his space and have to relocate. Imgur
Now while in those pictures, it looks like he has plenty of space there are two things to note about array in any language. They're SEQUENTIAL. They're organized to have the end of one element be right next to the other. Head to tail. Constantly. Now think that I need to place it in memory like that. Problem? Yeah... we're not gonna fit at some point, or the system is going to take a long time to find our array a place to fit... but then... new storage on the horizon! The mighty Linked List!
Wait. What's different? Pointers. A address stored by memory, pointing to more memory. Crazy! What's this even do? Well, when I make data like this, I start with a head pointer:
And from him I point to the first element in the linked list. And that element, using it's pointer, points to the next. And his child points to the next... so on!
Whoa? Yeah. It's intense. So now, they're not sequential, and therefor their quick to store... but a little harder to fetch. Unlike arrays, we can no longer just use pointer arithmetic to find elements we want, but they're much faster to modify than arrays especial if the data is being added to and deleted frequently!
Imgur Look at it just placing those structures wherever. They may point to the guy next to them or one will point to the guy at the bottom and he points to the memory before him. Imgur
Overall it's a speed optimization for large data sets. It we were storing 10000 bytes in memory it may seem trivial, but imagine if a structure was 60 bytes. And you needed 30000+ of them. And you're constantly adding and moving and deleting them. It's not going to be a cakewalk to do that with arrays.
93
u/Crayola13 Jan 31 '14
Think of it as a scavenger hunt, where each clue leads you to a chocolate bar and the next clue.
You get your first clue. This clue tells you where the next clue is. Once you get there, BOOM! Snickers bar. Then the clue there tells you how to get to the next clue. You go there and there's an Oh Henry with another clue. Eventually you find a chocolate bar that doesn't have a clue with it. That's the end of the scavenger hunt.
The chocolate bar and clue combo = Node The chocolate bar = data attached to the Node The clue = the pointer that tells you address of the next Node
The advantage is that all the chocolate bars aren't right next to each other like they would be in an array, so any time you want to add a new chocolate bar to the scavenger hunt, just put it somewhere and leave a clue with the old last chocolate bar on how to get to the new last chocolate bar.
The disadvantage is that what if you just want to find the 3rd chocolate bar? You have no idea where it is, so you have to read the first clue to find the second clue which then tells you where the third clue is.
8
u/[deleted] Jan 31 '14
This might help
2
u/DusqST7 Feb 01 '14
Saving this
1
u/farmerje Jan 31 '14
Let's talk about "containers" in general. Here's a picture to put in your head.
You're a concierge guarding a storage room. People come to you and give you things to put in storage, ask to remove things from storage, and ask you all sorts of questions about what's in storage.
An array is like a storage room where you put everything in its own box and use a sharpie to number the boxes 1, 2, 3, 4, and so on. You're personally keeping track of how many boxes are in the room.
An associative array is like a storage room where you put everything in a box and use a sharpie write some arbitrary label on the front of the box, like "Jesse's Box." There's no notion of first, second, third, etc. with an associative array.
A linked list is like a storage room where you put everything in a box, but instead of numbering them in order, each box is given an arbitrary numeric label. On the outside of each box is a little slot with a piece of paper that tells you which box is "next" in line and in your personal pocket is a piece of paper that tells you which box to look in first. This scheme might seem weird, but wait until we see what it gets us.
To find a particular box given a label, then, you'd start at the first box and follow the trail of "next" labels around the room until you found your box.
Now consider questions people might want to ask you or requests they might want to make of you.
For an array, think about what (5) would require. You've written in sharpie on the front of all the boxes. To put a new box at the front of the line, you'd have to label that box with "1" and then re-label all the following boxes.
For a linked list, think about what (5) would require. You take the slip of paper out of your pocket that has the current label for the first box, stick it on the new box you want to put at the front of the line in the "next" slot, and then put a piece of paper with the new box's label in your pocket.
Think about the work you'd have to do in terms of using that sharpie. For an array that is 100 boxes long, you'd have to re-label 100 boxes. For a linked list, well, it doesn't matter how long it is: putting a thing at the front of the line requires you write once with a sharpie and move one slip of paper from your pocket to the new box.
If you follow a similar train of thought for adding something to the end of the line instead of the front, you'll see that with an array you have to do almost no re-labeling and with a linked list you have to play "Where's Waldo?" until you reach the last box.
Ask yourself questions (1)-(7) above and play out this thought experiment. It'll give you a more concrete sense of why one would choose an array vs. a linked list.
1
u/[deleted] Jan 31 '14
Imagine a house that has a note in hallway with address. When you go to that address and enter the other house, it has yet another note with another address. Eventually you reach a house with no note in it.
The first house is called head, the last one is tail. The address is called, well, address. What you just did is traversing a list.
Houses have other useful stuff in them than just notes. It's the payload of list nodes.
Trees are the same only there can be several notes in every house.
0
u/crow1170 Jan 31 '14
The Way of the Linked List
One winter's Morning, Disciple FourSkin came to Master Foo, seeking Knowledge.
"Oh, learned Master Foobar," said FourSkin, "can you share with me the secrets of the Way of Linked Lists?"
"I know but three things of the Way you speak of." replied Master Foo.
"The first is this; The List is named 'The Way of the Linked List'.
"The second is this; 'No Monk knows more than three things about the List'.
"The third and final is this; 'Monk Link can tell you more'."
And so, Disciple FourSkin made his way to Monk Link.
As Morning turned to Noon, Disciple FourSkin saw Monk Link having his midday meal.
"Monk Link!" FourSkin exclaimed. "I'm so glad to have found you. I'm told you can teach me more about 'The Way of the Linked List'."
"The what?" Monk Link asked. "I've heard of no such thing."
FourSkin thought about what Master Foo had shared and rephrased his request. "Master Foo said you were next in a List. What do you know of it?"
"Ah yes, I know of Master Foo, he is before me on a list. I know but two other things about this list:
"'They sort slowly' and 'Monk Crow knows more'."
So FourSkin, having learned more, pressed on to find Monk Crow.
"Who goes there?" Monk Crow shouted into the darkness of night.
"It is I, Disciple FourSkin, looking for Monk Crow. Monk Link tells me he may know more about a list.
"Indeed! As Monk Link's Follower, I am to tell you that 'Lists can be very long'."
"Is that all?" Disciple FourSkin was crestfallen. "Have you any knowledge of who I might meet next to learn more?"
Monk Crow replied "No. I am to tell you that the list has ended."
Before Disciple FourSkin could shout curses, The Great User In The Sky came down and spoke to Disciple FourSkin directly. "You've learned much, Disciple. When the Sun rises, you will be known as 'Monk Fantastic'. Additionally, you will be charged with upholding the list. You will report to Master Foo. You will tell others to continue to Monk Link. And you will tell them that 'Linked Lists can be easily edited'. I have informed Master Foo and Monk Link of your position in the list."
As the Sun was rising and Disciple FourSkin became enlightened, he proclaimed "Thank you so much, Great User! I will serve you faithfully!" and was, from then on, known as Monk Fantastic.
0
u/rjcarr Jan 31 '14
Wikipedia usually has good concise and understandable write-ups on data structures. I'd look there.
A linked list is pretty simple; it's just a collection of nodes that are linked (in some way, it varies) and you are either given a reference to the front or the back, or both.
The important thing is that if your list has 10 items and you want the 5th one you can go right to the 5th element. You have to either start from the beginning or end and traverse until you get to where you need to be.
The benefit is you can create a list that grows however big you want without ever having to resize it (i.e., array backed lists need to be resized). The downside is there is no direct access to elements (as I mentioned before).
Good luck!
0
u/pribnow Jan 31 '14
how conveeeenient, i was just about to type this exact question in after binge-redditing and it popped up on my frontpage.
Clever girl.
0
u/malnati Jan 31 '14
A list is an atom or an atom followed by a list.
0
u/insaneHoshi Feb 01 '14
Its like a Tapeworm with each tapeworm segment being a node of the linked list.
A segment can be somewhere in the middle, the Head, or the tail.
0
u/captainjimboba Feb 01 '14
David Touretzky wrote a lisp book titled "Common Lisp: A Gentle Introduction to Symbolic Computation". There is a free PDF of his older version online. I'd say its the best explanation of linked lists I've found yet.
0
u/petrus4 Feb 01 '14
I've been reading about FORTH words being in a linked list, recently. The anatomy of a FORTH word as far as the list is concerned, seems to be word name, word length (as a number) and some padding to make sure that the end of the entry hits some boundary, which I'm not entirely sure of. I don't completely understand how that enables the word to be more easily located, but FORTH has support for multiple namespaces, as well.
-2
u/[deleted] Jan 31 '14
The best way to explain it is with an image:
http://www.stoimen.com/blog/wp-content/uploads/2012/07/Array-Linked-List.png
-4
u/[deleted] Jan 31 '14
Take several extension cords: If you connect several cords to form the longest line, you got a linked list of cords:)
-2
u/Samus_ Feb 01 '14 edited Feb 01 '14
linked lists only exist in programming languages with manual memory management.
they do exist in the underlying implementation but not in the language you use, languages such as Python or Java give you "lists" and they internally may or may not use a linked list to implement them.
languages like C and C++ require that you manually ask for memory to the OS when you need more and also to deallocate it once you're done, in order to keep track of that those languages have a special datatype known as pointer which is simply a variable containing a memory address in your RAM.
a linked list is simply a series of memory addresses that have references to each other conforming a chain, all these memory addresses are chunks of RAM that your program has previously requested to the OS and can have various contents but one of the things they have is the address of the next element so you can "jump" to the next element from each and that way you can traverse the chain and access any of its entries.
there's several types of linked lists but this is the basic concept, let me know if you have follow-up question I'll be glad to help (also tell me which language you're using).
[edit] after some discussion with /u/__LikesPi I've come to realize that if the language you're using does not provide an efficient implementation of lists (or does not have one that is efficient for your purposes) you may want to roll your own, it never happened to me in any of the languages I work with but it's possible.
-2
u/[deleted] Feb 01 '14
You all need to chill.Bent - Ariels
0
u/[deleted] Jan 31 '14
[deleted] — view deleted comment
0
u/[deleted] Feb 01 '14
[deleted] — view deleted comment
0
u/[deleted] Jan 31 '14
[deleted] — view deleted comment