Doubly Linked List

What am I doing wrong?

Page 1 of 1

2 Replies - 11441 Views - Last Post: 15 April 2006 - 08:22 PM Rate Topic: -----

#1 sufistuk8ed  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 15-April 06

Doubly Linked List

Posted 15 April 2006 - 06:50 PM

Hello everyone, I can't figure out what I am doing wrong with this program... It asks the user to either insert or delete a character into/from the list. After each insertion or deletion, it should print the list forwards and then print it backwards, in alphabetical order. I'm not getting any compiler errors or warnings, but I get a run time error when it tries to print the list backwards. Could someone please take a look at my code? Oh, and it is in C.

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

/* self-referential structure */
struct listNode 
{            
   char data; /* each listNode contains a character */
   struct listNode *nextPtr; /* pointer to next node*/
   struct listNode *prevPtr; /* pointer to previous node*/
}; /* end structure listNode */


typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */

/* prototypes */
void insert(ListNodePtr *sPtr, char value);
char delete(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printBackwards(ListNodePtr currentPtr);
void instructions(void);

int main()
{ 
   ListNodePtr startPtr = NULL; /* initially there are no nodes */
   int choice; /* user's choice */
   char item;  /* char entered by user */

   instructions(); /* display the menu */
   printf("? ");
   scanf("%d", &choice);

   /* loop while user does not choose 3 */
   while (choice != 3) 
   { 
      switch (choice) 
   { 
         case 1:
            printf("Enter a character: ");
            scanf("\n%c", &item);
            insert(&startPtr, item); /* insert item in list */
            printList(startPtr);
            break;

         case 2:
            /* if list is not empty */
            if (!isEmpty(startPtr)) 
 	 { 
               printf("Enter character to be deleted: ");
               scanf("\n%c", &item);

               /* if character is found, remove it */
               if (delete(&startPtr, item)) 
      { /* remove item */
                  printf("%c deleted.\n", item);
                  printList(startPtr);
               } /* end if */

               else 
      {
                  printf("%c not found.\n\n", item);
               } /* end else */

            } /* end if */
            else 
 	 {
               printf("List is empty.\n\n");
            } /* end else */

            break;

         default:
            printf("Invalid choice.\n\n");
            instructions();
            break;
      } /* end switch */

      printf("\n? ");
      scanf("%d", &choice);
   } /* end while */

   printf("End of run.\n");
   
   return 0; /* indicates that program ended successfully */

} /* end main */

/* display program instructions to user */
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");
} /* end function instructions */

/* Insert a new value into the list in sorted order */
void insert(ListNodePtr *sPtr, char value)
{ 
   ListNodePtr newPtr;      /* pointer to new node */
   ListNodePtr currentPtr;  /* pointer to current node in list */
   ListNodePtr prevPtr;  /* pointer to previous node in list */

   newPtr = malloc(sizeof(ListNode)); /* create node */

   if (newPtr != NULL)  /* is space available */
   {
      newPtr->data = value; /* place value in node */
      newPtr->nextPtr = NULL; /* node does not link to another node */

      prevPtr = NULL;
      currentPtr = *sPtr;

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

      /* insert new node at beginning of list */
      if (prevPtr == NULL) 
   { 
         newPtr->nextPtr = *sPtr;
         *sPtr = newPtr;
      } /* end if */

      else 
   { /* insert new node between previousPtr and currentPtr */
         prevPtr->nextPtr = newPtr;
         newPtr->nextPtr = currentPtr;
      } /* end else */
   
   } /* end if */
   else 
   {
      printf("%c not inserted. No memory available.\n", value);
   } /* end else */

} /* end function insert */

/* Delete a list element */
char delete(ListNodePtr *sPtr, char value)
{ 
   ListNodePtr prevPtr; /* 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 */
      return value;
   } /* end if */
   else 
   { 
      prevPtr = *sPtr;
      currentPtr = (*sPtr)->nextPtr;

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

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

   return '\0';

} /* end function delete */

/* Return 1 if the list is empty, 0 otherwise */
int isEmpty(ListNodePtr sPtr)
{ 
   return sPtr == NULL;

} /* end function isEmpty */

/* Print the list */
void printList(ListNodePtr currentPtr)
{ 
   /* if list is empty */
   if (currentPtr == NULL) 
   {
      printf("List is empty.\n\n");
   } /* end if */
   else 
   { 
      printf("\nThe list is:\n");

      /* while not the end of the list */
      while (currentPtr != NULL) 
   { 
         printf("%c --> ", currentPtr->data);
         currentPtr = currentPtr->nextPtr;   
      } /* end while */

      printf("NULL\n");

   printBackwards(currentPtr);
   } /* end else */

} /* end function printList */

/* Print the list backwards */
void printBackwards(ListNodePtr currentPtr)
{ 
   printf("The list backwards is:\n");

   while (currentPtr->nextPtr != NULL) 
   {
     currentPtr = currentPtr->nextPtr;

  while (currentPtr != NULL)
  { 
 	 printf("%c --> ", currentPtr->data);
 	 currentPtr = currentPtr->prevPtr;   
  } 
   } /* end while */

} /* end function printBackwards */



Is This A Good Question/Topic? 0
  • +

Replies To: Doubly Linked List

#2 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: Doubly Linked List

Posted 15 April 2006 - 08:20 PM

I'm not near a compiler at the moment, so I can't really test and comment with any authority (maybe someone near a compiler can do so), but it looks as if you call the reverse print function when currentPtr has a value of null...and accessing it results in a segmentation fault.
Was This Post Helpful? 0
  • +
  • -

#3 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 204
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Doubly Linked List

Posted 15 April 2006 - 08:22 PM

Just because the code is syntactically correct (doesn't have errors on compiling/linking) doesn't mean the code is correct.

Your code has a lot of comments... which can be a bad thing when all they do is describe the method name (eg: unnecessary commenting just clutters the code making it harder for others to read) making the code longer than it needs to be.

the double while loop in print backwards is redundant as they both have the same condition, simply do the print first then update the pointer.
(Also with this code you are moving your pointer backwards twice, once per loop)

As for your question, the reason the code does not work at run time, is:
1) your while loop is using currentPtr->nextPtr instead of currentPtr->prevPtr
2) since the head of this linked list is never null, you will need another condition to stop the loop (when it reaches the first node, it does not have a data section, and thus results in another error.
A linked list should have a head pointer within the class that points to the first node (a double linked list usually has a tail pointer as well)
3) when you print the list forward it stops when currentPtr becomes null, thus the value passed to print backwards is also null, and would also generate the error

All of these problems revolve around the single while loop in print backwards, and all can be solved with minimal changes (following my advice on syntax of your while loops) and by adding a head pointer

Hopefully you can figure it out on your own, you have done a decent job so far, so i think you can. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1