Pointers

[stoneJax]

I am trying to write a function that uses a number of pointers to nodes in a linked list. The pointers that I am supposed to use are headPtr, tailPtr, precursor, and cursor. The head and tail are the obvious ones, while cursor points to the current item in the list and precursor points to the item before cursor. The function is supposed to remove the current item. So, in my code there a few things that I am unsure about. For example, should I be creating a temporary node pointer that is for deleting the current item, or can I just delete the cursor node pointer? Also, in the else if statement I am not sure how to move the precursor back once after deleting a current item? Another thing that is giving me a hard time is not being able to read the debugger, so it is hard to test my logic. For example, in the autos window I can get a reading for tailPtr such as:

+tailPtr0x0081d708 {data=10 next=0x0081d698 {data=30 next=0x00000000 <NULL> } } cs_sequence::Sequence::Node *

I don't understand why a tailPtr to one node is giving 2 sets of data, and 2 sets of addresses. Seems like if a pointer is pointing to a node there should be 1 data, and 1 address.


The comments are guidelines given to me.

// Precondition: is_item returns true. 
// Postcondition: The current item has been removed from the Sequence. If the item removed 
// was the last item in the Sequence, then there is now no current item.  Otherwise, the item
// that was after the removed item is now the current item.
void Sequence::remove_current()
    {
            if (is_item())
            {
                Node* temp = nullptr;

                if (cursor == headPtr)  // If the item removed is the first item in the Sequence
                {
                    precursor = nullptr;
                    headPtr = headPtr->next;
                    temp = cursor;
                    cursor = cursor->next;
                    delete temp;
                }
                else if (cursor == tailPtr)   // If the item removed is the last item in the Sequence
                {                            // Figure out how to move precursor back one
                    temp = cursor;
                    cursor = nullptr;
                    tailPtr = precursor;
                    tailPtr = nullptr;
                    cursor = precursor;
                    delete temp;
                }
                else // If the item removed is in between head and tail;
                {
                    temp = cursor;
                    precursor->next = cursor->next;  
                    cursor = cursor->next;
                    delete temp;
                }
                numItems--;

            }
}

[salem c]

The debugger is "helpfully" showing you what tailPtr->next looks like without you having to physically type anything in.

[stoneJax]

There is no tailPtr->next in my code though. Also, since a tailPtr is to point at the end of the list, then there should be no such thing as tailPtr->next.

[salem c]

Well there's your problem then.

Apparently, your tailPtr is no longer pointing at the tail, because there IS a next after it.

[zapshe]

What exactly is the issue? How did you implement your linked list? Is it working as expected or not?

[jonnin]

lets take just the first one. you are not thinking through the cases and issues.
scenario: there is exactly 1 item in the list. head == tail, assuming you did that right. You want to delete it.

                    precursor = nullptr;    //this should not be necessary. what is the purpose of this statement?
                    headPtr = headPtr->next; //ok, head is now null. that is correct
                    temp = cursor;   // ok, temp is now old head, assuming cursor == head. 
                    cursor = cursor->next;  //ok, cursor is now null; 
                    delete temp;   //head is deleted. 
                      //what about tail? tail is now pointing to the deleted node and will give an 
                     //error when you access it.  

it looks correct if the list has more than 1 item.

I don't know what else may be going on in there, but every time you mess with the pointers in your list, you need to evaluate what happens to both head and tail for empty, one element, two element, and multi element lists. Two element may not be a special case with your approaches seen here, but at least test the code well on a 2 element list to be sure something elsewhere did not miss a scenario and bork up head & tail.

[dutch]

You don't need the separate cases and all that complexity.

    Node* next = cursor->next;

    if( precursor )
        precursor->next = next;
    else
        headPtr = next;

    delete cursor;

    cursor = next;

    if( !cursor )
        tailPtr = precursor;

    --numItems;

[jonnin]

^^ nice cleanup. I think it needs empty-list check (so next isnt blowup) but otherwise it really cuts it down.

[dutch]

I should've mentioned the precondition that curr cannot be null (which also implies that the list can't be empty). From our perspective, prev and curr are mysteriously set somewhere and then this function is called, so we need to trust that both of those are correct. We could add:

if( !cursor || (precursor && precursor->next != cursor) )
    // bad arguments 

Here's a complete program to play with:

#include <iostream>

struct Node
{
    int data;
    Node* next;

    Node( int d, Node* n = nullptr )
        : data( d ), next( n ) { }
};

// Remove curr from the list.
// precond: neither head, tail nor curr are null.
//          prev points to curr or is null if curr is head.
void remove( Node*& head, Node*& tail, Node* curr, Node* prev )
{
    Node* next = curr->next;

    if( prev )
        prev->next = next;
    else
        head = next;

    delete curr;

    curr = next;

    if( !curr )
        tail = prev;
}

void print( Node* nd )
{
    for ( ; nd; nd = nd->next)
        std::cout << nd->data << ' ';
    std::cout << '\n';
}

int main()
{
    Node *head = nullptr, *tail = nullptr;

    for( int n: { 1, 2, 3, 4, 5, 6, 7, 8 })
    {
        // prepend
        //head = new Node( n, head );
        //if( !tail ) tail = head;
        
        // append
        Node* nd = new Node( n );
        if( tail )
            tail->next = nd;
        else
            head = nd;
        tail = nd;
    }

    // Start curr at head...
    Node *curr = head, *prev = nullptr;
    // ... and advance n positions.
    int n = 3;
    for( int i = 0; curr && i < n; ++i )
    {
        prev = curr;
        curr = curr->next;
    }

    print( head );
    std::cout << "tail: " << (tail ? tail->data : -1) << '\n';

    if( curr )
        remove( head, tail, curr, prev );

    print( head );
    std::cout << "tail: " << (tail ? tail->data : -1) << '\n';
}

[stoneJax]

I had to tweak my function some plus add some code for another case. Definitely not as clean and elegant as yours but I am happy to get it working. I also appreciate your example to see and learn how much more efficiently it can be done. Thank you.