Channels ▼
RSS

Design

Linked Lists Are, Like, So Last Century


A linked list is a dynamic data structure used to hold a linearly arranged (typically unordered) collection of data. The simplest variation will be just a "head" pointer referencing the first node in the list. Nodes are declared to contain a data portion and a "next" pointer to the succeeding node on the list. If the next pointer of a node is NULL (or some equivalent), that node is the last one on the list. Additional pointers can be included to facilitate faster access to specific points in the list; e.g., a "tail" pointer referencing the last node will speed up appending new nodes to the end of the list.

Why were linked lists developed? Won't an array work just as well or better? While a linked list doesn't support random access to any element on the list, it does allow for the insertion, deletion, or relocation of nodes in O(1) time. And there are no limits — other than the amount of memory available on the system — to the number of nodes that can be held in the list. So, with regards to access and data movement restrictions, arrays and linked lists would appear to be complementary. Programmers have learned to use whichever data structure best fits the algorithmic situation they are coding.

Now that we've entered the parallel programming epoch, do linked lists still have a place? Dan Grossman of The University of Washington says, "No." I first heard of this radical idea from a colleague that had done a presentation with Prof. Grossman at a SIGCSE conference. The claim is that a tree can be used anywhere that you might want to use a linked list. (In my visually oriented mind, I see an animated linked list and tree singing "Anything You Can Do" from Annie Get Your Gun. I doubt if either data structure can bake a pie, either.) Is Dr. Grossman's idea heretical or forward-looking? Let me try to convince you of the latter.

A linked list is a sequential data structure that is very well-suited for sequential processing. A tree is the epitome of fork-join parallelism, as I've been expounding throughout my previous three posts. As with a linked list, a tree can dynamically expand and contract. The time needed to add a new leaf node might not be constant, but it can be O(log n) for a well-organized tree, which is much better than the O(n) needed for two pointers to chase each other to the end of a list without a tail pointer. What about some of the other operations for which you might use a linked list? Can these be emulated by a tree, especially in parallel? Here are some operations on a linked list and how they can be "simulated" by a tree.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video