Linked lists...fun!

Alright, I've got a nice linked list going on...but I've come to a problem. I created a SLL (singly linked list) and all is good except that I can't figure out how to delete a node from the middle of the list. I figure I would go about it by setting the pNext of the node before the one I wish to delete to the address of the node after the one I wish to delete. However, is there a simple way of getting the previous node in the list without creating a DLL (doubly-linked list) or would I just be better off doing the extra work to make a DLL? I figure I could work in some static variables or so that I could store the soon-to-be deleted node's address in and then restart the traversing of the list until pNext is the address of the node I am deleting, but that's a pain. Any ideas or suggestions are appreciated. Just hoping some of you out there with linked list experience might have come across this and have a fabulous solution. Thanks in advance! :D

In general, there is no simple way to delete a node in the midle of a singly linked list. Doubly linked lists are best for that.

However, one solution (other that traversing all the way through the list up until the node before the one you are deleting), is to make a structure which holds both a node pointer and a pointer to the previous node (the previous node is updated every time you advance in the list). The only thing you want the "previous node" pointer for is for when you delete the current node. Make a member function for that new structure for deleting the node. It should set the previous node's next pointer to the current nodes next pointer, and delete the current node (maybe set the new current node in that structure to the next node... if there is one).

But even that has quite a few problems -- for instance:

let's say you had two of those "train" structures going at once. They are now one behind the other -- you delete the one that's behind.

See the problem? Now the "train" in front's "previous" pointer points to deallocated memory.

So what it comes down to is you can use that method, but not in all circumstances. If you really want a 100% safe way of doing it, then use a doubly-linked list. Only do a solution like the one I mentioned if it's really impotant for your list to take up less memory and if you only have to delete nodes in isolated areas of code.

I thought that DLLs were exactly the same as a SLL with the added pointer to the previous node's address? From what I get, you said I could either create a DLL or add a pointer to the previous node's address to my structure. What's the difference? Thanks.

The "previous node" pointer I'm suggesting would not be a part of the node.

All of your nodes still solely have a "next" pointer, however, make a structure which has 2 members: a pointer to a node in the list and a pointer to the previous node. Use instances of that structure to traverse through the list when you want to delete nodes.

Get it? So every node still has no "previous pointer" but your "train" has a previous pointer. Again, this comes with the problems that I mentioned above, which are solved with a doubly linked list, but in many circumstances this solution works fine, but not always, as I mentioned above.

If you are using a SLL and want to delete a node in the middle say then, you have to have a pointer to the previous node (create a member-function for this purpose). This is neccesary or else you will "lose" the link.

To the question about DLL you must ask yourself if it neccesary to have some extra operation i.e. traverse backwards in the list. Also remember that a DLL is twice larger (in terms of link-pointers) and a little slower(needs to link an extra poniter). This might not seen as a problem but when you have many entries in the list this can slow down the program, but in general this isn´t an issue.

If you want to be on the "safe side" you will go for DDL, I would :).

Thanks the the advice guys...I guess I'll just convert it over to a DLL. Thanks again!

Ok, I converted my SLL into a DLL. However, this is the first time I have created a DLL and I was hoping I could get some advice on my node deletion code...The code I have works, but for some reason it seems sloppy. Here is what I have:

Code:

---

void BankAccount::DeleteAccount()
{
        if(pPrev == 0) // first node
        {
                pFirst = pNext;
                pFirst->SetPrev(0);
        }
        else if(pNext == 0) // last node
        {
                BankAccount *pBA;
                pBA = pPrev;
                pBA->SetNext(0);
        }
        else // somewhere in the middle
        {       
                BankAccount *pBA;
                BankAccount *pBA2;
                pBA = pPrev;
                pBA2 = pNext;
                pBA->SetNext(pNext);
                pBA2->SetPrev(pPrev);
        }
        return;
};

---

I just put it together using logic, so I'm sure there is a more efficient way of doing it. If you have any suggestions, let me know. Thanks.

Why can't you do something like this for a single linked list:

Code:

---

while (cptr->next!=searchNode || cptr->next!=NULL)
  cptr=cptr->next;

node *delNode=cptr->next;
if (delNode==NULL)
  return;

cptr->next=cptr->next->next;
delete delNode;

---

you don't take into account the fact that it might have both the next AND previous node pointers set to 0.

Also, you might want to just make a templated linked list class (or use the STL, but I'm assuming you are doing this to learn, not to just "get it done").

Quote:

---

Originally posted by PJYelton
Why can't you do something like this for a single linked list:

Code:

---

while (cptr->next!=searchNode || cptr->next!=NULL)
  cptr=cptr->next;

node *delNode=cptr->next;
if (delNode==NULL)
  return;

cptr->next=cptr->next->next;
delete delNode;

---

---

We've mentioned that. You don't want to do it usually because in a long list, that's a horrible waste of time. You don't want to have to search through the entire list every time you delete a node in most circumstances.

EDIT: also, in your code, you wanted && not || and you might as well just use
cptr->next = delNode->next;
delete delNode;
for that last part.

Quote:

---

Originally posted by Polymorphic OOP
you don't take into account the fact that it might have both the next AND previous node pointers set to 0.

---

Yeah, I noticed that right after I posted my code when I tried deleting the only node left :p Thanks for the help guys.

Oops, you are right, you did mention tranversing the whole list and I did mean && :D

Most of my linked list work deals with finding and deleting a node, which unless they are sorted I'm not sure how to do any other way than tranversing.