Thread: Linked lists...fun!

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    7

    Talking 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!

  2. #2
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.
    Last edited by Polymorphic OOP; 01-05-2003 at 03:09 PM.

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    7

    Ok, so what exactly is a DLL?

    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.

  4. #4
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.

  5. #5
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    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 .

  6. #6
    Registered User
    Join Date
    Jan 2003
    Posts
    7
    Thanks the the advice guys...I guess I'll just convert it over to a DLL. Thanks again!

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    7

    Just need some help

    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.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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;

  9. #9
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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").

  10. #10
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.
    Last edited by Polymorphic OOP; 01-05-2003 at 04:15 PM.

  11. #11
    Registered User
    Join Date
    Jan 2003
    Posts
    7
    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 Thanks for the help guys.

  12. #12
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Oops, you are right, you did mention tranversing the whole list and I did mean &&

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM