Yes, I am a real developer but the technologies I use don't have those paradigms. I doubt it this is good or bad, just different.
Yes, I am a real developer but the technologies I use don't have those paradigms. I doubt it this is good or bad, just different.
{ 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.
Here's a model of a linked list. We start with an empty list represented by an empty array.
[]
In normal arrays we'd add a number by putting it into the array, like [1], but we'll do something a little weirder: [1, []]
we build a new array which contains one value and the empty array. We add new elements in the same way []
[1, []]
[2, [1, []]]
[3, [2, [1, []]]]
The final one there is a bit like the array [3,2,1], but seems to have a lot more ceremony. In any case, the values above model linked lists.Why would you use such a thing?
Well, when you want to push a new value on to an array you may find (internally) that the array you have so far is too small. To fix this, you build a new, larger array and move all of the old elements to the new array plus the one new thing you've added. This can be expensive.
With linked lists, adding a new element is always the exact same process. It is in this way faster and simpler.
Of course, the downside of linked lists is that there is more overhead to, say, read the 10th element. In an array you can just do a[10], but in an linked list you must do a[0][0][0][0][0][0][0][0][0][1]. Obviously this involves much greater overhead.
Linked lists are closely related to infinite streams, however. Sometimes they better model what you actually want to talk about—the idea of having a value "now" and some more values "in the future". They also are much more naturally implemented immutably and have a much more natural sense of a fold or reduction.
So, as with all data structures, there's a tradeoff.
Your language most certainly has a syntax for bitwise operators. If you want to optimize (speed up) your code, knowledge like that would help you.
Node/Javascript: https://developer.mozilla.org/en/docs/Web/JavaScript/Referen...
PHP: http://php.net/manual/en/language.operators.bitwise.php
Python: https://wiki.python.org/moin/BitwiseOperators
Ruby: http://calleerlandsson.com/2014/02/06/rubys-bitwise-operator...
Visual Basic: http://msdn.microsoft.com/en-us/library/wz3k228a.aspx
A linked list is a kind of (abstract) data structure (http://en.wikipedia.org/wiki/Linked_list). If you come in touch with a static typed language (C, C++, C#, Java) such knowledge is essential. In languages like JavaScript and PHP you usually just use an object or an array. You can think of an linked list as an array of objects.
By the way, from what I've read bitwise operators aren't very efficient in JavaScript because of the overhead of conversion from generic duck-typing to binary.
JSONs have keys that are strings so a hashmap or hashtable is probably more likely.
Okay, now that I've got that out of my system, I'll try to contribute something positive. Linked lists are useful to understand because they're very similar to, but less complex than, a common representation of trees and graphs. In a tree or graph, each node can have several children instead of just one.
There are also some special algorithms that make use of the ability to grow or shrink a linked list in the middle without copying the whole tail [1]. The thing that makes this more rarely useful than you might think is that random access to the middle is O(n), so you have to be moving around in order adding/deleting things.
[1] Dancing Links: http://en.m.wikipedia.org/wiki/Dancing_Links
Note, this is actually a circular, doubly linked list.
To me it's not a paradigm. It's how data is stored and represented in memory. Where such issues become problems in larger projects is when you have a lead that doesn't know what B-trees are and they need to optimize database access. Or that person is loud and influential and derails every technical conversation because it's way over their head.