(Doubly Linked List) Maintaining two links in each node (previous node and next
ID: 3686666 • Letter: #
Question
(Doubly Linked List) Maintaining two links in each node (previous node and next node) makes some operations simplier to implement.
1) We don't need the second Search function anymore, shown below (i.e., we can use the first Search function that takes two parameters). Why?
/* Search for given value in the listed list pointed to by firstNodePtr,
* return the matching node's address.
@param firstNodePtr
@param value
@postcondition: if the value is found in the linked list,
the node's address will be returned, and
@return value: same as Search...
*/
IntNodeType * Search (IntNodeType * firstNodePtr, int value)
{
...
}
/* Search for given value in the listed list pointed to by firstNodePtr,
* return the matching node's address, and
* set its previous node's address in prevNode parameter
@param firstNodePtr
@param value
@param prevNode: set to the previous node
@postcondition: if the value is found in the linked list,
the node's address will be returned, and
@return value: same as Search...
*/
IntNodeType * Search (IntNodeType * firstNodePtr, int value, IntNodeType * & prevNode)
{
...
}
2) How would you modify the following functions (considering Search does not provide the previous node address)?
void InsertBeforeValue (IntNodeType * & head, int value, int beforeValue)
{
IntNodeType * cur, * prev, * newNode;
newNode = new IntNodeType (value,NULL);
cur = Search (head, beforeValue, prev);
assert (cur!=NULL);
if (prev==NULL) {
assert (cur==head);
//insert the new node before the head
newNode->next = head;
head = newNode;
}
else {
prev->next = newNode;
newNode->next = cur;
}
}
/* Delete the node storing the given value from the linked list
1. Find the value in the list (i.e., find the pointer that points to the node),
and also remembers the address of its previous node
2. If the node to be removed is not in the header, skip it in the list
(assign its next node's address to its prev node's next)
otherwise set header to its next node's address
3. delete the node (to free up heap storage)
@param firstPtr: if the value is stored in the head, then firstPtr will be updated
@param value
@return true if the value is removed; false if the value is not found
*/
bool Delete (IntNodeType * & firstPtr, int value)
{
IntNodeType * prev, * cur;
cur = Search (firstPtr, value, prev);
if (cur==NULL)
return false;
else {
// remove cur node from the linked list
if (prev!=NULL)
{ //not the first one
prev->next = cur->next; //bypass the cur node
}
else //cur is the first node
firstPtr = cur->next; //update the head pointer
delete cur; //deallocate the node itself
return true;
}
}
Explanation / Answer
The third question is not clear. WHat are we expected to do there? Please explain. I am posting the answers for the first two questions.
Q1.
In the second search function, we are providing the argument for previous node as well. But there is no need for that. For search, we need only the start node, and we can go ahead searching
it. The need for previous node is a waste. :)
Q2.
void InsertBeforeValue (IntNodeType * & head, int value, int beforeValue)
{
IntNodeType * cur, * prev, * newNode,*tmp;
newNode = new IntNodeType (value,NULL);
cur = Search (head, beforeValue);
if(cur!=NULL)
{
tmp=cur->prev;
newNode->prev=tmp;
newNode->nect=cur;
cur->prev=newNode;
}
else
{
//Did not find the node. Where to insert then?
}
}
Q3. // Please explain :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.