struct node {
int data;
/* ... */
struct node *next;
};
typedef struct node NODE;
Suppose that we have a singular list of NODE
or a circular list of NODE
. To remove a node from the list, we'd like to implement
following function:
/* Remove NPTR from the list pointed by HEAD, and return it. */
NODE *list_extract(NODE **head, NODE *nptr);
The node that we need to extract from the list is pointed by nptr
.
So we need to make sure that the next
field of the node
before nptr
should point the node after nptr
. One way to find
the previous node is to iterate all nodes from head
to find the node
whose next
field is the node pointed by nptr
:
NODE *before;
for (before = head; before != 0; before = before->next)
if (before->next == nptr)
break;
However, it may not be so efficient to traverse lots of node before
nptr
if the list is very very long. There is another way to extract
a node from a list without iterating the list to find the previous
node.
head nptr
[10] -> ... -> A:[12] -> B:[34] -> ...
Suppose we have a list like the above. head
and nptr
is the
pointer to the head of the node and the node that needs to be
extracted respectively. Let the node points by nptr
is node A, and
the next node of node A is node B. Node A
has an integral data, 12,
and node =B= has 34
.
Instead of finding the node before nptr
, we like to swap the
contents of the node A and node B. To do that, I'll introduce a
temporary node, T
, and copy the contents of node =A= into it.
head nptr
[10] -> ... -> A:[12] -> B:[34] -> ...
^
|
T:[12] -----+
Note that we copied every fields of node A
into node T
, so =next=
field of node T
also points the same node as node A
points. Then,
we copy all fields of node B into node A:
head nptr
[10] -> ... -> A:[34] -------------+
|
V
T:[12] -> B:[34] -> ...
Then, we copy all fields of node T
into node B
:
head nptr
[10] -> ... -> A:[34] -----------> ...
+----+
| |
V |
T:[12] -> B:[12] -+
Since we copyied next
field from node =T= to node B
, node =B=
turns to be a circular list of its own node, which we don't intent.
So set next
field of node B
to NULL
.
head nptr
[10] -> ... -> A:[34] -----------> ...
T:[12] -> B:[12] -|
Now the node that we wanted to extracted is copyied to node B, which
is accessible by next
field of node T. And the list has
successfully removed the contents of node pointed by nptr
.
However, when the target nptr
is the last node, we cannot use this
trick since there is no next
node. In that case, we use the well
known solution, to iterate all nodes to find the previous node.
The full
source code of list_extract()
is here:
NODE *
list_extract(NODE **head, NODE *nptr)
{
NODE t;
NODE *prev;
if (*head == nptr) {
if (nptr->next == NULL) {
*head = 0;
return nptr;
}
else {
*head = nptr->next;
nptr->next = NULL;
return nptr;
}
}
if (nptr->next) {
memcpy(&t, nptr, sizeof(t));
memcpy(nptr, nptr->next, sizeof(t));
memcpy(t.next, &t, sizeof(t));
t.next->next = 0;
return t.next;
}
for (prev = *head; prev != NULL; prev = prev->next) {
if (prev->next == nptr)
break;
}
if (!prev)
return 0;
prev->next = nptr->next;
nptr->next = 0;
return nptr;
}
And the time complexity will be:
\begin{eqnarray}
O(f(n)) & = & \left\{
\begin{array}{l l}
O(1) & \quad \text{ if $nptr$ is the head} \\
O(n - 1) & \quad \text{ if $nptr$ is the last} \\
O(1) & \quad \text{ the rest } \\
\end{array} \right. \\
&=& \frac{1}{n}O(1) + \frac{1}{n}O(n-1) + \frac{n - 2}{n}O(1) \\
&=& \frac{n - 1}{n}O(1) + \frac{1}{n}O(n) \\
&\cong& O(1) \quad \text{ if $n$ is relatively large }
\end{eqnarray}