4 ms·

I've been a programmer for 15 years (web dev, self-taught) and I don't know what those are. I think a linked list is like a JSON object, right? Yes, I am a rea

I've been a programmer for 15 years (web dev, self-taught) and I don't know what those are. I think a linked list is like a JSON object, right? 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.

Igglyboo 12y ago
A linked list is an actual data structure, whereas JSON is just a format for storing data. The computer actually has to lay the json out in memory somehow. JSONs have keys that are strings so a hashmap or hashtable is probably more likely. http://en.wikipedia.org/wiki/Linked_list http://en.wikipedia.org/wiki/Linked_list http://en.wikipedia.org/wiki/Hash_table http://en.wikipedia.org/wiki/Hash_table
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.
- tel 12y ago
  A better reason why linked lists are better than arrays is that they have obvious, fast immutable APIs. Immutable data is not always a win, but sometimes it is.
  - deleted 12y ago
    [deleted]
- fredsted 12y ago
  Could you recommend any good books about that for a web developer?
tel 12y ago
Linked lists are another way of getting a lot of the functionality of arrays. While arrays are like a box of ordered things, linked lists are like a chain. 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.
Glide 12y ago
Probably not, you can have a career never using linked lists . The problem is that it's such a fundamental CS concept it's going to be hard to pass interviews without that knowledge if you were starting from a junior position. 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.
frik 12y ago
> the technologies I use don't have those paradigms. 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/Reference/Operators/Bitwise_Operators https://developer.mozilla.org/en/docs/Web/JavaScript/Referen... PHP: http://php.net/manual/en/language.operators.bitwise.php http://php.net/manual/en/language.operators.bitwise.php Python: https://wiki.python.org/moin/BitwiseOperators https://wiki.python.org/moin/BitwiseOperators Ruby: http://calleerlandsson.com/2014/02/06/rubys-bitwise-operators/ http://calleerlandsson.com/2014/02/06/rubys-bitwise-operator... Visual Basic: http://msdn.microsoft.com/en-us/library/wz3k228a.aspx 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 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.
- protonfish 12y ago
  Most of the optimizing I do has to do with DOM manipulation and replacing slow generic library functions with native and/or custom-written ones. I've got a lot of low-hanging fruit to pick before I get to things like bitwise operators. Most optimizations I've seen are very language-specific and it can be hard to guess what is faster. Which is why profiling and a tool like http://jsperf.com/ http://jsperf.com/ are critical. 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.
  - petercooper 12y ago
    You probably already know this, but your last sentence also has one minor advantage, in that you can use an otherwise pointless bitwise operation to strip off decimals, e.g. 100.919 | 0 .. => 100
- collyw 12y ago
  I actually fond the most efficient solution to a problem recently (generating massive numbers of DNA sequence combinations, and checking for the number of mismatches between them) came from using MySQL and bitwsie operators. I tried Python, it was at least an order of magnitude slower. I tried Java, but that ran out of memory surprisingly quickly. I might try it in C at some stage but that will involve a fair bit more time.
jwmerrill 12y ago
A linked list is a tool for making sure that your data is never in the cache when you want it to be that a lot of developers fetishize because lisp and because they're so easy to implement that every CS curriculum will make you implement one at some point. Just use (dynamically growable) arrays, like, almost always, or heaps or binary trees in special circumstances. 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 http://en.m.wikipedia.org/wiki/Dancing_Links Note, this is actually a circular, doubly linked list.

Igglyboo 12y ago

A linked list is an actual data structure, whereas JSON is just a format for storing data. The computer actually has to lay the json out in memory somehow. JSONs have keys that are strings so a hashmap or hashtable is probably more likely. http://en.wikipedia.org/wiki/Linked_list http://en.wikipedia.org/wiki/Linked_list http://en.wikipedia.org/wiki/Hash_table http://en.wikipedia.org/wiki/Hash_table

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.

tel 12y ago
A better reason why linked lists are better than arrays is that they have obvious, fast immutable APIs. Immutable data is not always a win, but sometimes it is.
- deleted 12y ago
  [deleted]
fredsted 12y ago
Could you recommend any good books about that for a web developer?

tel 12y ago

Linked lists are another way of getting a lot of the functionality of arrays. While arrays are like a box of ordered things, linked lists are like a chain. 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.

Glide 12y ago

Probably not, you can have a career never using linked lists . The problem is that it's such a fundamental CS concept it's going to be hard to pass interviews without that knowledge if you were starting from a junior position. 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.

frik 12y ago

> the technologies I use don't have those paradigms. 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/Reference/Operators/Bitwise_Operators https://developer.mozilla.org/en/docs/Web/JavaScript/Referen... PHP: http://php.net/manual/en/language.operators.bitwise.php http://php.net/manual/en/language.operators.bitwise.php Python: https://wiki.python.org/moin/BitwiseOperators https://wiki.python.org/moin/BitwiseOperators Ruby: http://calleerlandsson.com/2014/02/06/rubys-bitwise-operators/ http://calleerlandsson.com/2014/02/06/rubys-bitwise-operator... Visual Basic: http://msdn.microsoft.com/en-us/library/wz3k228a.aspx 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 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.

protonfish 12y ago
Most of the optimizing I do has to do with DOM manipulation and replacing slow generic library functions with native and/or custom-written ones. I've got a lot of low-hanging fruit to pick before I get to things like bitwise operators. Most optimizations I've seen are very language-specific and it can be hard to guess what is faster. Which is why profiling and a tool like http://jsperf.com/ http://jsperf.com/ are critical. 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.
- petercooper 12y ago
  You probably already know this, but your last sentence also has one minor advantage, in that you can use an otherwise pointless bitwise operation to strip off decimals, e.g. 100.919 | 0 .. => 100
collyw 12y ago
I actually fond the most efficient solution to a problem recently (generating massive numbers of DNA sequence combinations, and checking for the number of mismatches between them) came from using MySQL and bitwsie operators. I tried Python, it was at least an order of magnitude slower. I tried Java, but that ran out of memory surprisingly quickly. I might try it in C at some stage but that will involve a fair bit more time.

jwmerrill 12y ago

A linked list is a tool for making sure that your data is never in the cache when you want it to be that a lot of developers fetishize because lisp and because they're so easy to implement that every CS curriculum will make you implement one at some point. Just use (dynamically growable) arrays, like, almost always, or heaps or binary trees in special circumstances. 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 http://en.m.wikipedia.org/wiki/Dancing_Links Note, this is actually a circular, doubly linked list.