How to remove one item from a linked list?

[idknuttin]

I had to write a program where the user enters a series of integers and I store those integers using a linked list, when the user enters -9 I stop recording the integers to the linked list. Then the user enters one last integer and if that integer is in the linked list I have to remove (delete) its first occurrence from the linked list and print the linked list, if that number that the user entered is not in the linked list then I simply have to print the linked list. I also have to delete the linked list at the end of the program to free up the ram.

I have a program where the linked list is created from the user inputs, I just need help with the part where I have to delete the last number the user enters from the linked list. I wrote a piece of code that supposedly deletes that one entry but I am not sure if I did it correctly, I'll comment in the code so you know what I am trying to do.

The code does work as intended, however I am not sure if it works because I actually deleted the first occurrence or because I simply skipped over the first occurrence when printing the linked list.

This is homework so I do not want anyone to give me that code if my code doesn't make sense, I want someone to try and explain to me what I am doing wrong and how I can fix it.

Thank you.

  #include <iostream>

class ListNode{
public:
int content;
ListNode *pointerToNext;
};

void freeTheMemory(ListNode *runner){
if( runner!=nullptr){
freeTheMemory((*runner).pointerToNext);
delete runner;
}
}

int main(){
int userInput;
ListNode *head;
std::cout<<"Insert the first element of the list: ";
std::cin>>userInput;
head=new ListNode;
(*head).content=userInput;
(*head).pointerToNext=nullptr;
ListNode *runner;
runner=head;

while(userInput!=-9){
std::cout<<"Insert an element of the list (-9 for the end): ";
std::cin>>userInput;
if(userInput!=-9){
(*runner).pointerToNext=new ListNode;
runner=(*runner).pointerToNext;
(*runner).content=userInput;
(*runner).pointerToNext=nullptr;
}
}

std::cout<<"Enter another element" <<std::endl;
int userInput2;
std::cin>>userInput2;


std::cout<<"List printout: "<<std::endl;
runner=head;
int first = 0;  //counter so only the first occurrence gets deleted
 
while(runner!=nullptr){
if(userInput2 == (*runner).content && first==0){  
                                      //***not sure if this if statement
  ListNode* temp;                     //breaks the linked list
  temp=runner;                        //or if it even does anything?
  runner=(*runner).pointerToNext;
  delete temp;
  first++;
}
std::cout<<(*runner).content<<" ";
runner=(*runner).pointerToNext;
}
std::cout<<std::endl;

// FREEING THE MEMORY
freeTheMemory(head);

return 0;
}

[dhayden]

Thank you for plainly stating that this is homework and for wanting to learn rather than just get the answer.

You'll save yourself a lot of heartache if you indent your code to reflect the actual block structure. It's way too easy to miss a closing brace otherwise, or to think that a statement is part of a particular block when it isn't.

Line 11 etc.: Instead of (*runner).pointerToNext, use runner->pointerToNext They mean the same thing and it's easier to type.

Your code to delete the item isn't right. You delete the item but there is still a pointer in the previous node to the deleted item. If you copy the code to print the list and print it a second time, all hell breaks loose:

    std::cout << "Printing/deleting again\n";
    runner = head;
    first = 0;          //counter so only the first occurrence gets deleted
    while (runner != nullptr) {
        if (userInput2 == (*runner).content && first == 0) {
            //***not sure if this if statement
            ListNode *temp;     //breaks the linked list
            temp = runner;                       //or if it even does anything?
            runner = (*runner).pointerToNext;
            delete temp;
            first++;
        }
        std::cout << (*runner).content << " ";
        runner = (*runner).pointerToNext;
    }
    std::cout << std::endl;

Insert the first element of the list: 1
Insert an element of the list (-9 for the end): 2
Insert an element of the list (-9 for the end): 3
Insert an element of the list (-9 for the end): 4
Insert an element of the list (-9 for the end): 5
Insert an element of the list (-9 for the end): 6
Insert an element of the list (-9 for the end): 7
Insert an element of the list (-9 for the end): 8
Insert an element of the list (-9 for the end): -9
Enter another element
3
List printout:
1 2 4 5 6 7 8
Printing/deleting again
1 2 -2144448728 -2144448744 -2144448760 -2144448776 -2144448792 0
Aborted (core dumped)

I suggest a separate function to delete the item. The typical way (which isn't the most efficient) is to use a pointer to the previous element in the list. Something like this:

    Node *prev = nullptr;
    for (Node *cur = head; cur; prev = cur, cur = cur->next) {
        if (cur->content == val) {
            // found the node. Now delete it
            if (prev) {
                prev->next = cur->next;
            } else {
                head = cur->next;
            }
            delete cur;
            break;
        }
    }

[idknuttin]

I didn't fully understand your code but I wrote new code with your suggestion of first going through the list, finding and deleting the item, then printing out the list later. The code compiles but and error occurs and does not print the list, do you know what I am doing wrong here?

  ListNode* cur;
  ListNode* next;
  ListNode* prev;
  cur=head;
  next=head;
  prev=head;
  int first = 0;

  while(next != nullptr){
    if(first == 0){
    cur=(*cur).pointerToNext;
  }
    next=(*next).pointerToNext;

    if((*cur).content == userInput2 && first == 0){  //find the first occurrence user's number.
      next=(*next).pointerToNext;              //set next to one item after the first occurrence.
      delete cur;                                         //delete the first occurrence.
      (*prev).pointerToNext=next;              //make the previous item before the first occurrence
      first++;                                               //point to next to connect the entire list.
    }
    prev=(*prev).pointerToNext;
  }

[cire]

On line 17 you delete a node. On line 15, the next iteration of that loop you treat it as if it points to a valid node, resulting in undefined behavior. Perhaps you should terminate the loop immediately after deleting the node.

[idknuttin]

I edited the loop to end once it deletes the node and it still says "segmentation failure (core dumped)"

[gunnerfunner]

OP: dhayden's observation:

Normally a list uses two classes: one for the list itself and one for a node within the list. You're using one class to represent both, which is a little unusual.

from here: http://www.cplusplus.com/forum/beginner/208101/ ... is also relevant for you

As you don't want code for your particular example what I've done is added a deleteNode() method to the program in the above link so that you can take a look and see if it can be helpful:

#include<iostream>

struct Node
{
	Node* next;
	int data;
	Node(const int d) : data(d), next(nullptr) {}
	~Node() {std::cout << "Goodbye " << data << '\n';}
};
struct LList
{
    Node* start = nullptr;
    void insert (const int& item);
    void deleteNode(const int& item);
    void display()const;
    ~LList()
	{
	    Node* temp = start;
	    while (temp)
        {
            Node* next = temp -> next;
            delete temp;
            temp = next;
        }
        start = nullptr;
    }
};
void LList::insert(const int& item)
{
	Node* temp = new Node(item);
	if(!start)
    {
        start = temp;
    }
    else
    {
        Node* last = start;
        while (last -> next)
        {
            last = last -> next;
        }
        last -> next = temp;
    }
}
void LList::display()const
{
	Node* show = start;
	while (show)
	{
		std:: cout << show ->data << '\n';
		show = show->next;
	}
}
void LList::deleteNode(const int& item)
{
    if (start -> data == item)//first node delete
    {
        Node* temp  = start;
        start = start -> next;
        delete temp;
        temp = nullptr;
        return;
    }
    if (start -> next)//list has more than 1 node
    {
        Node* lead = start -> next;
        Node* current = start;
        while (lead -> next)
        {
            if(lead -> data == item)
            {
                current -> next = lead -> next;
                Node* temp = lead;
                lead = lead -> next;
                delete temp;
                temp = nullptr;
                if(lead -> next)
                {
                    lead = lead -> next;
                    current = current -> next;
                }
            }
            else
            {
                lead = lead -> next;
                current = current -> next;
            }
        }
        if (lead -> data == item)//now lead is the last node
        {
            current -> next = nullptr;
            delete lead;
            lead = nullptr;
        }
    }
}

int main()
{
	LList n;
	int input{};
	do
    {
        std::cout << "Insert an element \n";
        std::cin >> input;//suggest input validation
        if(input != -9)
        {
            n.insert(input);
        }
    } while (input != -9);
    n.display();
    int delItem{};
    std::cout << "Enter another element to delete \n";
    std::cin >> delItem;
    n.deleteNode(delItem);
	n.display();
}

ps: this program does not check for an empty list explicity but that should also be added in

[idknuttin]

Thanks to everyone who posted with hints, I was able to make a program that works and with all of the necessary checks, I didn't use a class to create the linkedlist because I am not too comfortable/familiar with classes yet so I just used a while loop like in my original code.

[idknuttin]

if anyone is interest here is my code that works, yes it's longer then it needs to be but this helps me understand it better, once I learn shortcuts and how to make code shorter I will write shorter code.

Whenever userInput2 is not in the list the program would not run properly but when I made it so the program won't enter the while loop at line 71 if userInput2 is not in the list then the program started working fine, however that while loop doesn't change anything in the list if userInput2 is not in the list so I don't know why it was breaking the program, does anyone have any ideas?

#include<iostream>

class ListNode{
public:
  int content;
  ListNode *pointerToNext;
};

void freeTheMemory(ListNode *runner){
  if(runner != nullptr){
    freeTheMemory((*runner).pointerToNext);
    delete runner;
  }
}

int main(){
  int userInput;
  ListNode *head;
  std::cout<<"Insert the first element of the list: ";
  std::cin>>userInput;

  int listno = 1;  //keep track number of elements

  head = new ListNode;
  (*head).content=userInput;
  (*head).pointerToNext=nullptr;
  ListNode *runner;
  runner=head;

  while(userInput != -9){  //create linkedlist
    std::cout<<"Insert an element of the list (-9 for the end): ";
    std::cin>>userInput;
    if(userInput != -9){
      listno++;
      (*runner).pointerToNext=new ListNode;
      runner=(*runner).pointerToNext;
      (*runner).content=userInput;
      (*runner).pointerToNext=nullptr;
    }
}

  std::cout<<"Enter another element" <<std::endl;
  int userInput2;
  std::cin>>userInput2;

  runner=head;
  int matchingElement = 0;
  while(runner != nullptr){  //check if list has a matching element
    if((*runner).content==userInput2){
      matchingElement++;
    }
    runner=(*runner).pointerToNext;
  }

  //if list only contains matching element
  //delete it and end program
  if(listno == 1 && matchingElement > 0){
    delete head;
    std::cout<<"Your list is empty" <<std::endl;
    return 1;
  }

  ListNode *cur;
  ListNode *next;
  ListNode *prev;
  cur=head;
  next=head;
  prev=head;

  //finding and deleting the first occurrence of matching element
  while(next != nullptr && matchingElement > 0){
    if((*head).content == userInput2){
      ListNode *temp;
      temp=head;
      head=(*head).pointerToNext;
      delete temp;
      break;
    }

    next=(*next).pointerToNext;
    cur=(*cur).pointerToNext;

    if((*cur).content == userInput2){
      next=(*next).pointerToNext;
      delete cur;
      (*prev).pointerToNext=next;
      break;
    }
    prev=(*prev).pointerToNext;
  }

  //printing remaining list
  std::cout<<"List printout: " <<std::endl;
  runner=head;
  while(runner != nullptr){
    std::cout<<(*runner).content<<" ";
    runner=(*runner).pointerToNext;
  }

  std::cout<<std::endl;

  //free the memory
  freeTheMemory(head);

  return 0;
}