Having trouble removing the last item in a singly linkedlist

[decoy98]

Hello, I have implemented a simple method that removes a number via search. I got it working to the point that it deletes any node from the head till before the last item. The only problem I have is that what if the user specifies a number to be removed and the number happens to be in the last position in the linked list?

/* private variables, SinglyLinkedList.h */
	private:
		// A node has the item, and a pointer to the next node
		struct SinglyLinkedListNode {
			ListItemType item;
			SinglyLinkedListNode *next;
		};

		int size; // how many nodes are in the SinglyLinkedList
		SinglyLinkedListNode *head; // points to the head node

		// finds a specific node in the linked list
		SinglyLinkedListNode *find(int index) const;

/* SinglyLinkedList.cpp deleteNumber(int number) method */
  void SinglyLinkedList::deleteNumber(int number) {
	SinglyLinkedListNode * nextNode = new SinglyLinkedListNode;
	SinglyLinkedListNode * traversalNode = new SinglyLinkedListNode;

	traversalNode = head;	// assign traversal node to beginning of the list
	nextNode = traversalNode->next;

	// if the number we are looking to delete is in the head node, delete it
	if (head->item == number) {
		head = nextNode;
		cout << "=> Deleted " << number << " from the list." << endl;
		size--;
	}

	// if it's somewhere else
	else {
		while (traversalNode->next != NULL) {	// traverse nodes until the end of the list
			traversalNode = traversalNode->next;	// iteration part
			nextNode = traversalNode->next;
			if (traversalNode->item == number) { // if current node's value is what we are looking for, break
				break;
			}
		}
		// if we reached the end of the list, and can't find, print error
		if (traversalNode->next == NULL) {
			if (traversalNode->item == number) {
				// This is the last number, delete me.
			}
			else {
				cout << "=> Can't find " << number << " in the list." << endl;
			}
		}
		// if we reached the desired number to delete, delete it.
		else {
			traversalNode->item = nextNode->item;
			traversalNode->next = nextNode->next;
			size--;
			cout << "=> Deleted " << number << " from the list." << endl;
		}
	}
}

[LendraDwi]

To delete first node move *head to head->next, then delete the node.
to delete last node change next to NULL in a node before the last node, i suggest to create somethinh like *tail to mark the last node in link list

[andywestken]

Keeping track of the tail can help in some situations, but here the main issue is that the list traversal loop at lines 32-38 is not keeping track of the previous node. At this point you don't need the next one (that's available as a member of the current node) but you do need the previous node.

This is because when you delete the node you found (ignoring the head node for the moment) you've got to set the previous node's next to the next of the node you're just about to delete (which will be null it you're deleting the current last link.)

(Talking of delete, I don't see any unwanted nodes being deleted?)

Actually, looking at lines 50, 51 I see you're not actually removing the found node; instead you're copying the contents of the next node over to the found node and throwing the next node away (consequently leaking the old next node's memory.)

There should be no copying of the value at this point; just relinking of the nodes (and a delete!) As it's just an int you're copying here it's cheap, but if this was was a bulky data object the copy operation could cost!

And I think you are complicating things a bit by the way you are using traversalNode->next == NULL to test whether a node has been found or not. Using traversalNode == NULL and the previous node works for me with no special casing for last node.

Andy

PS

1. Can the list ever be empty? (i.e. have no head node?) If so, then line 21 could crash your program.

2. I see you class provides a "find" method, though the parameter name implies that it's intended to return the i'th entry rather actually find something. Or is the value of index compared against the item member of the SinglyLinkedListNode structs? You could split deleteNumber into a find operation (which could be used elsewhere) and the actual node removal.

3. Lines 17 and 18 of your code don't look quite right?

    SinglyLinkedListNode * nextNode = new SinglyLinkedListNode;
    SinglyLinkedListNode * traversalNode = new SinglyLinkedListNode;

After creating the two new nodes you are then trampling on them (so you're leaking memory.) A cut and paste-ism??