Doubly Linked List - C

print backwards doubly linked list

Page 1 of 1

1 Replies - 5205 Views - Last Post: 02 November 2010 - 08:54 AM Rate Topic: -----

#1 dp-14  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 14-September 10

Doubly Linked List - C

Posted 02 November 2010 - 08:16 AM

I'm working on this Doubly linked list trying to get it to print backwards. I've seen old topics where they say you need to put in a head pointer in order to get it to print in reverse but I'm not sure where/how to implement it? The area that I'm having trouble with is the second while in the print function. Thanks in advance




#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 *previousPtr;
}; /* 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 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 previousPtr;  /* pointer to previous node in list */
   ListNodePtr currentPtr;  /* pointer to current node in list */

newPtr = (ListNode*)malloc(sizeof(ListNodePtr));

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

      previousPtr = NULL;
      currentPtr = *sPtr;

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

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

      else { /* insert new node between previousPtr and currentPtr */
         previousPtr->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 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){ 
        *sPtr = (*sPtr)->nextPtr; /* de-thread the node */
      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;
         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)
{ listNode *startPtr=NULL;
ListNodePtr previousPtr;
   /* 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\n");
   } /* end else */
	
 struct listNode *temp = NULL;
   while (currentPtr == NULL){
	   temp = currentPtr -> previousPtr;
	   currentPtr->previousPtr = currentPtr->nextPtr;
       currentPtr->nextPtr = temp;
       currentPtr = currentPtr->previousPtr;
	   printf("%c -->", currentPtr->data);
     }     if(temp != NULL )
        currentPtr = temp->previousPtr;
 
 
} /* end function printList */



Is This A Good Question/Topic? 0
  • +

Replies To: Doubly Linked List - C

#2 Djabby  Icon User is offline

  • D.I.C Head

Reputation: 37
  • View blog
  • Posts: 131
  • Joined: 02-November 10

Re: Doubly Linked List - C

Posted 02 November 2010 - 08:54 AM

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

newPtr = (ListNode*)malloc(sizeof(ListNodePtr));

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

      previousPtr = NULL;
      currentPtr = *sPtr;

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

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

      else { /* insert new node between previousPtr and currentPtr */
         previousPtr->nextPtr = newPtr;
         newPtr->nextPtr = currentPtr;
      } /* end else */

      // ADDED:
      newPtr->previousPtr = previousPtr;

    } /* 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 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){ 
        *sPtr = (*sPtr)->nextPtr; /* de-thread the node */
      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;

         // ADDED:
         currentPtr->nextPtr->previousPtr = previousPtr;
         return value;
      } /* end if */
    } /* end else */

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



Just set the previousPtr if something you set a new nextPtr.
Because this must be assured: currentPtr->nextPtr->previousPtr == currentPtr
as long as currentPtr->nextPtr is not NULL
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1