3 ms·
A linked list is a way to build a list out of nodes. Each node has a piece of data, and a pointer to the next node (or null if you've reached the end of the li
by btilly 16y ago
A linked list is a way to build a list out of nodes.
Each node has a piece of data, and a pointer to the next node (or null if you've reached the end of the list). In a doubly linked list the nodes also has a pointer to the previous node.
This structure lets you build a list of arbitrary length without having to know in advance how much memory to assign it. You can append and iterate over elements in O(1), however seeking to an individual list element is O(n).
Most dynamic languages do not make much use of linked lists since it is easier just to use dynamically resized arrays. Any time you fill it you allocate a new array that is, say, 20% bigger and move the data. These allow you to seek to any element (including the next one) in O(1) with better average performance than linked lists. They also let you append in amortized average O(1) cost. Meaning that when you average out the cost of n appends, the overhead is O(n). However that cost is born unfairly, most are cheap but very occasionally you need to allocate the next bigger array and move existing data. For many applications (eg building a web page) this is fine. But if you're working in real time code then amortized average O(1) is not the same as O(1), and you must use a linked list.
There, now you know what a linked list is.
- sudont 16y agoThank you! The why is very illuminating.