1. Linked List example:
Here, we will discuss deleting an element with a specific value from a linked list.
Here are some constraints for our example:
1. The list holds char's.
2. Deletion can occur anywhere in the list.
3. The delete operation will not return the element that we delete, it only need remove it from the list.
Now, recall the basic structure of a singly-linked list:
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
In other words, there is a node for each element, where nodes consist of a part in which the element is stored and a link to the next node. The last node links to nothing (i.e., there are no nodes after it). Also, there is a link to the beginning of the list.
What do these links correspond to in C++?
Answer: Pointers!
We'll consider our elements and nodes to have the following types:
typedef char ItemType;
class Node {
public:
...
ItemType getData();
Node *getNext();
void setNext(Node *);
private:
ItemType data;
Node *next; // pointer to node after me
};
And, the actual linked list will be a type called List:
class List {
public:
...
bool search(ItemType);
private:
Node *link; // pointer to beginning (1st node) of linked list
};
When the list is empty, what value will the pointer to the beginning have?
Answer: There are no nodes to point to, so it will be NULL!
Finally, if we want an instance of the List class, we can create one as:
List list;
2. Different cases:
There are a few steps to deleting a specific element from the list:
1. Find the node with the element (if it exists).
2. Remove that node.
3. Reconnect the linked list.
4. Update the link to the beginning (if necessary).
The order in which we perform these steps will depend on how we implement the deletion operation.
Note: For simplicity, if there are two elements with the value we want, we'll just remove the first one.
Finding the node in question is a matter of traversing the list and looking at each node's element.
Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:
* Removing a node from the beginning.
* Removing a node from the middle.
* Removing a node from the end.
Removing from the beginning
When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node. For example, removing node with a:
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
However, we must fix the pointer to the beginning of the list:
link
|
+-------------+
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
Removing from the middle
Removing a node from the middle requires that the preceding node skips over the node being removed. For example, removing the node with b:
link
|
v
--------- --------- ---------
| a | --+--+ | b | --+---> | c | 0 |
--------- | --------- ---------
| ^
+----------------+
This means that we need some way to refer to the node before the one we want to remove.
Removing from the end
Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it). For example, removing the node with c:
link
|
v
--------- --------- ---------
| a | --+---> | b | 0 | | c | 0 |
--------- --------- ---------
Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does."
IMPORTANT NOTE: When there is only one node, and it is the one to be removed, are we in the case of removing at the beginning or end?! We should make sure that one of these cases handles removing this single node ELSE we should create a new case.
What we've learned from these pictures is that when we find the node we want to remove, we need some kind of reference to the node preceding it OR some way to backtrack to that node.
Deletion member functions
We'll write List member functions to delete an element from a list in 2 ways: iteratively and recursively (which will require a helper function):
class List {
public:
...
bool deleteIter(ItemType);
bool deleteRecur(ItemType);
private:
Node *link;
Node *delRec(Node *, ItemType); // helper function
};
The deletion functions will return a bool representing whether the element was deleted (i.e., was present in the list).
3. Iterative implementation:
Let's look at how to delete iteratively (i.e., with a loop) via a member function:
bool deleteIter(ItemType);
We'll need to be able to change the pointer to the list, link, in the case that the first node in the list is removed. Since deleteIter() is a member function of List, and link is one of the data member of that class, we can access it in deleteIter() when necessary.
We will iterate (i.e., loop) through the list to find the item to delete. It's easy to see how to start a pointer at the beginning and move it from one node to the next:
--------- --------- ---------
| x | --+---> | y | --+---> | z | --+--->
--------- --------- ---------
^
|
currP
In other words:
* Start at the beginning:
currP = link
* Advance to the next node when necessary:
currP = currP->getNext()
by calling the member function to get the next node.
* Stop when there are no more nodes, i.e., make sure that:
currP != NULL
It's easy to combine these into a for loop:
for (currP = link; currP != NULL; currP = currP->getNext()) {
...
However, when we find the one to remove, we'll also need a pointer to the previous node:
--------- --------- ---------
| x | --+---> | y | --+---> | z | --+--->
--------- --------- ---------
^ ^
| |
prevP currP
Thus, we also need to maintain a previous pointer at each step of the loop:
for (currP = link;
currP != NULL;
prevP = currP, currP = currP->getNext()) {
(Notice that there are 2 increments separated by a comma.)
To complete the function, we'll have to:
* Have some way to indicate when there is no previous node.
Remember that removing the first node is a special case because...
o It requires no relinking of nodes.
o We have to update the pointer to the beginning of the list.
* Relink the list (i.e., skip over the node to be deleted).
* Remove the node.
One implementation of this function might be:
bool List::deleteIter(ItemType item)
{
Node *currP, *prevP;
/* For 1st node, indicate there is no previous. */
prevP = NULL;
/*
* Visit each node, maintaining a pointer to
* the previous node we just visited.
*/
for (currP = link;
currP != NULL;
prevP = currP, currP = currP->getNext()) {
if (currP->getData() == item) { /* Found it. */
if (prevP == NULL) {
/* Fix beginning pointer. */
link = currP->getNext();
} else {
/*
* Fix previous node's next to
* skip over the removed node.
*/
prevP->setNext(currP->getNext());
}
delete currP; /* Deallocate the node. */
return true; /* Done searching. */
}
}
return false; /* Not in the list. */
}
We do handle the situation of removing the first node, i.e., when there is no previous. See how we use a previous pointer value of NULL to indicate this and do the right thing.
Does this function handle deletions from empty lists correctly?
Finally, this function can be called as:
list.deleteIter(item);
4. Recursive implementation:
Another way to implement a deletion function is with recursion (since recursion gives us backtracking).
The recursive version will need to receive a pointer to the node it is examining, and thus, the recursion will have to be done by a helper function:
Node *delRec(Node *, ItemType);
which will be private in class List. Users of the list will call the public member function deleteRecur(), which will mainly just call delRec() to do all the work and will return a true/false value depending on whether the item we want to delete is in the list or not.
bool deleteRecur(ItemType);
Remember that for a recursive function (i.e., a function that calls itself), we need to decide:
* Base case(s): when to stop recursing.
* Recursive part(s): how function will call itself to solve the problem.
The base cases are fairly easy, since we need to stop recursing when:
* We find the matching value.
* We search the whole list and don't find a matching value.
To determine what should be the recursive part of the function, we should consider 2 tasks required of this function:
1. Finding the one to remove.
How will we search the list for the element? Well, the list will be passed as a pointer to a node (recall the prototype--here we've named the pointer currP):
Node *delRec(Node *currP, ItemType item);
So, if we decide that the node pointed to by currP is not the right node, then we just recurse to examine the next node:
delRec(currP->getNext(), item);
and so on, until all nodes have been examined.
2. Relink the list.
When we remove a node, the previous node has to skip over the removed node. A way to achieve this with recursion is through pointer reassignment.
Consider the following, where the current call to delRec() gets a pointer to the node with x:
1. delRec(pointer-to-node-with-x, 'y');
--------- --------- ---------
| x | --+---> | y | --+---> | z | --+--->
--------- --------- ---------
^
|
currP (in 1.)
Since x is NOT the thing to be removed, another recursive call is made. This next recursive call is going to access the node with y:
1. delRec(pointer-to-node-with-x, 'y');
2. delRec(pointer-to-node-with-y, 'y');
--------- --------- ---------
| x | --+---> | y | --+---> | z | --+--->
--------- --------- ---------
^ ^
| |
currP (in 1.) currP (in 2.)
Remember that when the recursive call on the node with y (call 2) is done, we'll be back to the call on the node with x (i.e., we backtrack to call 1):
1. delRec(pointer-to-node-with-x, 'y');
2. call 2 done, back to 1.
--------- --------- ---------
| x | --+---> | y | --+---> | z | --+--->
--------- --------- ---------
^
|
currP (in 1.)
Now since y is the thing to be removed...
If there was some way that this function call on the node with y (call 2) could tell us the node with y was removed and that it pointed to the node with z, then we could fix the node with x, having it skip over y (to z).
Well, it can!! Remember that the recursive function returns a pointer to a node!
Thus, what we'll do is have each recursive call return a pointer to the node to which the previous node should point. Thus, when the node is left alone, we just return a pointer to itself (i.e., "Don't skip over me!"). When the node is removed, we return a pointer to the next node (i.e., "Skip over me!").
So, we use the return value of the recursive call as:
currP->setNext(delRec(currP->getNext(), item));
When the next node is not removed, this pointer reassignment is equivalent to if we had done:
currP->next = currP->next;
i.e., no change. However, if the next node is the one to be removed, it would be like we had done:
currP->next = currP->next->next;
and thus, skips over the removed node.
Note: This also works for removing the first node (i.e., it fixes the pointer to the beginning of the list), if the initial call to the function is:
link = delRec(link, item);
Again, to complete the function, all the things we'll have to do are:
* Determine when we hit the end of the list.
* Determine when we've found the right node.
* Deallocate the correct node.
* Return what the link in the previous call should point to.
Finally, our functions look like:
bool List::deleteRecur(ItemType item)
{
if (!search(item))
return false;
link = delRec(link, item);
return true;
}
Node *List::delRec(Node *currP, ItemType item)
{
/* See if we are at end of list. */
if (currP == NULL)
return NULL;
/*
* Check to see if current node is one
* to be deleted.
*/
if (currP->getData() == item) {
Node *tempNextP;
/* Save the next pointer in the node. */
tempNextP = currP->getNext();
/* Deallocate the node. */
delete currP;
/*
* Return the NEW pointer to where we
* were called from. I.e., the pointer
* the previous call will use to "skip
* over" the removed node.
*/
return tempNextP;
}
/*
* Check the rest of the list, fixing the next
* pointer in case the next node is the one
* removed.
*/
currP->setNext(delRec(currP->getNext(), item));
/*
* Return the pointer to where we were called
* from. Since we did not remove this node it
* will be the same.
*/
return currP;
}
This recursive implementation even works when we try to delete from an empty list (i.e., there are no nodes).
A call to delete recursively will thus look like:
list.deleteRecur(item);
BU CAS CS - Deleting from a Linked List
This page created by Jisook Youn
Material adapted for C++ from Deleting from a Linked List (C version by Robert I. Pitts
No comments:
Post a Comment