Delete item at tail of singly linked list (C++)

[toobladink]

I need help debugging this. I have already turned it in for a grade, but it doesn't actually work properly and I need to know where I should look to get this working. I've spent the past couple days trying to figure it out myself, and my test is coming up super soon on this, so any assistance is appreciated.

 

It currently works if the list is empty, and I can insert an item at the tail of the list, but if there is an item in the list, it does not work properly and I believe I have a mix up with the addresses.

 

For reference, this is a singly linked list. The constructor creates the head and tail of the list, and sets the length of private variable "length" to zero. A "node" is a struct that has been defined that holds an item and the address to the next "node."

 

void List2::PutItemT(itemType newItem)
{
	//cur is for: inserting a new item in list
	node* cur = new node;
	cur->item = newItem; // inserts the new item into the node
	cur->next = NULL; // assigns the address to NULL because it's the tail
	if (length == 0) // special case for when list is empty
	{
		head = cur;
		tail = cur->next;
	}
	else
	{
		// temp is for: prev item in list
		node* temp = new node;
		temp = head;
		while (temp->next != NULL) // iterates through to get last item in list
		{
			temp = temp->next;
		}
		if (temp->next == NULL) // i suppose this if statement is redundant, because it
		{ 						// should be reached anyways because of the way we move though the list
			temp->next = cur;   // assigns the pointer in the last node to point to the new node created
		}
		cur = temp->next;		
		tail = cur;
		temp = NULL;
	}
	length++;
	cur = NULL;
}

 

[colonel_mortis]

What is tail supposed to point to? In a functional language, it would point to the second element, and that's what you are setting it to in the length == 0 branch (where tail is NULL there), but in a procedural language it typically points to the last element to allow constant time insertions without needing to traverse the list, which is how you're using it in the else branch. I don't think that's the cause of your issue though, because you don't read from tail anywhere in that method.

 

There are a few other issues with your code (eg the node* temp = new node will create a memory leak), but I can't see anything that would cause the chain of ->next to not work correctly. What exactly isn't working in your list?

[toobladink]

In the assignment, tail was always supposed to point to the last item in the list. I set up a special case where the list is empty (when length == 0) because I was getting segmentation faults without it.

 

I'm trying to put an item at the end of the list, ideally using the tail pointer. If I try and add stuff at the tail, nothing gets added to the tail and I'm not quite sure why.

[colonel_mortis]

3 hours ago, toobladink said:

In the assignment, tail was always supposed to point to the last item in the list. I set up a special case where the list is empty (when length == 0) because I was getting segmentation faults without it.

 

I'm trying to put an item at the end of the list, ideally using the tail pointer. If I try and add stuff at the tail, nothing gets added to the tail and I'm not quite sure why.

Your current code (tweaked slightly just to suit me and my more Java coding style) works correctly for me, tested with

#include <iostream>

class Node {
    public:
        Node* next;
        int value;
};

class List2 {
        Node* head;
        Node* tail;
        int length;
    public:
        List2();
        void PutItemT(int newItem);
        void printList();
};

List2::List2() {
    head = nullptr;
    tail = nullptr;
    length = 0;
}

void List2::PutItemT(int newItem) {
    //cur is for: inserting a new item in list
    Node* cur = new Node;
    cur->value = newItem; // inserts the new item into the node
    cur->next = NULL; // assigns the address to NULL because it's the tail
    if (length == 0) // special case for when list is empty
    {
        head = cur;
        tail = cur;
    }
    else
    {
        // temp is for: prev item in list
        Node* temp = head;
        while (temp->next != NULL) // iterates through to get last item in list
        {
            temp = temp->next;
        }
        temp->next = cur;
        cur = temp->next;		
        tail = cur;
        temp = NULL;
    }
    length++;
    cur = NULL;
}

void List2::printList() {
    Node* current = head;
    std::cout << "[";
    while (current != nullptr) {
        std::cout << current->value;
        if (current->next != nullptr) {
            std::cout << ", ";
        }
        current = current->next;
    }
    std::cout << "]\n";
}

int main() {
    List2 lst;
    lst.printList();
    lst.PutItemT(3);
    lst.printList();
    lst.PutItemT(5);
    lst.printList();
    lst.PutItemT(7);
    lst.printList();
}

To use the tail pointer for insertions, both head and tail should point to cur in the length=0 block. It becomes

    if (length == 0) // special case for when list is empty
    {
        head = cur;
        tail = cur;
    }
    else
    {
        tail->next = cur;
        tail = cur;
    }

 

[toobladink]

9 hours ago, colonel_mortis said:

Your current code (tweaked slightly just to suit me and my more Java coding style) works correctly for me, tested with

#include <iostream>

class Node {
    public:
        Node* next;
        int value;
};

class List2 {
        Node* head;
        Node* tail;
        int length;
    public:
        List2();
        void PutItemT(int newItem);
        void printList();
};

List2::List2() {
    head = nullptr;
    tail = nullptr;
    length = 0;
}

void List2::PutItemT(int newItem) {
    //cur is for: inserting a new item in list
    Node* cur = new Node;
    cur->value = newItem; // inserts the new item into the node
    cur->next = NULL; // assigns the address to NULL because it's the tail
    if (length == 0) // special case for when list is empty
    {
        head = cur;
        tail = cur;
    }
    else
    {
        // temp is for: prev item in list
        Node* temp = head;
        while (temp->next != NULL) // iterates through to get last item in list
        {
            temp = temp->next;
        }
        temp->next = cur;
        cur = temp->next;		
        tail = cur;
        temp = NULL;
    }
    length++;
    cur = NULL;
}

void List2::printList() {
    Node* current = head;
    std::cout << "[";
    while (current != nullptr) {
        std::cout << current->value;
        if (current->next != nullptr) {
            std::cout << ", ";
        }
        current = current->next;
    }
    std::cout << "]\n";
}

int main() {
    List2 lst;
    lst.printList();
    lst.PutItemT(3);
    lst.printList();
    lst.PutItemT(5);
    lst.printList();
    lst.PutItemT(7);
    lst.printList();
}

To use the tail pointer for insertions, both head and tail should point to cur in the length=0 block. It becomes

    if (length == 0) // special case for when list is empty
    {
        head = cur;
        tail = cur;
    }
    else
    {
        tail->next = cur;
        tail = cur;
    }

 

Thank you so much for the help, this is extremely helpful to see where I messed up. I feel like I was a little lost on what I need to assign things, but this is super clear. Thanks!

[Blade of Grass]

Just remember to replace NULL with nullptr.

[ANUPLUCIFERGAMER]

On 4/4/2019 at 2:13 AM, colonel_mortis said:

What is tail supposed to point to? In a functional language, it would point to the second element, and that's what you are setting it to in the length == 0 branch (where tail is NULL there), but in a procedural language it typically points to the last element to allow constant time insertions without needing to traverse the list, which is how you're using it in the else branch. I don't think that's the cause of your issue though, because you don't read from tail anywhere in that method.

 

There are a few other issues with your code (eg the node* temp = new node will create a memory leak), but I can't see anything that would cause the chain of ->next to not work correctly. What exactly isn't working in your list?

How does 'new' create a mem leak?

[straight_stewie]

59 minutes ago, ANUPLUCIFERGAMER said:

How does 'new' create a mem leak? 

Trivially, new creates a memory leak every time it's not matched with a delete.

 

Since the pointer Node* = new Node is allocated on the stack, the pointer goes out of scope and gets lost at least as soon as the method ends. This does not destroy the object, it only loses the pointer. Since the method never had a call to delete Node there *appears to be a memory leak.

 

Realistically, however, the pointer is saved in the Nodes previous Node. Therefore, it can be deleted by iterating through the list and calling delete there.

[Blade of Grass]

On 4/6/2019 at 6:46 AM, straight_stewie said:

Realistically, however, the pointer is saved in the Nodes previous Node. Therefore, it can be deleted by iterating through the list and calling delete there.

You’re looking at the wrong code. Mortis was referring to the original code the author wrote in which there is a direct memory leak due to the allocation of new memory and the subsequent loss of reference in the next line. The code written was

Quote

node* temp = new node;
temp = head;

Which provides no way to reference to the newly allocated node.