3 ms·
Imagine an object: { data: stuff, next: more_stuff } `next` is a reference to the next object like this one in the list, and `data` is a reference t
by deckiedan 12y ago
Imagine an object:
{ data: stuff,
next: more_stuff }
`next` is a reference to the next object like this one in the list, and `data` is a reference to the actual object at this point in the list.
You've now got a close-enough idea about what a linked-list is.
You can also have dual-linked lists, where each object also has a `previous` pointer to the previous object in the list.
If you want, you could store the data directly in this object, rather than having a pointer out to the actual data (of course).
This kind of thing can be very useful for certain kinds of data manipulation, where the built-in lists aren't efficient enough - for whatever reason. Say the language you're using creates an entirely new list whenever you try to remove an element from the middle of a list - or when you need to be moving / removing elements all over the place.
The big downside of such a linked list is that you can't easily jump to a specific item number in the list. So jumping to item 200 means walking through the first 199 elements in the list to find it.
I've only had to implement a linked list once in a JS project, I don't remember the reason why. I think the algorithm just worked a lot more efficiently that way.
One reason a linked list could be useful in a javascript (or PHP, or whatever) language would be, for instance, if you had a game where when a player hit a block with a hammer, that block would bounce up and down, as would the two blocks on either side. If you store all the blocks in a regular list, then you need to know the index of the block in order to find the blocks on either side. In a linked list, you don't.
One of the original big advantages of linked lists is that you can have objects of variable size, and the list can grow and shrink without adjusting any of the previous elements. Opposed to this is an `array` (sometimes called a vector) which is a fixed size chunk of memory which is split up into identical sized parts. You can then jump to element 200 by looking at the starting position + 200 * the size of a single element.
This works pretty well, but if you want to add another 20 elements into the middle of the array, you need to allocate a new chunk of memory and move the whole lot into it, and deallocate the previous entire array. This is one of the reasons why strings are usually immutable in many languages. Strings are stored as arrays, not linked lists of letters.
I think it's worth learning about all this "Computer Science" stuff, even if you don't need it very often, as it means when you come across a new problem you have a much bigger mental toolkit from which to figure it out.