/* Chapter 15 - Project 1 Directions: Write a program to remove an element from a linked list; the remove function should take just the element to be removed. Is this function easy to write and will it be fast? Could this be made easier or faster by adding and additional pointer to the list? */
#include <ctime> // time
#include <cassert>
#include <iostream>
usingnamespace std;
//our linked list structure, has one intege
struct LinkedList
{
int value; // our value
LinkedList* pNextValue;// pointer to the next value
};
LinkedList* head = NULL; // global variable head (start of list)
// add value
LinkedList* addValue(int v)
{
LinkedList* pValue = new LinkedList; // allocate memory
pValue->value = v; // set pointer to the random number
pValue->pNextValue = head; // point to previous first element in list
head = pValue; // update so that our newest value is at the beginning of list
return pValue;// return our list
}
// traverse through list and display
void displayList()
{
LinkedList* current = head; // setting current to first element in list
int i = 1; // keeps track
while(current != NULL)
{
cout << "Value #" << i << ": " << current->value << ".\n";
current = current->pNextValue; // go to next value
i++; // increment i
}
}
// remove an element from the linked list
void removeElement(int remValue)
{// to remove an element, we go through the list, find the value given // if we find it, stop // to remove, disconnect the link // relink the two values now (ie. value 1->2->3->NULL, 2 is removed, 1->3->NULL )
// LinkedList* current = head;
// LinkedList* next = current;
// while(current != NULL)
// {
// if(current->value == remValue)
// { // if match
// break; // break out of while
// }
// else
// {
// cout << "Value " << current->value << " does not match " << remValue << ".\n";
// next = current; // save in case
// current = current->pNextValue;
// go to next value
// }
// }
// end while
// if(current == NULL)
// {
// if we reached end of list
// cout << "Can't remove value: no match found.\n"; // no match, cant remove
// }
// else
// { // found match
// cout << "Deleting: " << current << "\n";
// delete current;
// current = next->pNextValue; // current is updated
// }
// }
// LinkedList *first;
// LinkedList *current;
// LinkedList *trailCurrent;
// bool found;
// if(first == NULL) //Case 1
// cerr<<"Cannot delete drom an empty list";
// else
// {
// current = first;
// found = false;
// while(current != NULL && !found)//search the list
// if(current->value == remValue)
// found = true;
// else
// {
// trailCurrent = current;
// current = current->pNextValue;
// }
// if(current == NULL) //Case 4
// cout<<"Item to be deleted not in list"
// <<endl;
// else
// if(current->value == remValue)
// {
// if(first == current) //Case 2
// {
// first = first->pNextValue;
// delete current;
// }
// i--;
// }
// else
// cout<<"Item to deleted not in list";
//}
// }
LinkedList *current;
LinkedList *first;
LinkedList *trailCurrent;
bool found;
if(first == NULL)
cerr<<"Cannot delete from an empty list.\n";
else
{
if(first->value == remValue)
{
current = first;
first = first->pNextValue;
// count--;
if(first == NULL)
// last = NULL;
delete current;
}
else
{
found = false;
trailCurrent = first;
current = first->pNextValue;
while(current != NULL && !found)
{
if(current->value != remValue)
{
trailCurrent = current;
current = current->pNextValue;
}
else
found = true;
}
if(found)
{
trailCurrent->pNextValue = current->pNextValue;
// count--;
// if(last == current)
// last = trailCurrent;
delete current;
}
else
cout<<"Item to be deleted is not in the list."<<endl;
}
}
}
// main
int main()
{
LinkedList* listValue = addValue(3); // add a value to our linked list
cout << "In memory, our list value is at: " << listValue << "\n"; // mem address
cout << "Our actual value should be: " << listValue->value << "\n"; // actual value there
cout << "Adding more values.\n"; listValue = addValue(5);
listValue = addValue(10);
listValue = addValue(15);
cout << "Mem address for " << listValue->value << ": " << listValue << "\n";
displayList();
removeElement(5);
displayList();
cout << "\n";
}
You can greatly simplify the remove function. Instead of keeping a pointer to the previous item (trailCurrent in your code), keep a pointer to the pointer to the current item. When the loop starts, this points to head. Afterwards, it points to the pNextValue pointer in the previous item. With this method, there are no special exceptions for empty lists or removing from the front of the list
// remove an element from the linked list
void
removeElement(int remValue)
{
LinkedList **pHeadOrNext; // points to head, or a node's pNextValue pointer
LinkedList *current; // points to the current node
for (pHeadOrNext = &head; // pHeadOrNext points to head pointer
(current = *pHeadOrNext); // assign current to whatever pHeadOrNext points to. If result is null then exit loop
pHeadOrNext = ¤t->pNextValue) { // point pHeadOrNext at the current node's pNextValue pointer
if (current->value == remValue) {
// found it;
*pHeadOrNext = current->pNextValue;
delete current;
return;
}
}
cout << remValue << " is not in the list.\n";
}