StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The classic example is the remove operation from a doubly linked versus singly linked list (not that we have much cause to worry about that much any more, but it illustrates the principal).</p> <p>In a doubly linked list (with a dummy node so that the list always has at least one node) you can remove a node with just a reference to that node:</p> <pre><code>node.Prev.Next = node.Next; node.Next.Prev = node.Prev; </code></pre> <p>Contrast this to the same operation in a singly linked list, which requires traversing the entire list.</p> <p>This illustrates the idea that algorithms almost always mirror the complexity of the data structures. This is even more true in database apps where complex database schemas create complex code and vice versa. I think most experienced programmers have uttered more curses regarding lousy data models than lousy code (although that also has to do with the degree of refactoring difficulty between data and code as well).</p> <p>From Wikipedia:</p> <p>Double-linked lists require more space per node (unless one uses xor-linking), and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both directions. In particular, one can insert or delete a node in a constant number of operations given only that node's address. To do the same in a singly-linked list, one must have the previous node's address. Some algorithms require access in both directions. On the other hand, they do not allow tail-sharing, and cannot be used as persistent data structures.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload