StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The textbook is wrong. The first member of a list has no usable "previous" pointer, so additional code is needed to find and unlink the element if it happens to be the first in the chain (typically 30 % of the elements are the head of their chain, if N=M, (when mapping N items into M slots; each slot having a separate chain.))</p> <p>EDIT:</p> <p>A better way then using a backlink, is to use a <strong>pointer</strong> to the link that points to us (typically the ->next link of the previous node in the list)</p> <pre><code>struct node { struct node **pppar; struct node *nxt; ... } </code></pre> <p>deletion then becomes:</p> <pre><code>*(p->pppar) = p->nxt; </code></pre> <p>And a nice feature of this method is that it works equally well for the first node on the chain (whose pppar pointer points to some pointer that is <em>not</em> part of a node.</p> <p>UPDATE 2011-11-11</p> <p>Because people fail to see my point, I'll try to illustrate. As an example there is a hashtable <code>table</code> (basically an array of pointers) and a buch of nodes <code>one</code>, <code>two</code>, <code>three</code> one of which has to be deleted.</p> <pre><code> struct node *table[123]; struct node *one, *two,*three; /* Initial situation: the chain {one,two,three} ** is located at slot#31 of the array */ table[31] = one, one->next = two , two-next = three, three->next = NULL; one->prev = NULL, two->prev = one, three->prev = two; /* How to delete element one :*/ if (one->prev == NULL) { table[31] = one->next; } else { one->prev->next = one->next } if (one->next) { one->next->prev = one->prev; } </code></pre> <p>Now it is obvious that the obove code is O(1), but there is something nasty: it still needs <code>array</code>, and the index <code>31</code>, so in <em>most</em> cases a node is "self contained", and a pointer to a node is sufficient to delete it from its chain, <strong>except</strong> when it happens to be the first node in its chain; additional information will then be needed to find <code>table</code> and <code>31</code>.</p> <p>Next, consider the equivalent structure with a pointer-to-pointer as a backlink.</p> <pre><code> struct node { struct node *next; struct node **ppp; char payload[43]; }; struct node *table[123]; struct node *one, *two,*three; /* Initial situation: the chain {one,two,three} ** is located at slot#31 of the array */ table[31] = one, one-next = two , two-next = three, three->next = NULL; one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next; /* How to delete element one */ *(one->ppp) = one->next; if (one->next) one->next->ppp = one->ppp; </code></pre> <p>Note: no special cases, and no need to know the parent table. (consider the case where there is more than one hashtable, but with the same nodetypes: the delete operation would still need to know <em>from which table</em> the node should be removed). </p> <p>Often, in the {prev,next} scenario, the special cases are avoided by adding a dummy node at the start of the double linked list; But that needs to be allocated and initialised, too.</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