C++

Forum

 
Deleting the head node in a linked list

Pages: 12
MrPigeon (26)
I know this question has been asked a few times, however all the examples I have seen do not return anything. Whereas I would like my function to return the data that was deleted.

I have this code at the moment, where value_type is just an alias for int at the moment:

1
2
3
4
5
6
7
8
9
10
11
12
 
node::value_type linkedlist::removeFromHead(){
	node* temp_head;
	node::value_type data;
	
	data = head_ptr->getData();
	temp_head = head_ptr;
	head_ptr = head_ptr->getNext();
	head_ptr->setPrevious(NULL);
	delete temp_head;

	return data;	
}


When I try to use this function though, I get a segfault. Any advice on what I'm doing wrong would be greatly appreciated.
Duthomhas (13206)
Somewhere in your linked list class you are attempting to access the old head after deleting it with the above method, or you are simply deleting the last node, which the above code fails to account for. Hope this helps.
cire (8284)
This code does not take handle an empty list or a list with a single item correctly.

What should the function return in the case of an empty list?
MrPigeon (26)
@Duoas, I've gone through my code and all of my methods only refer to head_ptr. Since head_ptr is assigned to the next node in the list, I don't understand how I could be trying to access the old head_ptr after deleting it.

@cire I believe this alteration should now make this method handle and empty list or a list with one item. Correct me if I am wrong though. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
node::value_type linkedlist::removeFromHead(){
	node* temp_head;
	node::value_type data;
	
	data = head_ptr->getData();
	temp_head = head_ptr;
	head_ptr = head_ptr->getNext();
	if (head_ptr != NULL) {
		head_ptr->setPrevious(NULL);
	} else {
		current_ptr = NULL;
		tail_ptr = NULL;
	}
	delete temp_head;
	
	return data;	
}


To answer your second question, I'm not entirely sure. The lab sheet I got didn't go into detail about how we should implement our methods, only what methods we should have.

I have left a thread on my course's discussion board asking "How could you check for NULL pointers and not return a value_type if it is NULL?". I figured I could still get the method working even if only on a list with a size of at least 1.
Last edited on
keskiverto (10402)
What if current_ptr was pointing to the head? You now cover that for one case only.

You would now return a default-constructed value_type from empty list, if line 5 would not crash due to nullptr.

You can document that calling removeHead on empty list is undefined.
You could throw exception if list is empty.
ne555 (10692)
@MrPigeon: http://www.cplusplus.com/forum/general/112111/


By the way, if using a circular list with a dummy header cell you don't need to check for NULL (next and previous would always point at a valid cell)
MrPigeon (26)
@ne555 I tried using the debugger, but I'm not entirely sure how it works in cygwin. I typed "gdb debug_list list_test" but I wasn't sure what to do next.
ne555 (10692)
$ gdb program_name
> run
(Seg Fault)
> backtrace
or you may use an IDE
MrPigeon (26)
@ne555, ah that was easier than I thought it would be. I don't really understand the backtrace part though.

Also, I don't want to use an IDE. Since the course I'm doing at the moment requires that all programs compile and run in cygwin, I'd rather just use it and nothing else. Even if I don't quite understand it all.

Anyway here's what I got when I debugged:

"Starting program: /cygdrive/c/uni/seng1120/lab5/list_test
[New Thread 14156.0x2788]
[New Thread 14156.0x21ec]
0
Please enter a number:
1
1
Please enter a number:
2
2
Please enter a number:
3
3
Please enter a number:
4
4
Please enter a number:
5
5

Program received signal SIGSEGV, Segmentation fault.
0x000000010040110b in banfield_lab5::node::~node() ()
(gdb) backtrace
#0 0x000000010040110b in banfield_lab5::node::~node() ()
#1 0x0000000100401131 in banfield_lab5::node::~node() ()
#2 0x000000010040114e in banfield_lab5::node::~node() ()
#3 0x0000000100401131 in banfield_lab5::node::~node() ()
#4 0x000000010040114e in banfield_lab5::node::~node() ()
#5 0x0000000100401131 in banfield_lab5::node::~node() ()
#6 0x000000010040114e in banfield_lab5::node::~node() ()
#7 0x0000000100401131 in banfield_lab5::node::~node() ()
#8 0x000000010040114e in banfield_lab5::node::~node() ()
#9 0x0000000100401131 in banfield_lab5::node::~node() ()
#10 0x000000010040114e in banfield_lab5::node::~node() ()
#11 0x0000000100401131 in banfield_lab5::node::~node() ()
#12 0x000000010040114e in banfield_lab5::node::~node() ()
#13 0x0000000100401131 in banfield_lab5::node::~node() ()
#14 0x000000010040114e in banfield_lab5::node::~node() ()
#15 0x0000000100401131 in banfield_lab5::node::~node() ()
#16 0x000000010040114e in banfield_lab5::node::~node() ()
#17 0x0000000100401131 in banfield_lab5::node::~node() ()
#18 0x000000010040114e in banfield_lab5::node::~node() ()
#19 0x0000000100401131 in banfield_lab5::node::~node() ()
#20 0x000000010040114e in banfield_lab5::node::~node() ()
#21 0x0000000100401131 in banfield_lab5::node::~node() ()
#22 0x000000010040114e in banfield_lab5::node::~node() ()
#23 0x0000000100401131 in banfield_lab5::node::~node() ()
#24 0x000000010040114e in banfield_lab5::node::~node() ()
#25 0x0000000100401131 in banfield_lab5::node::~node() ()
#26 0x000000010040114e in banfield_lab5::node::~node() ()
#27 0x0000000100401131 in banfield_lab5::node::~node() ()
#28 0x000000010040114e in banfield_lab5::node::~node() ()
#29 0x0000000100401131 in banfield_lab5::node::~node() ()
#30 0x000000010040114e in banfield_lab5::node::~node() ()
#31 0x0000000100401131 in banfield_lab5::node::~node() ()
#32 0x000000010040114e in banfield_lab5::node::~node() ()
#33 0x0000000100401131 in banfield_lab5::node::~node() ()
#34 0x000000010040114e in banfield_lab5::node::~node() ()
#35 0x0000000100401131 in banfield_lab5::node::~node() ()
#36 0x000000010040114e in banfield_lab5::node::~node() ()
#37 0x0000000100401131 in banfield_lab5::node::~node() ()
#38 0x000000010040114e in banfield_lab5::node::~node() ()
#39 0x0000000100401131 in banfield_lab5::node::~node() ()
#40 0x000000010040114e in banfield_lab5::node::~node() ()
#41 0x0000000100401131 in banfield_lab5::node::~node() ()
#42 0x000000010040114e in banfield_lab5::node::~node() ()
#43 0x0000000100401131 in banfield_lab5::node::~node() ()
#44 0x000000010040114e in banfield_lab5::node::~node() ()
#45 0x0000000100401131 in banfield_lab5::node::~node() ()
#46 0x000000010040114e in banfield_lab5::node::~node() ()
#47 0x0000000100401131 in banfield_lab5::node::~node() ()
#48 0x000000010040114e in banfield_lab5::node::~node() ()
#49 0x0000000100401131 in banfield_lab5::node::~node() ()
#50 0x000000010040114e in banfield_lab5::node::~node() ()
#51 0x0000000100401131 in banfield_lab5::node::~node() ()
#52 0x000000010040114e in banfield_lab5::node::~node() ()
#53 0x0000000100401131 in banfield_lab5::node::~node() ()
#54 0x000000010040114e in banfield_lab5::node::~node() ()
#55 0x0000000100401131 in banfield_lab5::node::~node() ()
#56 0x000000010040114e in banfield_lab5::node::~node() ()
#57 0x0000000100401131 in banfield_lab5::node::~node() ()
#58 0x000000010040114e in banfield_lab5::node::~node() ()
#59 0x0000000100401131 in banfield_lab5::node::~node() ()
#60 0x000000010040114e in banfield_lab5::node::~node() ()
#61 0x0000000100401131 in banfield_lab5::node::~node() ()
#62 0x000000010040114e in banfield_lab5::node::~node() ()
#63 0x0000000100401131 in banfield_lab5::node::~node() ()
#64 0x000000010040114e in banfield_lab5::node::~node() ()
#65 0x0000000100401131 in banfield_lab5::node::~node() ()
#66 0x000000010040114e in banfield_lab5::node::~node() ()
#67 0x0000000100401131 in banfield_lab5::node::~node() ()
#68 0x000000010040114e in banfield_lab5::node::~node() ()
#69 0x0000000100401131 in banfield_lab5::node::~node() ()
#70 0x000000010040114e in banfield_lab5::node::~node() ()
#71 0x0000000100401131 in banfield_lab5::node::~node() ()
#72 0x000000010040114e in banfield_lab5::node::~node() ()
#73 0x0000000100401131 in banfield_lab5::node::~node() ()
#74 0x000000010040114e in banfield_lab5::node::~node() ()
#75 0x0000000100401131 in banfield_lab5::node::~node() ()
#76 0x000000010040114e in banfield_lab5::node::~node() ()
#77 0x0000000100401131 in banfield_lab5::node::~node() ()
#78 0x000000010040114e in banfield_lab5::node::~node() ()
#79 0x0000000100401131 in banfield_lab5::node::~node() ()
#80 0x000000010040114e in banfield_lab5::node::~node() ()
#81 0x0000000100401131 in banfield_lab5::node::~node() ()
#82 0x000000010040114e in banfield_lab5::node::~node() ()
#83 0x0000000100401131 in banfield_lab5::node::~node() ()
---Type <return> to continue, or q <return> to quit---"

It seems the problem is in the destructor for my node class:

1
2
3
4
 
node::~node(){
		delete next;
		delete previous;
	}


I'm kinda sure I know what I'm doing wrong. But if anyone else knows, let me know. :)
Last edited on
giblit (3750)
What happens if next/previous are null? 
1
2
 
if(next) delete next;
if(previous) delete previous;
Also, you aren't using pointers to your nodes?
MrPigeon (26)
@giblit That's what I was testing now. I tried this code:

1
2
3
4
5
 
node::~node(){
	if (previous == NULL) {delete next;} 
	else if (next == NULL) {delete previous;}
	else if (next != NULL && previous != NULL) {delete next; delete previous;}
	}


This doesn't work though as I still get the same seg fault error in the debugger.

Also, I believe I am using pointers to my nodes. Here are the private variables from the node.h file: 

1
2
3
4
 
private:
	value_type data;
	node* next;
	node* previous;


And here's the private variables from the linkedlist.h file:

1
2
3
4
5
6
 
private:
	
	size_type used;
	node* head_ptr;
	node* tail_ptr;
	node* current_ptr;
Last edited on
giblit (3750)
Well..the thing is when you delete one node you delete everything else down that branch. So if you are trying to use this for your "remove" instead of removing one element you just removed the whole branch. To do it this way you would need to move it to the very bottom of the branch first. Then cleaning up the tree this way would be very easy. You could simply do something like delete head;
MrPigeon (26)
@giblit Ah, thank you. I realised what I did wrong thanks to you. I've updated my code to:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
//Precondition: A list has been instantiated and has at least one item
//Postcondition: The head pointer is deleted with the next item in the list becoming the head pointer
node::value_type linkedlist::removeFromHead(){
	node* temp_head;
	node::value_type data;
	
	data = head_ptr->getData(); //Return the data current stored in the head pointer
	temp_head = head_ptr; //Sets the temporary pointer to point to the head pointer
	head_ptr = head_ptr->getNext();	//Sets the head pointer to the next item in the list
	if (head_ptr != NULL) {	//If the next item is not empty, isolate the temporary node
		head_ptr->setPrevious(NULL);		
		temp_head->setNext(NULL); //This line right here!
	} else { //list is empty, update current and tail
		current_ptr = NULL;
		tail_ptr = NULL;
	}
	delete temp_head;
	
	return data;	
}


I'm not entirely sure if that is the solution you meant, but it works now and I'm happy. Thank you to everyone who helped :)

Edit: So I wanted to test whether this method was actually working but to do that I want to print out the list in its entirety. So I wrote a test program and included this loop:

1
2
3
 
 for (my_list->moveToHead(); my_list->getCurrent() != 0; my_list->forward()) {
		cout << my_list->getCurrent() << " -> ";
	}


But now I'm getting another segfault:

"Program received signal SIGSEGV, Segmentation fault.
0x0000000100401210 in banfield_lab5::node::getData() const ()
(gdb) backtrace
#0 0x0000000100401210 in banfield_lab5::node::getData() const ()
#1 0x000000010040187e in banfield_lab5::linkedlist::getCurrent() const ()
#2 0x0000000100401a74 in main ()"

Here's the implementations of getData() and getCurrent():

1
2
3
4
5
6
7
 
node::value_type node::getData() const {
		return data;
	}

node::value_type linkedlist::getCurrent() const{
	return current_ptr->getData();
}


Any chance anyone knows what I've done wrong now? Sorry dynamic memory allocation isn't exactly my forte yet..

Last edited on
ne555 (10692)
> What happens if next/previous are null?
http://www.cplusplus.com/reference/new/operator%20delete/
``If (the pointer) is a null-pointer, the function does nothing.''


> temp_head->setNext(NULL); //This line right here!
yes, that's correct


About your new issue
1
2
 
my_list->getCurrent() != 0
node::value_type linkedlist::getCurrent() const

getCurrent() returns a value, not a pointer to a note, so it would not give you NULL when reaching the end of the list
Last edited on
keskiverto (10402)
1
2
3
 
node::value_type linkedlist::getCurrent() const{
	return current_ptr->getData();
}

This should crash, if current_ptr is null.
You could guard it:
1
2
3
4
5
6
7
8
 
node::value_type linkedlist::getCurrent() const{
  if ( current_ptr ) {
    return current_ptr->getData();
  }
  else {
    return // what?
  }
}



The recursive destructor:
You have that
1
2
3
4
5
 
node::~node ()
{
  delete next;
  delete prev;
}

You have two nodes:
1
2
3
4
5
6
 
node * A = new node;
node * B = new node;
A->prev = nullptr;
A->next = B;
B->prev = A;
B->next = nullptr;

So good so far. Now you call
1
2
3
4
5
6
 
delete A;
// What happens?
// A->~node() calls delete next; i.e. B->~node()
// B->~node() calls delete prev; i.e. A->~node()
// A->~node() calls delete next; i.e. B->~node()
// ...

That doesn't sound fun after a while.

Solution:
1
2
3
4
5
6
7
 
node::~node ()
{
  if (next) next->prev = nullptr;
  if (prev) prev->next = nullptr;
  delete next;
  delete prev;
}


Your list has:
1
2
3
 
node* head_ptr;
node* tail_ptr;
node* current_ptr;

Whenever the list erases (some) nodes, it must ensure that those three pointers have consistent state after the operation.

One could consider the use of various smart pointer types instead of raw pointers (for educational purposes). All this is educational, isn't it? (The standard library already has linked lists.)
MrPigeon (26)
@ne555 I see, I have come up with a much simpler solution now. I just had to change counter from an int to size_t.

1
2
3
4
5
6
7
 
        cout << "NULL <-> ";	
	my_list->moveToHead();
	for (counter = 0; counter < my_list->size(); counter++) {
		cout << my_list->getCurrent() << " <-> ";
		my_list->forward();
	}
	cout << "NULL" << endl;


Here is the output of my now functioning test program:

"$ ./list_test
0 //Displays initial size
Please enter a number:
1 //Number entered by user
1 //Current size of the list
Please enter a number:
2
2
Please enter a number:
3
3
Please enter a number:
4
4
Please enter a number:
5
5
NULL <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> NULL // Displays the contents of the list
Removing from head: 1 //Displays the item that was removed from the head of the list
2 // Displays the value stored in the current item
4 // Displays the updated size of the list
NULL <-> 2 <-> 3 <-> 4 <-> 5 <-> NULL // Displays the new contents of the list"

@keskiverto Yes, this is entirely educational. Also, I believe I understood what you said about the destructor.

This is what I have now:

1
2
3
4
5
6
7
8
9
10
 
node::~node(){
	if (next != NULL) {
		next->setNext(NULL);
	}
	if (previous != NULL) {
		previous->setPrevious(NULL);
	} 
	delete next; 
	delete previous;
	}



Last edited on
keskiverto (10402)
I wrote: if (next) next->prev = nullptr;
You wrote: if (next) next->setNext( nullptr );
Details, details, ...
cire (8284)
Also, I believe I understood what you said about the destructor.

This is what I have now:
1
2
3
4
5
6
7
8
9
10
 
node::~node(){
	if (next != NULL) {
		next->setNext(NULL);
	}
	if (previous != NULL) {
		previous->setPrevious(NULL);
	} 
	delete next; 
	delete previous;
	}


It's an odd design decision you've made. Generally speaking, a node should not delete other nodes. If this destructor is invoked on a node in the middle of a linked list, you're going to have two separate unattached lists (assuming reasonable behavior from node::setNext and node::setPrevious.)
MrPigeon (26)
@keskiverto & cire Ah, I see. I just did some drawings on paper and I think I know what's going on now.

1
2
3
4
5
6
 
node::~node(){
	if (next != NULL) next->previous = NULL;
	if (previous != NULL) previous->next = NULL; 
	delete next; 
	delete previous;
	}


So if next is not equal to NULL then the previous of next is assigned to NULL. If previous is not equal to NULL then the next of previous is assigned to NULL. Then it is safe to delete next and previous.

But as cire said, if the destructor was invoked from a method (e.g removeFromCurrent()) then I would have two lists with one having its tail pointing to a null pointer and the other with its head pointing to another null pointer.

So would I add another if clause such as:

1
2
3
4
 
if (next != NULL && previous != NULL) {
		next->previous = previous;
		previous->next = next;
	}


or do I make sure that I've isolated the pointer (As in my removeFromHead() method above) and set the previous and next within the function removeFromCurrent()?

Or is it just up to me how I wish to implement it?
Last edited on
cire (8284)
If the goal of your node destructor is to keep a linked list knit together when a node is deleted, it should probably look something like this:

1
2
3
4
5
 
node::~node()
{
    if (next) next->previous = previous ;
    if (previous) previous->next = next ;
}


Note that delete is not used in the destructor.

Then, linkedlist::removeFromHead would look something like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
//Precondition: A list has been instantiated and has at least one item
//Postcondition: The head pointer is deleted with the next item in the list becoming the head pointer
node::value_type linkedlist::removeFromHead()
{
    node* delete_me = head_ptr ;
    head_ptr = head_ptr->getNext();

    if (tail_ptr == delete_me) tail_ptr = head_ptr;
    if (current == delete_me) current = head_ptr;

    auto data = delete_me->getData();
    delete delete_me;   // takes care of updating links.
    return data;
}


Your postcondition should probably mention something about the value of current.
Last edited on
Pages: 12