Thread: singly linked to doubly linked

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    63

    singly linked to doubly linked

    Have a tough assignment on linked lists and nothing in my book on doubly linked lists, I'm re-reading the chapter and trying to come up with something bnut any pointers would be greatly appreciated. I'll update it when I get something going:

    Change the singly linked list code in the book to a doubly linked list - figure 12.3

    To do this you should create a Node:

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

    so that you can move forward and backwards in the list.

    You should implement insert and delete so that they work properly. You should implement a print_backwards to prove that your doubly linked list is working correctly.

    Note that you should keep track of the head and tail of the list.

    here is fig 12.3
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* self referential structure */
    struct listNode {
    	char data; /* each listNode contains a character */
    	struct listNode *nextPtr; /* pointer to the nextnode */
    }; /* 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; /* users 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 the 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 ) ) {
                        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("? ");
    		scanf( "%d", &choice );
    	} /* end while */
    
    	printf( "end of run.\n" );
    	return 0; /* indicate sucessful termination */
    
    } /* 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 of instructions */
    
    /* insert a new value into the list in sorted order */
    void insert ( ListNodePtr *sPtr, char value)
    {
    	ListNodePtr newPtr;       /* pointer to a new node */
        ListNodePtr previousPtr;  /* pointer to previous node in list */
        ListNodePtr currentPtr;  /* pointer to current node on 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 */
    
    		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 begining 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 id */
    	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 on list */
        ListNodePtr currentPtr;  /* pointer to current node on list */
        ListNodePtr tempPtr;     /* temperary 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 {
    		previousPtr = *sPtr;
    		currentPtr = ( *sPtr )->nextPtr;
    
    		/* loop to find correct location on 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;
    			free ( tempPtr );
    			return value;
    		} /* end if */
    
    	} /* end else */
    
    	return '\0';
    
    } /* end function delete */
    
    /* return 1 if list is empty, 0 otherwise */
    int isEmpty ( ListNodePtr sPtr )
    {
    	return sPtr == NULL;
    
    } /* end function isEmpty */
    
    /* Print the list */
    void printList ( ListNodePtr currentPtr )
    {
    	/* if list id empty */
    	if ( currentPtr == NULL) {
    		printf( " The list is empty.\n\n" );
    	} /* end if */
    	else {
    		printf( " The 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 */
    
    } /* end function printlist */
    Last edited by jsbeckton; 11-03-2005 at 04:23 PM.

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    The first thing is DO NOT ignore warnings. In your program, that warning on line 44 is really an error. IsEmpty() expects a pointer to a ListNodePtr object, in otherwords, it is prototyped this way:
    Code:
    int isEmpty( ListNode**sPtr );
    line 44 of your program is passing only a single pointer thing, which is the wrong data type. That is one of the very BAD things about typcasting pointers to hide them -- it is very easy to make coding errors. The example I showed above is very clear about what kind of pointer the function expects.

    To correct this, it would have to be coded as below. Or change the function prototype and possibly the function itself to require only a single-pointer object. I suspect the function prototype is wrong.
    Code:
    int main()
    {
     ...
     ...
                    if (!isEmpty(&startPtr )) {
     ...
    }
    Last edited by Ancient Dragon; 11-03-2005 at 04:34 PM.

  3. #3
    Registered User
    Join Date
    Oct 2005
    Posts
    63
    Thanks,I fixed and updated that.

  4. #4
    Registered User
    Join Date
    Oct 2005
    Posts
    63
    Do I need to just get rid of the original struct and use the given one to make it doubly linked? I understand that the idea is to have pointers going back and forth so I can move both ways through the list, I guess I'm just not sure if I should make a whole new program or modify this one. Any suggestions?

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    char delete ( ListNodePtr *sPtr, char value )
    You might want to call that function something else (in C++ delete is an operator!).

    I would make a new program, but you can modify that one if you want to.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    >>I would make a new program, but you can modify that one if you want to.
    I would have modified that one and save as new file if i have got the assignment.
    Long time no C. I need to learn the language again.
    Help a man when he is in trouble and he will remember you when he is in trouble again.
    You learn in life when you lose.
    Complex problems have simple, easy to understand wrong answers.
    "A ship in the harbour is safe, but that's not what ships are built
    for"

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    It doesn't matter too much.

    jsbeckton might want to use a do-while loop in main instead of a while loop. It would eliminate some duplicate code. Just a suggestion.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    I understand that the idea is to have pointers going back and forth so I can move both ways through the list, I guess I'm just not sure if I should make a whole new program or modify this one. Any suggestions?
    Note that you should keep track of the head and tail of the list.
    You need some mechanism to traverse the list in both directions. Thus, you need a pointer to the next node and a pointer to the previous node in your structure. The statements in bold handle the head and tail requirements. They are updated in your insert function since I assume you will be sorting the data again.

    Allocate memory for the new node, load it with data and then call the insert function.

    Code:
    struct listNode
    {
        char data;
        struct listNode *priorPtr;
        struct listNode *nextPtr;
    
    }ListNode;
    
    struct listNode  *start = NULL;         
    struct listNode  *last = NULL;           
    
    
    
    void insert( struct listNode   *newnode,  /* new node */
                    struct listNode   **start, /* first node */
                    struct listNode   **last /* last node */
                    )
    {
        struct listNode  *oldptr, *ptr;
        if(*last == NULL) /* first node in linklist */
        {
            newnode->nextPtr = NULL;
            newnode->priorPtr = NULL;
            *last = newnode;
            *start = newnode;
            return;
        }
        ptr = *start; /* start at top of linklist */
        oldptr = NULL;
        while(ptr)
        {
            if(ptr->data < newnode->data )
            {
                oldptr = ptr;
                ptr = ptr->nextPtr;
            }
            else
            {
                if(ptr->priorPtr)
                {
                    ptr->priorPtr->nextPtr = newnode;
                    newnode->nextPtr = ptr;
                    newnode->priorPtr = ptr->priorPtr;
                    ptr->priorPtr = newnode;
                    return;
                }
                newnode->nextPtr = ptr; /* newnode first node */
                newnode->priorPtr = NULL;
                ptr->priorPtr = newnode;
                *start = newnode;
                return;
            }
        }
        oldptr->nextPtr = newnode;
        newnode->nextPtr = NULL;
        newnode->priorPtr = oldptr;
        *last = newnode;
    }
    Last edited by BobS0327; 11-05-2005 at 10:21 PM. Reason: Add code to insert function

  9. #9
    Registered User
    Join Date
    Oct 2005
    Posts
    63
    How come the new nodes are struct, the ones he said to use were pointers in the struct :
    Code:
    struct Node{
    char d;
    Node *next;
    Node *prev;
    }

  10. #10
    Registered User
    Join Date
    Oct 2005
    Posts
    63
    I inserted the new struct and attempted to change the insertion to doubly linked by rearanging the pointer configuration as indicated but I am getting a lot of errors and must be doing something horribly wrong. I have no real erference for doubly linked pointers in my book sp its kinda hard to see how it is written, I understand what I am trying to do but I have no clue as to how to write the actual code. I read the whole chapter 4 times that talks all about singly linked lists and then the assignment is a doubly linked list, sounds kinda stupid to me but I'll struggle through it.

    Am I attempting to modify the code in the right place and where does the sPtr fit in? Here is the updated code
    Code:
    /* CH_10-12 linked */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    /* self referential structure */
    struct listNode {
    char data; /* each listNode contains a character */
    struct listNode *nextPtr; /* pointer to the nextnode */
    }; /* end structure listNode */
    
    /* structure */
    struct Node {
    	char d;
    	Node *next;
    	Node *prev;
    }; /* end structure Node */
    
    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; /* users 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 the 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 ) ) {
                        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("? ");
    		scanf( "%d", &choice );
    	} /* end while */
    
    	printf( "end of run.\n" );
    	return 0; /* indicate sucessful termination */
    
    } /* 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 of instructions */
    
    /* insert a new value into the list in sorted order */
    void insert ( ListNodePtr *sPtr, char value)
    {
    	ListNodePtr newPtr;       /* pointer to a new node */
        ListNodePtr previousPtr;  /* pointer to previous node in list */
        ListNodePtr currentPtr;  /* pointer to current node on 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 */
    
    		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 */
    		if ( previousPtr == NULL ) {
    			currentPtr->prev->next;
    			newPtr->previousPtr->prev;
    			newPtr->next;
    			curentPtr->prev;
    
    		} /* end if */
    		else { /* insert new node between previousPtr and currentPtr */
    			previousPtr->nextPtr = newPtr;
    			newPtr->nextPtr = currentPtr;
    		} /* end else */
    
    	} /* end id */
    	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 on list */
        ListNodePtr currentPtr;  /* pointer to current node on list */
        ListNodePtr tempPtr;     /* temperary 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 {
    		previousPtr = *sPtr;
    		currentPtr = ( *sPtr )->nextPtr;
    
    		/* loop to find correct location on 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;
    			free ( tempPtr );
    			return value;
    		} /* end if */
    
    	} /* end else */
    
    	return '\0';
    
    } /* end function delete */
    
    /* return 1 if list is empty, 0 otherwise */
    int isEmpty ( ListNodePtr sPtr )
    {
    	return sPtr == NULL;
    
    } /* end function isEmpty */
    
    /* Print the list */
    void printList ( ListNodePtr currentPtr )
    {
    	/* if list id empty */
    	if ( currentPtr == NULL) {
    		printf( " The list is empty.\n\n" );
    	} /* end if */
    	else {
    		printf( " The 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 */
    
    } /* end function printlist */

  11. #11
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    Code to demonstrate the doubly linked list.

    Code:
    int main(void)
    {
        char temp[] ={"ZGBFAD"};
        int x;
        struct listNode  *start = NULL;         
        struct listNode  *last = NULL;    
        struct listNode  *data = NULL;
        struct listNode  *tempnode  = NULL;   
        for(x = 0; x< 5;x++)
        {
            // C environment
            //data =  malloc(sizeof(ListNode));
            // C++ environment
             data = (struct listNode  *) malloc(sizeof(listNode));
            if(!data)
            {
                // out of memory
                return 0;
            }
            data->data = temp[x];
            insert(data, &start, &last);
        }
        tempnode = start;
        while(tempnode) // print out the list  from beginning
        {
            printf("data = %c\n",tempnode->data);
            tempnode = tempnode->nextPtr; /* get nextPtr address */
        }
        return 0;
    }
    Last edited by BobS0327; 11-06-2005 at 07:50 PM. Reason: Spelling error

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. Singly Linked List
    By devarishi in forum C Programming
    Replies: 4
    Last Post: 12-24-2008, 12:00 AM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM