[JohnH3429]

I need to be able to take the singly linked list code below and make it into a doubly linked list and in addition to already printing the list forward I need to create another subroutine to print the doubly linked list in reverse. Any suggestions?

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


/**************************************************
*programmer: John Haines						  *
*Date 3-31-09									 *
*Name: main function							  *
* function: 
* asks user for names to insert into the linklist *
* and also which name to delete				   *
*												 *
**************************************************/


struct listNode{
   char * name;
   struct listNode * nextPtr;
};
void print_function ( struct listNode *startPtr);
void insert_function(struct listNode **startPtr, char *data);
void delete_function(struct listNode **startPtr, char *value);

main(){

char name[128];



;
  struct listNode * startPtr = NULL;
 printf("enter the names you want to insert into a linked list\n");

  print_function(startPtr);
  printf("enter name 1 \n");
  scanf("%s",name);
  insert_function(&startPtr,name);
  print_function(startPtr);
   printf("\n");

  printf("enter name 2 \n");
  scanf("%s", name);
  insert_function(&startPtr,name);
  print_function(startPtr);
  printf("\n");

  printf("enter name 3 \n");
  scanf("%s", name);
  insert_function(&startPtr,name);
  print_function(startPtr);
  printf("\n");
   
   printf("enter a name to delete\n");
   scanf("%s",name);
   delete_function(&startPtr,name);   
   print_function(startPtr);
   printf("\n");
	
}
/********************************************************
*programmer: John Haines								*
*Date 3-31-09
*Name: Insert_function								  *
* function: inserts a new word into a linked list 
*   in alphabetical order							   *
*
* Input												 *
*	   struct listnode **startPtr
*	   char *value - value is an adress to a character *
*											 
*   Output:											 *
*		   a newly inserted name into a linked list	*
*
**********************************************************/

void insert_function(struct listNode **startPtr, char *value){
  struct listNode *prevPtr = NULL;
  struct listNode *currentPtr = NULL;
  struct listNode *newPtr = NULL;

  int string = strlen(value);

  currentPtr = *startPtr;

	 newPtr = (struct listNode *)malloc(sizeof(struct listNode));
			if (newPtr == NULL){

	 printf("can't allocate memory\n");
	 return;
  }
  
  newPtr->name = (char *)malloc(string *sizeof(char));
  strncpy(newPtr->name,value,string);

  newPtr->nextPtr = NULL;

		  if (*startPtr == NULL){
	*startPtr = newPtr;
	return;
  }

  while (currentPtr != NULL && strncmp(newPtr->name,currentPtr->name,string) >0){ //possible problem here
	 prevPtr = currentPtr;
	 currentPtr = currentPtr->nextPtr;
  }

		 if (prevPtr == NULL){
	newPtr->nextPtr = currentPtr;
	*startPtr = newPtr;
	return;
   }

	 if (currentPtr == NULL){
	prevPtr->nextPtr = newPtr;
	return;
   }
  prevPtr->nextPtr = newPtr;
  newPtr->nextPtr = currentPtr;

}
/*********************************************************
* progammer: John Haines								 *
* Date: 3-31-09
* Name: delete_function								  *
* Function: Deletes a given entry in a linked list
* Input:												 *
*	   struct listnode **startPtr 
*	   char *value   - value is an adress to a character*
*														*
*
* Output:												*
*		   the printed linked list minus the 
* specified name to delete							   *
**********************************************************/



void delete_function(struct listNode **startPtr, char *value){
 struct listNode *currentPtr =NULL;
 struct listNode *prev =NULL;
 currentPtr = *startPtr;
 
		 if(*startPtr == NULL){
	 printf("the list is empty, can't delete\n");
	 return;
	}
	
  if((*startPtr)->name == value){
	  printf("list beginning\n");
	  *startPtr= currentPtr->nextPtr;
		free(currentPtr);
		return;
	}
	
	while(currentPtr!=NULL && (strcmp(value,currentPtr->name) != 0)){
	   prev = currentPtr;
	   currentPtr = currentPtr->nextPtr;
	}
		 
			  if(currentPtr == NULL){
	   printf("name not in list\n");
	   return;
	}
	prev->nextPtr = currentPtr->nextPtr;
	
} 
/********************************************************
*programmer: John Haines								*
*date: 3-31-09										  *
*name:print_function									*
*function: prints given names in a linked list		  *
* 
* Inputs:											   *
*		 struct listNode *startPtr					*
* Output:											   *
*		  A printed linkedlist of names				*
* ******************************************************* */

void print_function ( struct listNode *startPtr){
	struct listNode *currentPtr = startPtr;

while(currentPtr!=NULL){

				printf("|%2s| -->",currentPtr->name);

		currentPtr = currentPtr->nextPtr;
	
	}

			printf("\n");

}

[Zerobu]

In order to make a single linked list into a doubly one,you will need a pointer to point back to the previous node. So you will have a node that points to the next pointer and it will also point to the previous one.

This post has been edited by Zerobu: 03 April 2009 - 12:52 PM

[runfaster]

Also, in order to print backwards, you could use a pointer that points to the end of the list, and print through the list as you would if it were a singly linked list, using the pointer for the previous one that Zerobu mentioned.

This post has been edited by runfaster: 03 April 2009 - 12:58 PM

[Notorion]

be sure to add another pointer into your struct, like this

struct listNode{
   char * name;
   struct listNode * nextPtr;
   struct listNode * prevPtr;  //previous pointer
};