Thread: Linked List problem

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    1

    Linked List problem

    I need some help in writting a linked list program. The program I have to write has six nodes a-f. and I have delete the third node in the list and then show the list again missing the third node. I know how delete tails and headers but can't figure this out. Please help.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Location
    Fiji
    Posts
    212
    Well first is it a doubly-linked list or singly-linked list?

    Then when in doubt draw a picture. What I mean by this is, draw a box, this represents a node. So you need six boxes.

    Then draw arrows to connect the boxes, these are your pointers.

    This is a start. Go From there.

    kwigibo

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    95
    if its a single linked list, then you really need a temp pointer, so that once your one link away from the one you delete you would do:
    tempptr = node->next;
    node->next=node->next->next;
    free(tempptr);
    this way you link the list around the one you got rid of then free up the memory. But i think kwigibo's answer of drawing boxes will help the most, making sure that each box will disappear unless something is holding onto it (ie a pointer), see if you were to use the above without the tempptr then you would have waisted memory until the program exits.
    Hope this helps

  4. #4
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    Let's say you have a list looking like this:

    NODE_A --> NODE_B --> NODE_C ...

    and you want to delete NODE_B.

    The crucial point here is not to forget to link nodes A and C BEFORE you erase node B.

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    This is pretty easy to do:
    Code:
    typedef struct NodeStruct
    {
        int iData;
        struct NodeStruct* pNext;
    } NodeType;
    
    NodeType* DeleteNode( NodeType* pCurrNode, int iValue )
    {
        NodeType* pTemp;
        if( pCurrNode == NULL ) return NULL;
        else if( --iValue < 0 ) return pCurrNode;
        else if( iValue == 0 )
        {
            pTemp = pCurrNode->pNext;
            free( pCurrNode );
            return pTemp;
        }
        else
        {
            pCurrNode->pNext = DeleteNode( pCurrNode->pNext, iValue );
            return pCurrNode;
        }
    }
    If you have your list ready to go with a pointer to the head of the list pHead then you just do this to delete the #3 node:

    Code:
        pHead = DeleteNode( pHead, 3 );
    Replace the 3 with whatever number to delete that particular node. Any value passed into the DeleteNode function less than 1 will have no effect on the list. Values greater than the number of nodes in the list will similarly have no effect on the list.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    95
    another way without using a recursive function is:

    Code:
    typedef struct NodeStruct
    {
        int iData;
        struct NodeStruct* next;
    } NodeType;
    
    int DeleteNode(NodeType **mainlist, int value)
    {
      int counter=0;
      NodeType *tempptr, *tempptr2;
    
      if(*mainlist == NULL)
        return 2;     // LIST IS EMPTY
      else
      {
        tempptr = *mainlist;
        while((counter<(value-1)) && (tempptr->next!=NULL))
        {
          tempptr=tempptr->next;
          counter++;
        }
        if(tempptr->next==NULL)
          return 1;     // NUMBER DOESNT EXIST
        else
        {
          tempptr2 = tempptr->next;
          tempptr->next = tempptr->next->next;
          free(tempptr2);
        }
      }
    }
    but either one will work (think mine works, havent tested it).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM