298 Intermediate C Programming
18.4 Searching a Linked List
The next function searches a linked list for the node whose value is the same as the
given argument.
Node * List_search(Node * head, int val)
1
{2
Node * ptr = head;3
while (ptr != NULL)4
{5
if ((ptr -> value) == val)6
{7
return ptr;8
}9
ptr = ptr -> next;10
}11
return ptr; // must be NULL12
}13
The function starts from the first node in the list. Before the function does anything, the
function has to check whether the list is empty. This is the purpose of line 4. If the value is
found at line 6, then the function returns the node. Otherwise, ptr moves to the next node.
If multiple nodes store the value matching the argument val, then this function returns
the first match. Line 12 returns ptr and it should always be NULL.Ifptr is not NULL,then
the while loop should continue. This example shows the importance of initializing next to
NULL to indicate the end of the list.
18.5 Deleting from a Linked List
The List delete function deletes the Node object whose value isthesameasthesecond
argument. Suppose the program needs to delete the second Node object in the list. After
calling List
delete, the first and the third nodes must remain in the linked list. The first
node’s next must point to the third node (now second). This ensures that the node is still
reachable from the head. Fig. 18.6 shows the new list and Fig. 18.7 to Fig. 18.10 show the
steps.
How do we implement List
delete? First, the function creates a new pointer p and
makes its value the same as head’s value. The list is accessible from the head. The function
has to keep head’s value, because if head’s value is changed, then we lose the entire list.
Node * List_delete(Node * head, int val)
1
{2
printf("delete%d
", val);3
Node*p=head;4
if (p == NULL) // empty list , do nothing5
{6
return p;7
}8
Linked Lists 299
Node * head = NULL;
head = List_insert(head, 917);
head = List_insert(head, -504);
head = List_insert(head, 326);
head = List_delete(head, -504);
symbol address value address value
head 200 83000 83001 326
83000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
326
FIGURE 18.6: Delete the node whose value is −504.
Node * p;
p = head;
symbol address value
address value
p 201 83000
83001 326
head 200 83000
83000 75000
75001 -504
75000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
-504
326
p
FIGURE 18.7: To delete a list node, first create a pointer p that points to the same
memory address as head.
9
// delete the first node (i.e., head node)?10
if ((p -> value) == val)11
{12
p = p -> next;13
free (head);14
return p;15
}16
17
// not deleting the first node18
Node*q=p->next;19
while ((q != NULL) && ((q -> value) != val))20
300 Intermediate C Programming
Node * p;
p = head;
Node * q;
q = p -> next;
symbol
address
value
address
value
q 202 75000
83001 326
p 201 83000
83000 75000
head 200 83000
75001 -504
75000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
-504
326
p
q
FIGURE 18.8: The function creates another pointer q.Itsvalueisthesameasp->next.
Node * p;
p = head;
Node * q;
q = p -> next;
p -> next = q -> next;
symbol address value
address value
q 202 75000
83001 326
p 201 83000
83000 60000
head 200 83000
75001 -504
75000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
-504
326
p
q
FIGURE 18.9: Modify p->next to bypass the node that is about to be deleted.
{
21
// check whether q is NULL before checking q -> value22
p = p -> next;23
q = q -> next;24
}25
if (q != NULL)26
{27
// delete the node whose value is val28
p -> next = q -> next;29
free (q);30
}31
Linked Lists 301
Node * p;
p = head;
Node * q;
q = p -> next;
p -> next = q -> next;
free (q);
symbol
address
value
address value
q202-
83001 326
p 201 83000
83000 60000
head 200 83000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
326
p
q
FIGURE 18.10: Release the memory pointed to by q.
return head;
32
}33
If head’s value (head -> value)isthesameasval, the first node is deleted. This is
achieved by storing head -> next in p at line 14. In this case, the function returns p as the
new head of the list. It is possible that p is set to NULL. This occurs when the list has only
one node and its value is the same as val. After deleting this node, the list is empty.
If head’s value is different from val, then the node to be deleted, if it exists, is after
head somewhere. When we find this node, we must make the previous node point to the
next node. As we will see below, the List
delete function uses another pointer q for this
purpose, and its value is p -> next.
Lines 20 to 25 find the node whose value is val.Thewhile loop stops in one of two
conditions: either q is NULL or q -> value is val. To avoid a memory error, the function
must check the first condition before checking the second condition. If q is NULL,then
the second condition is not checked. When q is NULL, the first part of the logical AND
(&&) expression is false and the entire logical AND expression is false. The program does
check whether q -> value is the same as val. This is called short-circuit evaluation and
C programs often rely on it. Lines 23 and 24 move p and q to their next nodes. Since q is
initialized to p -> next, the code inside the entire block always keeps q as p -> next.
What does it means when q is NULL at line 26? It means that no node in the linked
list stores val, and therefore no node needs to be deleted. If q is not NULL, then a node
whose value is val has been located. The function changes p -> next to q -> next.This
bypasses the node q that is about to be deleted. In this method, q isthenodetobedeleted
and p is the node before q. It is necessary to keep p because it is not possible to go backward
from q to p. The purpose of keeping both p and q is that we cannot go back one node from
q without p. The function then releases the memory pointed to by q. The value stored in q
is
still a memory address but that address is no longer valid. Using q’s value after free(q)
will cause segmentation fault. It is also possible to implement List
delete with recursion.
Below is a sample implementation. Lines 19 to 31 above can be replaced by a single line as
shown below.
Node * List_delete2(Node * head, int val)
1
302 Intermediate C Programming
{
2
printf("delete%d
", val);3
if (head == NULL)4
{5
return NULL;6
}7
8
if ((head -> value) == val)9
{10
Node * p = head -> next;11
free (head);12
return p;13
}14
15
head -> next = List_delete2(head -> next, val);16
return head;17
}18
How does this work? The function checks whether the list is empty (line 4) and then
checks whether the first node is the node to be deleted (lines 9 to 14). How can line 16
in List
delete2 replace lines 19 to 31 in List delete? Line 16 calls List delete2 recur-
sively, passing head -> next. This means that every time List
delete2 is called, one node
(the head) is excluded. Thus, the list being considered shrinks in every recursive call, and
eventually reaches NULL (checked at line 4) if val is not stored in the list. This ensures that
List
delete2 terminates.
This function has three places that call return. Line 6 returns when the list is empty
and nothing can be deleted. Line 13 returns the node after head because head is the node
to be deleted. Line 17 returns head if head is not the node to be deleted.
Consider the scenario when val is not stored in any node. Line 16 assigns head -> next
to what is returned by calling List
delete2(head -> next, val).Sinceval is not
in the list, the condition at line 9 is never true in any of the recursive calls. The
function will always return the first argument. This means that line 16 will reduce to
head -> next = head -> next and the list remains unchanged.
Next consider the case when the list does contain a node whose value is val.Inthis
case, the condition at line 9 will become true in one recursive call. The function then
returns the node after head, skipping head. This is equivalent to line 15 in List
delete.
Thus, List
delete2 can delete the node whose value is val. List delete2 does not need
to use q because the call stack stores the value of each node (as head) as the function moves
forward along the list.
18.6 Printing a Linked List
List print is more straightforward than the previous functions because it does not need
to change the list. The function simply goes through the nodes one-by-one and prints the
values. The listing below gives two implementations: one iterative, and one recursive.
void List_print(Node * head)
1
{2
printf("nPrintthewholelist:
");3
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.