Linked List - some basic questions?

[dhayden]

Delete_At_n should delete the node so it doesn't leak memory. Also, it assumes that there are at least N items in the list which may be okay but it's the sort of thing that should be documented.

[Arslan7041]

Oh snap, I can't believe I forgot that!

So I guess a second temp variable is necessary then, so I can point it to the nth node and then free it.

Here is my updated Delete function:

void Delete_At_n(Node* &pToHead, int n)
{
    if(pToHead == 0)
        return;

    Node* temp = pToHead;

    if(n==1) // special case for deleting first node;
    {
        pToHead = temp->next; // point pToHead to wherever first node was linked to
        return;
    }

    for(int i=0; i<n-2; i++)   // go to n-1th node
    {
        temp = temp->next;
    }

    Node* temp2 = temp->next; // temp2 pointing to nth node
    temp->next = temp2->next; // point n-1th node to whatever nth node is pointing to
   
    delete temp2;



    return;
}

As for the second thing you mentioned, I understand, but right now I just want to get down the core concepts of linked lists. The codes im writing are simply to teach myself, so Im not really worried about error-handling right now. Im just assuming that a valid value of n is passed for the sake of simplicity.

Anything else that needs to be fixed?

[dhayden]

Anything else that needs to be fixed?

You're still leaking the memory. :)

[Arslan7041]

You're still leaking the memory. :)

Gah! Fixed.

[Arslan7041]

Function to reverse the list. It seems to work fine. Suggestions/criticisms are welcomed.

I called it "Reverse_Iterative" as I'll be writing another reverse function which will be recursive.

void Reverse_Iterative(Node* &pToHead)
{
    Node* current = pToHead; // set current node to whatever pToHead is pointing to
    Node* previous = 0, *next; // for storing the address of previous and next nodes
    while(current != 0)
    {
        next = current->next; // store address of next node
        current->next = previous; // point current node to previous node
        previous = current; // update previous to the current node
        current = next; // move current up to next node
    }
    pToHead = previous; // pToHead now points at what used to be the 'last' node, now making it the first
}

[Arslan7041]

So I found this recursive solution online. It works but Im confused because of the last line:

void Reverse_Recursive(Node*& pToHead)
{
  Node* rest = pToHead->next;
  if (pToHead == 0 || rest == 0) return;
  Reverse_Recursive(rest);
  pToHead->next->next = pToHead;
  pToHead->next = 0;
  pToHead = rest; // what does this do? How does rest change?
}

How does this work? I tried drawing a diagram and went though this code twice, but Im still left confused by the final line. It seems to mess up my understanding of whats going on. I think I may be severely misunderstanding what is happening to the rest pointer.

I understand recursion in that I know lines 6-8 are only executed once the base case condition is fulfilled, with each 'return' pointing p to the previous node. So thats not the issue here.

Any help?

[cire]

In order for the list to be reversed, the head pointer must point to the previously last node in the list.

Without line 8, that wouldn't happen. Keep in mind that rest will be pToHead in a recursive function call before line 8 is reached.