Monday, May 16, 2011

The double-linked list

Here's a concept that's been around in computer programming for as long as I can remember. Assume you have a big list of things (names, whatever) and each item in the list "knows" the item that comes before it, and the item that comes after it.

In other words, the double-linked list. You might use a double-linked list in a variety of applications. Typically, a double-linked list is used in a "stack" operation - because the double-links make it very easy to navigate forward in the list, and just as easy to move backward. Examples include the "Undo/Redo" actions in a word processor, or the "Back/Forward" buttons in a web browser.

This has been a part of computer programming curriculum for decades, but it was a patentable method in 2002 (awarded 2006).

Patent 7,028,023 describes a method where a "list is provided with auxiliary pointers for traversing the list in different sequences. One or more auxiliary pointers enable a fast, sequential traversal of the list with a minimum of computational time. Such lists may be used in any application where lists may be reordered for various purposes."

A more visual explanation of the double-linked list at wikipedia.

I worked with double-linked lists when I worked as a student intern at a geographics company, in 1994. I didn't even a computer programming student (I was in physics, learned programming "on the side") but it was still something easy enough to understand without an extensive programming background.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.