Deleting the head node in a linked list

[MrPigeon]

@cire That makes sense. That should make implementing removeFromCurrent a lot simpler. Also, now I can modify my method removeFromHead() to:

//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
	current_ptr = head_ptr; //Fail-safe in case current_ptr is set to the old head
	if (head_ptr == NULL) { //List is empty, update current and tail
		current_ptr = NULL;
		tail_ptr = NULL;
	}
	delete temp_head;
	
	return data;	
}

[keskiverto]

Line 12: if head is null, then current is already null.

Line 10. This is a design decision. You reset current to head on every removal.
The other way is to update current only if it does point to the temp.


PS. Consider using nullptr in stead of NULL.

[MrPigeon]

@keskiverto I reset current to head on every removal since I have not overloaded the comparison operator yet. So I can't write if (current_ptr == temp_head) etc. I wanted to test whether the function worked though and that was the easiest solution I found that didn't cause a segfault.

I've removed the current_ptr = NULL; line for now as like you said, current is reset to head on every removal. Once I overload the == operator though, this will most likely change.

I tried using nullptr but then I got the error message:

"$ make
g++ -c -Wall -c linkedlist.cpp
linkedlist.cpp:75:3: warning: identifier ‘nullptr’ is a keyword in C++11 [-Wc++0x-compat]
tail_ptr = nullptr;
^
linkedlist.cpp: In member function ‘banfield_lab5::node::value_type banfield_lab5::linkedlist::removeFromHead()’:
linkedlist.cpp:75:14: error: ‘nullptr’ was not declared in this scope
tail_ptr = nullptr;"

I did a bit of searching on google but I'm not very proficient with cygwin so I didn't really understand what I had to do. So I just kept using NULL.

[keskiverto]

I have not overloaded the comparison operator yet

Those are raw pointers, are they not. You cannot overload comparison of addresses. You have the ==.

g++ -std=c++11 -Wall -c linkedlist.cpp

See gcc manual for the -std= option. (GCC still uses -std=gnu++98 by default.)

Note: you have -c twice.

[MrPigeon]

So are you saying if (current_ptr == temp_ptr) is already valid? Otherwise how can I check whether current is pointing to an item that is about to be deleted?

Honestly, I've just been using the makefile that was supplied to me by my lecturer.

CC=g++
CFLAGS=-c -Wall
LDFLAGS=
SOURCES=node.cpp linkedlist.cpp list_test.cpp
OBJECTS=$(SOURCES:.cpp=.o)
EXECUTABLE=list_test.exe

all: $(SOURCES) $(EXECUTABLE)
	
$(EXECUTABLE): $(OBJECTS)
	$(CC) $(LDFLAGS) $(OBJECTS) -o $@

%.o : %.cpp
	$(CC) $(CFLAGS) -c $<

clean:
	rm -rf *.o core

[MrPigeon]

So it is valid. Here is the code I have at the moment:

//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 (current_ptr == temp_head) { //If the current pointer is pointing to the old head, set current to the next item(i.e the new head)
		current_ptr = head_ptr;
	}
	if (head_ptr == NULL) { //If the list becomes empty, update the current and tail pointers
		current_ptr = NULL;
		tail_ptr = NULL;
	}
	delete temp_head;
	
	return data;	
}

I've tested it with a list of 1 item and with a list of multiple items where current is set to either head, tail or an item in between. And so far, it seems pretty robust. It gives the correct results and doesn't crash. :)

[keskiverto]

What if you call this on an empty list?



Line 14 is not necessary. Head can become null only if you are about to remove the last node. If list has only one node, then current was pointing to it, and line 11 has already set current null.

[MrPigeon]

It will crash. I have documented in the precondition that the list must have a size of at least one item before calling this method. At least until I implement a try catch block.