Thread: Linked lists

  1. #1
    Registered User
    Join Date
    Aug 2006

    Linked lists

    Hi - i just needed some help. I'm constructing a circular linked list which means 1st node points to 2nd, and so on. The task i need to accomplish is that i need to remove one node (any node in the linked list). So lets say i have 8 nodes in my circular linked list and i want to remove the 4th node. We know that the 4th node points to the 5th node. Anyway, my current function has no problem with deleting any node except for the 2nd no. No matter what I try to do, I cannot delete the 2nd node. Here is my function: Im sorry if there isn't enough info here, but you can ask and i'll be happy to reply back. Thanks.

    node* prev = current; // current is the head of the linked list  im making a pointer prev to 			//also point to head
    node* cur; // just another pointer
     cur = prev;  // let cur also point to the head of the linked list
     for (int i=1; i <= size(); i++) // size is the size of the linked list
     if (prev -> num == x ) // x is the node I want to delete  so if the first node contains the                  //data (num is the data field of the node)  then do the following
      cur -> shortlink = prev -> shortlink ;
      delete cur;
      cur = prev;
      prev = prev -> shortlink;

  2. #2
    Registered User
    Join Date
    May 2006
    Berkshire, UK
    Just to be clear, when you say circular, do you mean that the last node points to the first?
    I am not quite clear what you are trying to do with your code... do you manage the garbage collection yourself? i.e. if there is clear space in the list do you release it for reuse?

    The obvious approach for deletion is to move to the element you want to delete. Make the next pointer of the previous element equal the next pointer of the element to be deleted and then make the previous pointer of the next element equal the previous pointer of the element to be deleted. Finally you need to clear up the element you are deleting (delete it or flag the memory as being available - we are back to garbage collection here).

    Why not create a class that cleans itself up? Or, if this is for a real-world situation, rather than some kind of assignment, save youself a lot of trouble and use the STL and maybe avoid linking the list altogether? What are your aims?

  3. #3
    Registered User
    Join Date
    May 2003
    1. A circular linked list has no head.
    2. What happens in your code if the node pointed at by current is deleted? current then points to a node that is no longer within the linked list.
    3. Why do you need to make your own linked list? C++ has a built in linked list type you can use, std::list.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  4. #4
    C / C++
    Join Date
    Jan 2006
    The Netherlands
    Quote Originally Posted by Cat
    3. Why do you need to make your own linked list? C++ has a built in linked list type you can use, std::list.
    That's called: practice

    Edit: or homework assignment
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand


    Whilst it is true that the C++ std library does not provide a ring-list (one where you can never step off the end because you land back on the start), you can implement one using a std::list by overloading the ++ and -- operators to wrap back to begin or rbegin when you reach the end. You would also need to override begin and rbegin which would use a new member variable to remember where to start.
    Granted, it wont quite be as efficient... but it'll be more useful and less buggy.

    You'd certainly want to avoid passing it to function like for_each though, for example!

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