Doubly linked list trying to delete selected node

Question

Im trying to use a doubly linked list and reading in from a text file to create a very basic cache. For now the cache capacity is 5 and I read in 20 values from the txt file the values 1-20. When I try to delete the head and then print the linked list, it print 0,2,3-20, so replacing 1 with 0. As far as I understand it I need to create a temporary node to set to the head value, then point the head to the next node and finally delete the temp node, which is what I've done, but I am clearly missing something vital.

int main(int argc, char** argv) {
node* head;
node* tail;
node* n;

int capacity = 5; 
int size = 0;

std::string fileName;   
std::ifstream inFile;

int start_block, num_blocks, ignore, req_num;
std::cout << "Project 3 milestone: LRU" << std::endl;
std::cout << "Enter filename: " << std::endl;
std::cin >> fileName;


inFile.open(fileName.c_str(), std::ifstream::in);
if (!inFile)    {
    std::cerr << "Cannot open file!  " << fileName << std::endl;
}

while(inFile.is_open()) {
    inFile >> start_block >> num_blocks >> ignore >> req_num;
    n = new node;
    n->data = start_block;
    n->prev = NULL; // 1st node
    head = n;
    tail = n;
    size++;

    while(!inFile.eof())    {
        inFile >> start_block >> num_blocks >> ignore >> req_num;
        n = new node;
        n->data = start_block;
        n->prev = tail;
        tail->next = n;
        tail = n;
        size++;
        //std::cout << start_block << " " << num_blocks << " " << ignore << " " << req_num << std::endl;    
        if  (size == capacity)  {
            cout << "Reached capacity:" << capacity << endl;
            // this is where I would delete the head node
        }   
    }           
    inFile.close();
}

PrintForward(head);
//PrintReverse(tail);
SearchRecursive(head,18);
DeleteHead(head, tail);
PrintForward(head);
//DeleteHead(head, tail);
//PrintForward(head);
return 0;
}

void SearchRecursive(node* ptr, int searchValue)    {
if(ptr == NULL) {   // if we pssed through list and didnt find value
    cout << searchValue << " was NOT found in the list\n";
}       
else if (ptr->data == searchValue)  {   // if we DID find it
    cout << searchValue << " IS in the list!\n";
}
else    {
    SearchRecursive(ptr->next, searchValue);    // else search recursively
}
}

void DeleteHead(node* head, node* tail) {
if (head == tail)   {   // if only 1 element
    cout << "Only 1 element here" << endl;
    delete head;
    head = NULL;
    tail = NULL;
}
else    {
    cout << "More than 1 element here" << endl;
    node *temp = head;
    head = head->next;
    delete temp;
}
}

EDIT: I improved the SearchRecursive function and can now delete nodes apart from the head and tail. Here is what I am using:

void SearchRecursive(node* ptr, int searchValue)    {
if(ptr == NULL) {   // if we pssed through list and didnt find value
    cout << searchValue << " was NOT found in the list\n";
}       
else if (ptr->data == searchValue)  {   // if we DID find it
    cout << searchValue << " IS in the list!\n";
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
    delete ptr;
}
else    {
    SearchRecursive(ptr->next, searchValue);    // else search recursively
}
}

Arkady Godlin Arkady Godlin · Accepted Answer · 2018-04-08T18:45:44

because you delete the head pointer, after you call DeleteHead the head pointer is now invalid, as the pointer isn't changed, the change in the function only reflect the value to where points the head parameter inside the function and it is not reflected outside this function, what you want is to change the value of the passed pointer, this is done by reference. so your function is now getting a reference to pointer and signature of function is now

void DeleteHead(node** head, node* tail)

and inside the function do *head = (*head)->next;

or you could just return the new head value from the function

node* DeleteHead(node* head, node* tail)

Doubly linked list trying to delete selected node

2 Answers