12 Replies - 2332 Views - Last Post: 10 April 2011 - 10:40 PM Rate Topic: -----

#1 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

double linked list problem in c

Posted 09 April 2011 - 08:11 PM

so basically this program takes in a char, stores it in a struct. and then has a pointer to the next structure to make it a linked list. im asked to change it to a double linked list so it can be navigated both ways. i already fixed the insert function, and added a print backwards function, both of which work.

now i am working on the delete function but no matter what how many things i try i always end up with pointers pointing to deleted nodes making errors in the memory. uhh, i honestly understand what i have to do and how to code it, but i cant figure out where to update the pointers at.

sorry for the wall of text, code is below: delete function is commented and is near the bottom



#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

struct listNode {
       char data;
       struct listNode *nextPtr;
       struct listNode *prevPtr;
       };
       
       typedef struct listNode ListNode;
       typedef ListNode *ListNodePtr;
       
       void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value );
       char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value);
       int isEmpty( ListNodePtr sPtr);
       void printList( ListNodePtr currentPtr );
       void printBack( ListNodePtr currentPtr );
       void instructions(void );

int main(int argc, char *argv[])
{
    ListNodePtr startPtr=NULL;
	ListNodePtr tailPtr=NULL;
    int choice;
    char item;
    
    instructions();
    printf("? ");
    scanf("%d", &choice);
    
    while(choice !=3){
                 switch(choice){
                                case 1:
                                     printf("Enter a character: ");
                                     scanf("\n%c", &item);
                                     insert(&startPtr, &tailPtr, item);
                                     printList(startPtr);
									 printBack(tailPtr);
                                     break;
                                case 2:
                                     if(!isEmpty(startPtr)){
                                                           printf("Enter a character to be deleted: ");
                                                           scanf("\n%c", &item);
                                                           if(deletechar(&startPtr, &tailPtr, item)){
                                                                                    printf("%c deleted.\n", item);
                                                                                    printList(startPtr);
                                                                                    printBack(tailPtr);
                                                                                    }
                                                           else{
                                                                printf("%c not found.\n\n", item);
                                                                }
                                                           }
                                     else{
                                          printf("List is empty.\n\n");
                                          }
                                          break;
                                     default:
                                             printf("invalid choice. \n\n");
                                             instructions();
                                             break;
                                          }
                                printf("? ");
                                scanf("%d", &choice);
                                }
                 printf("end of run.\n");
                 return 0;
}

void instructions(void){
     printf("Enter your choice:\n"
     "       1 to insert an element into the list.\n"
     "       2 to delete an element from the list.\n"
     "       3 to end.\n");
     }
     
void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
     ListNodePtr newPtr;
     ListNodePtr previousPtr;
     ListNodePtr currentPtr;
     
     newPtr = (ListNodePtr)malloc( sizeof( ListNode ) );
     
     
     if(newPtr!=NULL){
		  newPtr->data=value;
		  newPtr->nextPtr=NULL;
		  previousPtr=NULL;
		  currentPtr=*sPtr;
		  newPtr->prevPtr=NULL;
                      
          while(currentPtr !=NULL&&value > currentPtr->data){
                           previousPtr=currentPtr;
                           currentPtr=currentPtr->nextPtr;
		  }
		  if(previousPtr==NULL){  // inserted at beginning of list
			newPtr->nextPtr=*sPtr;
			*sPtr=newPtr;

			*tPtr=newPtr;
		  }
			else{
	           
				 if(currentPtr!=NULL){ // inserted in the middle

					 previousPtr->nextPtr=newPtr;
					 newPtr->nextPtr=currentPtr;

					 currentPtr->prevPtr=newPtr;
					 newPtr->prevPtr=previousPtr;
				 }
				 else{//inserted at end of list
					 *tPtr=newPtr;
					  previousPtr->nextPtr=newPtr;
					  newPtr->prevPtr=previousPtr;
				 }
			}
	 }
	 else{
		printf("%c not inserted. no memory available.\n", value);
		 }
}
             
     char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
          
   ListNodePtr previousPtr; /* pointer to previous node in list */
   ListNodePtr currentPtr; /* pointer to current node in list */
   ListNodePtr tempPtr; /* temporary node pointer */
   


   /* delete first node */
   if ( value == ( *sPtr )->data ) { 
      tempPtr = *sPtr; /* hold onto node being removed */
      *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
      free( tempPtr ); /* free the de-threaded node */
      
      //*tPtr=NULL; not sure if this needs a if statement...or what??
      return value;
       } /* end if */

   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;

      
      /* loop to find the correct location in the list */
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr; /* walk to ...   */
         currentPtr = currentPtr->nextPtr; /* ... next node */  
      } /* end while */

      /* delete node at currentPtr */
      if ( currentPtr != NULL ) { 
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         
         
         //previousPtr->prevPtr = currentPtr->prevPtr; this should be correct as well, but its not working bc i think im missing something
         

         free( tempPtr );
         return value;
      }/* end if */

   } /* end else */

   return '\0';
} /* end function delete */

          
          
     int isEmpty(ListNodePtr sPtr){
         return sPtr==NULL;
         }
         
     void printList(ListNodePtr currentPtr){
          if(currentPtr==NULL){
                               printf("List is empty.\n\n");
          }
          else{
               printf("the list is:\n");
                                                             
                               while(currentPtr !=NULL){
                                                printf("%c --> ", currentPtr->data );
                                                currentPtr=currentPtr->nextPtr;
                               }
                                                printf("NULL\n\n");
          }
      }
	  void printBack(ListNodePtr currentPtr){
          if(currentPtr==NULL){
             printf("List is empty.\n\n");
          }
          else{
             printf("the list in reverse is:\n");                   
             while(currentPtr !=NULL){
                printf("%c --> ", currentPtr->data );
                currentPtr=currentPtr->prevPtr;
             }
             printf("NULL\n\n");
		  }
      }
                                                      
     


Is This A Good Question/Topic? 0
  • +

Replies To: double linked list problem in c

#2 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 09 April 2011 - 08:57 PM

You overlooked a few aspects of the delete operation. I added some comments to your delete code -- if you deal with those items correctly that should straighten things out:

char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){

    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */
    ListNodePtr tempPtr; /* temporary node pointer */

    /*!        first make sure list isn't already empty           */

    /*!   before delete first node, make sure it isn't also the last node */
    
    /* delete first node */
    if ( value == ( *sPtr )->data ) {
        tempPtr = *sPtr; /* hold onto node being removed */
        *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
        free( tempPtr ); /* free the de-threaded node */

        /*!         need to set (*sPtr)->prevPtr             */
        
        return value;
    } /* end if */

    else {
        previousPtr = *sPtr;
        currentPtr = ( *sPtr )->nextPtr;


        /* loop to find the correct location in the list */
        while ( currentPtr != NULL && currentPtr->data != value ) {
            previousPtr = currentPtr; /* walk to ...   */
            currentPtr = currentPtr->nextPtr; /* ... next node */
        } /* end while */

        /*!   check to see if current node is last node        */
        
        /* delete node at currentPtr */
        if ( currentPtr != NULL ) {
            tempPtr = currentPtr;
            previousPtr->nextPtr = currentPtr->nextPtr;

        /*! the following line is not correct -- think about it: currentPtr->prevPtr *IS* previousPtr */
        /*! if you are deleting currentPtr, which node's prevPtr do you have to reset????             */
            //previousPtr->prevPtr = currentPtr->prevPtr; 


            free( tempPtr );
            return value;
        }/* end if */

    } /* end else */

    return '\0';
} /* end function delete */


Was This Post Helpful? 1
  • +
  • -

#3 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

Re: double linked list problem in c

Posted 09 April 2011 - 09:00 PM

^^thanks for your time ill try to implement that and ill let u know if have any further questions.
Was This Post Helpful? 0
  • +
  • -

#4 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

Re: double linked list problem in c

Posted 09 April 2011 - 10:27 PM

okay, i tried to make some changes here are some problems

+ it is deleting the node, but still having memory issues
+ if you delete the node from the middle like a->b->c, delete b you make a infinite loop

updated code: w/ new comments

     char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
          
   ListNodePtr previousPtr; /* pointer to previous node in list */
   ListNodePtr currentPtr; /* pointer to current node in list */
   ListNodePtr tempPtr; /* temporary node pointer */
   
   
   
//in the main fucntion it checks to see if list is empty

   /* delete first node */
   if ( value == ( *sPtr )->data ) {
        if(currentPtr=NULL){//checks make sure start pointer != tail pointer
                            *tPtr=NULL;
                            }//end if
        else{
      tempPtr = *sPtr; /* hold onto node being removed */
      *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
      free( tempPtr ); /* free the de-threaded node */
      
      *tPtr = (*tPtr)->prevPtr;//i think you meant tPtr not sPtr?
      return value;
       }//end else
  } /* end if */

   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;

      
      /* loop to find the correct location in the list */
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr; /* walk to ...   */
         currentPtr = currentPtr->nextPtr; /* ... next node */  
      } /* end while */

      /* delete node at currentPtr */
      if ( currentPtr != NULL ) { //this shouldnt run if its the last node?
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         
         currentPtr->prevPtr=previousPtr->nextPtr;//i think this makes more sense then?
         
         free( tempPtr );
         return value;
      }/* end if */
      else{
           *tPtr=previousPtr;
      }
         

      

   } /* end else */

   return '\0';
} /* end function delete */




once again, thanks for your help man, this is the first thing in c that has given me trouble.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5795
  • View blog
  • Posts: 12,627
  • Joined: 16-October 07

Re: double linked list problem in c

Posted 10 April 2011 - 04:10 AM

This is C++? Your list should be it's own class. Also, typedefing to pointers is messy. If you're going to write a C program in C++, why bother with C++ at all?

Looking at your C program, you're keeping a head and a tail. Why? Even in your C program, you'd do better with a struct for the list.
e.g.
typedef struct listNode {
	char data;
	struct listNode *prev, *next;
} Node;

typedef struct {
	Node *head, *tail;
} List;

void insert(List *, char);
char deletechar(List *, char);
int isEmpty(const List *);



At which point, it's a short trip to an actual C++ program:
class List {
private:
	struct Node {
		char data;
		Node *prev, *next;
		Node(char d, Node *p, Node *n) : data(s), prev(p), next(n) { }
	};
	Node *head, *tail;
public:
	List(): head(NULL), tail(NULL) { }
	~List();
	void insertChar(char);
	char deleteChar(char);
	bool isEmpty() const;
	void printList() const;
	void printBack() const;
};


Was This Post Helpful? 1
  • +
  • -

#6 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 10 April 2011 - 07:23 AM

View Poststeelers1377, on 10 April 2011 - 12:27 AM, said:

okay, i tried to make some changes here are some problems

+ it is deleting the node, but still having memory issues
+ if you delete the node from the middle like a->b->c, delete b you make a infinite loop

updated code: w/ new comments


I added some comments to your comments:

char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){

    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */
    ListNodePtr tempPtr; /* temporary node pointer */



//in the main fucntion it checks to see if list is empty
    /*! why not: if( *sPtr == NULL ) return '\0';    */

    /* delete first node */
    if ( value == ( *sPtr )->data ) {
    /*! you haven't assigned any value to currentPtr yet
     *  maybe you meant *sPtr ?     */
        if (currentPtr=NULL){//checks make sure start pointer != tail pointer
            *tPtr=NULL;
        }//end if
    /*! you haven't deleted anything yet, so "else" doesn't belong here */
        else{
            tempPtr = *sPtr; /* hold onto node being removed */
            *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
            free( tempPtr ); /* free the de-threaded node */

            *tPtr = (*tPtr)->prevPtr;//i think you meant tPtr not sPtr?
            /*! no, I meant that you have to set the "new" (*sPtr)'s prev->Ptr (to what?) */
            return value;
        }//end else
    } /* end if */

    else {
        previousPtr = *sPtr;
        currentPtr = ( *sPtr )->nextPtr;


        /* loop to find the correct location in the list */
        while ( currentPtr != NULL && currentPtr->data != value ) {
            previousPtr = currentPtr; /* walk to ...   */
            currentPtr = currentPtr->nextPtr; /* ... next node */
        } /* end while */

        /* delete node at currentPtr */
        if ( currentPtr != NULL ) { //this shouldnt run if its the last node?
            /*! if currentPtr is the last node you also have to set *tPtr */
            tempPtr = currentPtr;
            previousPtr->nextPtr = currentPtr->nextPtr;

            currentPtr->prevPtr=previousPtr->nextPtr;//i think this makes more sense then?
            /*! you are about to free currentPtr, so why would you want to change
             *  one of its fields?  But you do have to set the "previous" pointer
             *  of the node that follows the one that's being deleted, assuming 
             *  you aren't deleting the last node */

            free( tempPtr );
            return value;
        }/* end if */
        else{
            *tPtr=previousPtr;
        }




    } /* end else */

    return '\0';
} /* end function delete */



Was This Post Helpful? 1
  • +
  • -

#7 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

Re: double linked list problem in c

Posted 10 April 2011 - 01:22 PM

View Postr.stiltskin, on 10 April 2011 - 07:23 AM, said:

I added some comments to your comments:



okay, i attached a paint picture i made of what i think is happening with the pointers, if its right then the it just looks like i need to update prevPtrs->previous to the next node after the deleted node but i dont know how to access that since there is only previous and current?

o and for *sPtr->prevPtr=? that should just be the next pointer in the list going forward, so previousPtr->prevPtr but that doesnt seem to be working. but that could just be bc the above line isnt fixed yet.

char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
          
   ListNodePtr previousPtr; /* pointer to previous node in list */
   ListNodePtr currentPtr; /* pointer to current node in list */
   ListNodePtr tempPtr; /* temporary node pointer */
   
   if( *sPtr == NULL ){//checks to see if list is empty
       return '\0';
       }
       
   if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
      *tPtr=NULL;
   }
     
   
   
   /* delete first node */
   if ( value == ( *sPtr )->data){
      tempPtr = *sPtr; /* hold onto node being removed */
      *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
      free( tempPtr ); /* free the de-threaded node */
      
     // (*sPtr)->prevPtr=
      return value;
  } /* end if */

   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;

      
      /* loop to find the correct location in the list */
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr; /* walk to ...   */
         currentPtr = currentPtr->nextPtr; /* ... next node */  
      } /* end while */

      /* delete node at currentPtr */
      if ( currentPtr != NULL ) { 
           
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         
        previousPtr->prevPtr= previousPtr->nextPtr;
         
         free( tempPtr );
         return value;
      }/* end if */
      else{
           *tPtr=previousPtr;
      }
         

      

   } /* end else */

   return '\0';
} /* end function delete */

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#8 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 10 April 2011 - 03:00 PM

View Poststeelers1377, on 10 April 2011 - 03:22 PM, said:

okay, i attached a paint picture i made of what i think is happening with the pointers, if its right then the it just looks like i need to update prevPtrs->previous to the next node after the deleted node but i dont know how to access that since there is only previous and current?


Your picture is correct but your code isn't implementing that.

After you set
previousPtr->nextPtr = currentPtr->nextPtr; (line 42 of your latest code)
previousPtr points to the node on the left and previousPtr->nextPtr points to the node on the right, so let's stick to those "names". Now, to create that arrow that goes from the node on the right to the node on the left, which pointer of which node do you have to reset (and which node should it now point to)?


And this:

Quote

11 if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
12 *tPtr=NULL;
13 }
is misplaced. You should be doing that only if you are in fact deleting the first node. As it now stands, you are doing that whenever there is only 1 node in the list, regardless of whether or not it matches the value to be deleted.

And

Quote

o and for *sPtr->prevPtr=? that should just be the next pointer in the list going forward, so previousPtr->prevPtr but that doesnt seem to be working. but that could just be bc the above line isnt fixed yet.
if previousPtr was the node that preceded the deleted node, isn't it still the node that will precede the node that "replaces" the deleted node? previousPtr, not previousPtr->prevPtr!!

And remember, if you delete the first node (and it wasn't the only node in the list), you have to reset the prevPtr of the new first node. Since it is now the first node, what should its prevPtr point to?
Was This Post Helpful? 1
  • +
  • -

#9 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

Re: double linked list problem in c

Posted 10 April 2011 - 04:44 PM

omg it shouldnt take me this long to understand how to code a freakin double linked list.....

so


      if ( currentPtr != NULL ) {  
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         
         previousPtr->nextPtr=previousPtr; //if previousPtr->nextPtr is the node on the right and previousPtr is the node on the left, this 
         //should set the node on the left equal to the node on the right?
         
         free( tempPtr );
         return value;
      }/* end if */




and

(*sPtr)->prevPtr = previousPtr; //isnt this setting the *sPtr of prevPtr to the node preceding it like you said?


Was This Post Helpful? 0
  • +
  • -

#10 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 10 April 2011 - 06:54 PM

OK, I can't keep this up all night.

currentPtr->nextPtr was the node on the right, n'cest pas?
So after you do this
if ( currentPtr != NULL ) {  
   tempPtr = currentPtr;
   previousPtr->nextPtr = currentPtr->nextPtr;

isn't previousPtr->nextPtr also the node on the right?

So now you need to make that node's prevPtr point to "the one on the left", which is still previousPtr.

So:
previousPtr->nextPtr->prevPtr = previousPtr;
Was This Post Helpful? 1
  • +
  • -

#11 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 10 April 2011 - 07:00 PM

And here I believe you are still referring to the part of the code that delete the first node, correct? So, assuming that *sPtr has already been set to point to the new first node,,,

Quote

(*sPtr)->prevPtr = previousPtr; //isnt this setting the *sPtr of prevPtr to the node preceding it like you said?

is wrong because there is no previous node. You should be setting the first node's prevPtr to NULL.
Was This Post Helpful? 1
  • +
  • -

#12 steelers1377  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 09-April 11

Re: double linked list problem in c

Posted 10 April 2011 - 07:38 PM

okay okay i see it now, i didnt realize you could point from previousPtr->nextPtr->prevPtr, i also fixed the first if statement when deleting the first and ONLY node. so program is 100% thanks to you. im sorry it kept going back and forth and took soo long and you probably regret helping me but thanks.
Was This Post Helpful? 0
  • +
  • -

#13 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: double linked list problem in c

Posted 10 April 2011 - 10:40 PM

Not at all. I'm glad you finally got it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1