Linked list pop_back implementation ignores pointer-to-nullptr

Question

Let's assume I'm only allowed to use new and delete and no smart pointers in my implementation. I am not using sentinel nodes.

Below is my implementation for pop_back:

void sLinkedList::pop_back()
{

  if(begin == nullptr)
  {
    std::cerr << "There is nothing to pop." << std::endl;
  }
  else
  {
    node* nodeToDelete = begin;
    while(nodeToDelete->next != nullptr)
    {
      nodeToDelete = nodeToDelete->next;
    }
    delete nodeToDelete;
    nodeToDelete = nullptr;
    --mSize;
  }

}

What it does is it creates a pointer to a node nodeToDelete and it iterates through the whole list until it reaches the last node (the node that points to nullptr). Then I delete that last node, set it equal to nullptr, and everything should be fine because the node before this (previously the second-to-last node) now points to a nullptr, marking the end of the list.

When I ran main with the following instructions:

int main()
{
  sLinkedList newList;
  std::cout << "Length is " << newList.length() << std::endl;
  newList.print();
  newList.push_front(4);
  std::cout << "Length is " << newList.length() << std:: endl;
  newList.print();
  newList.pop_back();
  std::cout << "Length is " << newList.length() << std::endl;
  newList.print();
}

I get the output:

Length is 0
The list is empty.
Length is 1
4
Length is 0
4 // should print "There is nothing to pop."

Adding another pop_back directly after the first results in an Aborted (core dumped) signal.

Why doesn't the idea work?

user5323053 · Accepted Answer · 2016-08-17 09:08:31Z

Okay, but does it?

When you assign nodeToDelete = nodeToDelete->next; you're saying that your local pointer nodeToDelete now refers to the same location in memory as does nodeToDelete->next. There is no other relationship between the two pointers. So when you then assign nodeToDelete = nullptr; you're actually doing nothing: that local pointer is never used again, so it doesn't particularly matter what region of memory it points to.

Unfortunately, the should-be final node still points to where it used to, even though you deleted that node, and so your next pop_back call happily iterates into inaccessible memory.

I'm assuming this is homework so I probably shouldn't rewrite it for you. But you can fix it by actually modifying the should-be last node, rather than just your local copy of its next pointer.

Of course, if this is a real project, std::forward_list might help. :v

Anthem · Accepted Answer · 2016-06-28 21:39:45Z

1

everything should be fine because the node before this (previously the second-to-last node) now points to a nullptr, marking the end of the list.

Okay, but does it?

When you assign nodeToDelete = nodeToDelete->next; you're saying that your local pointer nodeToDelete now refers to the same location in memory as does nodeToDelete->next. There is no other relationship between the two pointers. So when you then assign nodeToDelete = nullptr; you're actually doing nothing: that local pointer is never used again, so it doesn't particularly matter what region of memory it points to.

Unfortunately, the should-be final node still points to where it used to, even though you deleted that node, and so your next pop_back call happily iterates into inaccessible memory.

I'm assuming this is homework so I probably shouldn't rewrite it for you. But you can fix it by actually modifying the should-be last node, rather than just your local copy of its next pointer.

Of course, if this is a real project, std::forward_list might help. :v

answered Jun 28, 2016 at 21:39

Anthem

191 bronze badge

3 Comments

Jossie Calderon Over a year ago

when I perform delete nodeToDelete, I'm assuming that I'm freeing the memory that nodeToDelete points to, which is the last node in the list. Isn't that true?

Anthem Over a year ago

Yes, the memory is deallocated, just as planned. That doesn't stop other nodes from holding pointers to it, though. You need to make sure nothing tries to access the memory you've freed. That means setting the last next pointer to nullptr.

Jossie Calderon Over a year ago

Ah, I see. I am supposed to set the before-the-last's next pointer to nullptr. That's impossible with the current method.

Collectives™ on Stack Overflow

Linked list pop_back implementation ignores pointer-to-nullptr

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related