Thread: singly linked list to doubly linked list

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    1

    singly linked list to doubly linked list

    I was just wondering how to change this singly linked list code into a doubly linked list. I know i have to use:

    struct Node{
    char d;
    Node *next;
    Node *prev;
    }

    i just want to be able to move forward and backwards in the list.

    i am confused....

    and by book doesn't cover it, it just basically says doubly linked list are useful to move forward and backwards

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode {            
       char data; 
       struct listNode *nextPtr; 
    }; 
    
    typedef struct listNode ListNode; 
    typedef ListNode *ListNodePtr; 
    
    
    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; 
       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, item ); 
                printList( startPtr );
                break;
    
             case 2:
    
                
                if ( !isEmpty( startPtr ) ) { 
                   printf( "Enter character to be deleted: " );
                   scanf( "\n%c", &item );
    
                   
                   if ( delete( &startPtr, item ) ) { 
                      printf( "%c deleted.\n", item );
                      printList( startPtr );
                   } 
                   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, char value )
    { 
       ListNodePtr newPtr;      
       ListNodePtr previousPtr; 
       ListNodePtr currentPtr;  
    
       newPtr = malloc( sizeof( ListNode ) ); 
    
       if ( newPtr != NULL ) { 
          newPtr->data = value; 
          newPtr->nextPtr = NULL; 
    
          previousPtr = NULL;
          currentPtr = *sPtr;
    
          
          while ( currentPtr != NULL && value > currentPtr->data ) { 
             previousPtr = currentPtr;          
             currentPtr = currentPtr->nextPtr;  
          } 
          
          if ( previousPtr == NULL ) { 
             newPtr->nextPtr = *sPtr;
             *sPtr = newPtr;
          } 
          else { 
             previousPtr->nextPtr = newPtr;
             newPtr->nextPtr = currentPtr;
          } 
    
       } 
       else {
          printf( "%c not inserted. No memory available.\n", value );
       } 
    
    } 
    
    
    char delete( ListNodePtr *sPtr, char value )
    { 
       ListNodePtr previousPtr; 
       ListNodePtr currentPtr;  
       ListNodePtr tempPtr;     
    
       
       if ( value == ( *sPtr )->data ) { 
          tempPtr = *sPtr; 
          *sPtr = ( *sPtr )->nextPtr; 
          free( tempPtr ); 
          return value;
       } 
       else { 
          previousPtr = *sPtr;
          currentPtr = ( *sPtr )->nextPtr;
    
          
          while ( currentPtr != NULL && currentPtr->data != value ) { 
             previousPtr = currentPtr;         
             currentPtr = currentPtr->nextPtr; 
          } 
    
          
          if ( currentPtr != NULL ) { 
             tempPtr = currentPtr;
             previousPtr->nextPtr = currentPtr->nextPtr;
             free( tempPtr );
             return value;
          } 
         
       } 
    
       return '\0';
    
    } 
    
    
    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" );
       } 
    }

  2. #2
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    I wrote some simple functions to manipulate doubly linked list a while ago and I'll share it with you. Note that I've done that a while ago so it could be some possible bugs. If you find it please let me know.
    Anyway I hope these can help you to learn more
    Last edited by Micko; 03-23-2005 at 04:08 PM.
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    135
    Go Here and scroll down to the Link List link .

    xeddiex

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Do you know how to walk through a single linked list? If so, what's the problem?
    Code:
    struct snode *s;
    struct dnode *d;
    
    for ( s = slist; s; s = s->next )
    {
        d->data = s->data;
        d->next = s->next;
        d->prev = dlist;
        dlist = d;
    }
    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. Making a doubly linked list
    By mlupo in forum C Programming
    Replies: 1
    Last Post: 10-16-2002, 09:05 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM