Help!!! single to double link lists!!

[scoob]

I have this assignemt to make a double link list for a student database.
I have tried to make it in single link list so that i can understand the implementation.
the problem is that i can't make it a double link list :S i am so confused! plz someone help me!

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

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

using namespace std;





struct StudentNode {
   char name[10];
   int age;
   double gpa;
   char sex[1];
   int ID;


   struct StudentNode *nextPtr;
};

typedef struct StudentNode Student;
typedef Student *StudentPtr;





void insert( Student **headOfList,  char *name, int age, double gpa, char *sex)
{
    static int ID;
	StudentPtr newPtr;
	StudentPtr previousPtr;
	StudentPtr currentPtr;
	ID++;

	newPtr = ( Student * ) malloc( sizeof( Student ) );

	if ( newPtr != NULL ) {

		strcpy(newPtr->name, name);
		newPtr->age = age;
		newPtr->gpa = gpa;
		strcpy(newPtr->sex, sex);
		newPtr->ID = ID;

		newPtr->nextPtr = NULL;

		previousPtr = NULL;
		currentPtr = *headOfList;

		if ( currentPtr != NULL ) {
			previousPtr = currentPtr;
			currentPtr = currentPtr->nextPtr;
		}

		if ( previousPtr == NULL ) {
			newPtr->nextPtr = *headOfList;
			*headOfList = newPtr;
		}
		else {
			previousPtr->nextPtr = newPtr;
			newPtr->nextPtr = currentPtr;
		}
	}

	else {
		printf( "%s not inserted. No memory available.\n", name );
	}
}

void deleteNode( Student  **headOfList, int tempID )
{
	StudentPtr previousPtr;
	StudentPtr currentPtr;
	StudentPtr tempPtr;


	if ( tempID == (*headOfList)->ID ) {

		tempPtr = (*headOfList);

		if((*headOfList)->nextPtr == NULL){

		free( tempPtr );

		}
		else{

		     (*headOfList) = (*headOfList)->nextPtr;
		     free( tempPtr );

		}

	}
	else {
		previousPtr = (*headOfList);
		currentPtr = (*headOfList)->nextPtr;

		if(currentPtr == NULL){
		cout << "student not found" << endl;


		}


        else{


		while (currentPtr->nextPtr != NULL && currentPtr->ID != tempID ) {
			previousPtr = currentPtr;
			currentPtr = currentPtr->nextPtr;
		}

		if ( currentPtr->nextPtr != NULL) {
			tempPtr = currentPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			free( tempPtr );
		}
		else {
			tempPtr = currentPtr;
			previousPtr->nextPtr = NULL;
			free( tempPtr );
		}
        }
	}


}


void editStud( Student **headOfList, int studID)
{

    StudentPtr previousPtr;
	StudentPtr currentPtr;



	char tempName[10];
	int tempAge;
	double tempGpa;
	char tempSex[1];




	if ( studID == (*headOfList)->ID ) {


    cout << "Please enter the new name" << endl;
    cin >> tempName;
    cout << "Please enter the new age" << endl;
    cin >> tempAge;
    cout << "Please enter the new G.P.A." << endl;
    cin >> tempGpa;
    cout << "Please enter the new sex" << endl;
    cin >> tempSex;


    strcpy((*headOfList)->name, tempName);
    (*headOfList)->age = tempAge;
    (*headOfList)->gpa = tempGpa;
    strcpy((*headOfList)->sex, tempSex);


	}
	else {


		currentPtr = (*headOfList)->nextPtr;


		while (currentPtr->nextPtr != NULL && currentPtr->ID != studID ) {


          currentPtr = currentPtr->nextPtr;
		}


            cout << "Please enter the new name" << endl;
            cin >>tempName;
            cout << "Please enter the new age" << endl;
            cin >>tempAge;
            cout << "Please enter the new G.P.A." << endl;
            cin >>tempGpa;
            cout << "Please enter the new sex" << endl;
            cin >>tempSex;


            strcpy(currentPtr->name, tempName);
            (currentPtr)->age = tempAge;
            (currentPtr)->gpa = tempGpa;
            strcpy(currentPtr->sex, tempSex);

        }



	}



void printStud( Student *headOfList, int studID)
{

    StudentPtr previousPtr;
	StudentPtr currentPtr;



	if ( studID == (headOfList)->ID ) {

    cout<<"-------------------------------"<< endl;
    cout<<"Student ID:"<< headOfList->ID << endl;
    cout<<"Student name:"<< headOfList->name << endl;
    cout<<"Student age:"<< headOfList->age << endl;
    cout<<"Student G.P.A.:"<< headOfList->gpa << endl;
    cout<<"Student sex:"<< headOfList->sex << endl;
    cout<<"-------------------------------"<< endl;

	}
	else {


		currentPtr = (headOfList)->nextPtr;


		if(currentPtr == NULL){
		cout << "student not found" << endl;


		}


        else{

		while (currentPtr->nextPtr != NULL && currentPtr->ID != studID ) {


          currentPtr = currentPtr->nextPtr;
		}


           if(currentPtr->ID == studID){
			cout<<"-------------------------------"<< endl;
            cout<<"Student ID:"<< currentPtr->ID << endl;
            cout<<"Student name:"<< currentPtr->name << endl;
            cout<<"Student age:"<< currentPtr->age << endl;
            cout<<"Student G.P.A.:"<< currentPtr->gpa << endl;
            cout<<"Student sex:"<< currentPtr->sex << endl;
            cout<<"-------------------------------"<< endl;

            }

            else{

            cout << "student not found" << endl;

            }

        }




	}

  }


void printList( Student *headOfList )
{

  while ( headOfList != NULL ) {

    cout<<"-------------------------------"<< endl;
    cout<<"Student ID:"<< headOfList->ID << endl;
    cout<<"Student name:"<< headOfList->name << endl;
    cout<<"Student age:"<< headOfList->age << endl;
    cout<<"Student G.P.A.:"<< headOfList->gpa << endl;
    cout<<"Student sex:"<< headOfList->sex << endl;
    cout<<"-------------------------------"<< endl;
    headOfList = headOfList->nextPtr;

  }
    return;


	}


int main(void)
{
   char name[10];
   int age;
   double gpa;
   char sex[1];
   int tempID;
   int studID;


    char choice;
    StudentPtr startptr = NULL;
    int yo=1;
    while(yo != 0)
	{



fflush(stdin);
		system("cls");
	   	printf("\n       This is a program that will manipulate student data\n");
	   	printf("         in a database feel program.\n");
		printf("\n         **********      PROGRAM MENU      **********      \n");
		printf("\n     A. New student.");
		printf("\n     B. Verify student.");
		printf("\n     C. Edit student.");
		printf("\n     D. Remove student.");
		printf("\n     E. Student with the highest GPA.");
		printf("\n     F. Student with the lowest GPA.");
		printf("\n     G. Male students.");
		printf("\n     H. Female students.");
		printf("\n     I. Show all students.");
		printf("\n     J. GPA descending.");
		printf("\n     K. Age descending.");
		printf("\n\n     Q. Quit.");
	   	printf("\n\n                      Please make a choice: ");
		scanf("%c", &choice);


		switch (choice) {
 		   case 'a':
		   case 'A':

            cout << "insert student last name" << endl;
            cin >> name;
            cout << "insert student age" << endl;
            cin >> age;
            cout << "insert student gpa" << endl;
            cin >> gpa;
            cout << "insert student sex" << endl;
            cin >> sex;


            insert( &startptr, name, age, gpa, sex);


            printf("Press any key to return back to the menu.");
		   		    getch();
                    break;



          case 'b':
          case 'B':

                cout << "Please enter the id of the student you want to print:" << endl;
                cin >> studID;
                printStud( startptr, studID);




                    printf("Press any key to return back to the menu.");
		   		    getch();
                    break;




          case 'c':
          case 'C':
                    studID = 0;
                    cout << "Please enter the id of the student you want to edit:" << endl;
                    cin >> studID;




                    editStud( &startptr, studID);







                    printf("Press any key to return back to the menu.");
		   		    getch();
                    break;










          case 'd':
          case 'D':



          cout << "Please enter the id of the student you want to delete:" << endl;
          cin >> tempID;

          deleteNode( &startptr, tempID);

          printf("Press any key to return back to the menu.");
          getch();
          break;




          case 'i':
          case 'I':


                   printList( startptr );
                   printf("Press any key to return back to the menu.");
                   getch();
                   break;


		}





	}



	return 0;

}

[geojia]

You have 450 lines of code! I suggest you try to tackle this problem step by step.
1. change your Node class so that it has a *prev of class Node
2. Implement constructor() everything is same except set start.prev to null.
3. implement add node(Node *currentNode, Node *nodeToBeInserted) here you need to
a: nodeToBeInserted->next=currentNode->next
b: nodeToBeInserted->prev=currentNode
c: currentNode->next=nodeToBeInserted
4. for delete node( *currNode, nodeToDel)
a.currNode->next=nodeToDel->next;
b.because you are passing in nodeToDel as an object, it'll go out of scope, but I think this causes memory leaks, so you probably should call destructor on the nodeToDel

Good luck!

[scoob]

First of all thank you very much for your tips!
I am a beginner in programming so i will try to figure out what you are trying to tell me... It would be really helpful if you could give me a line or two of code so that i understand better.

thank you in advance.

[geojia]

Here is a really good tutorial by Naru on linked list:
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_linklist.aspx

But right now I'm not seeing any linking structure in your student strut definition. As in you need a pointer to a student struct named next and another one named previous.

studentNode *next;
studentNode *prev;

Normally this is done with a Class and you point to objects of the same class. But it should be achievable with a struct.

[scoob]

is it possible for someone to make a sample code of the double link list so that i can after implement my algorithms?

[scoob]

ok... i have now tried to insert a double link list kind of feal....

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <stdio.h>
#include <conio.h>
#include <memory.h>

using namespace std;

struct node
 {
   char name[10];
   int age;
   double gpa;
   char sex[1];
   int ID;
   struct node *nextPtr;    // Pointer to next node
   struct node *prevPtr;    // Pointer to previous node
 };
typedef struct node Student;
typedef Student *StudentPtr;

void insert( Student **headOfList,  char *name, int age, double gpa, char *sex)
{
    static int ID;
	StudentPtr newPtr;
	StudentPtr previousPtr;
	StudentPtr nextPtr;
	StudentPtr currentPtr;
	ID++;

	newPtr = ( Student * ) malloc( sizeof( Student ) );

	if ( newPtr != NULL ) {

		strcpy(newPtr->name, name);
		newPtr->age = age;
		newPtr->gpa = gpa;
		strcpy(newPtr->sex, sex);
		newPtr->ID = ID;

		newPtr->nextPtr = NULL;


		previousPtr = NULL;
		currentPtr = *headOfList;

		if ( currentPtr != NULL ) {
			previousPtr = currentPtr;
			currentPtr = currentPtr->nextPtr;
		}

		if ( previousPtr == NULL ) {
			newPtr->nextPtr = *headOfList;
			*headOfList = newPtr;
		}
		else {
			previousPtr->nextPtr = newPtr;
			newPtr->nextPtr = currentPtr;
		}
	}

	else {
		printf( "%s not inserted. No memory available.\n", name );
	}
}

void printList( Student *headOfList )
{

  while ( headOfList != NULL ) {

    cout<<"-------------------------------"<< endl;
    cout<<"Student ID:"<< headOfList->ID << endl;
    cout<<"Student name:"<< headOfList->name << endl;
    cout<<"Student age:"<< headOfList->age << endl;
    cout<<"Student G.P.A.:"<< headOfList->gpa << endl;
    cout<<"Student sex:"<< headOfList->sex << endl;
    cout<<"-------------------------------"<< endl;
    headOfList = headOfList->nextPtr;

  }
    return;


	}

void deleteNode( Student  **headOfList, int tempID )
{
	StudentPtr previousPtr;
	StudentPtr currentPtr;
	StudentPtr tempPtr;
	StudentPtr nextPtr;


	if ( tempID == (*headOfList)->ID ) {

		tempPtr = (*headOfList);

		if((*headOfList)->nextPtr == NULL){

		free( tempPtr );

		}
		else{

		     (*headOfList) = (*headOfList)->nextPtr;
		     free( tempPtr );

		}

	}
	else {
		previousPtr = (*headOfList);
		currentPtr = (*headOfList)->nextPtr;

		if(currentPtr == NULL){
		cout << "student not found" << endl;


		}


        else{


		while (currentPtr->nextPtr != NULL && currentPtr->ID != tempID ) {
			previousPtr = currentPtr;
			currentPtr = currentPtr->nextPtr;
		}

		if ( currentPtr->nextPtr != NULL) {
			tempPtr = currentPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			previousPtr->nextPtr = currentPtr->nextPtr;
			free( tempPtr );
		}
		else {
			tempPtr = currentPtr;
			previousPtr->nextPtr = NULL;
			free( tempPtr );
		}
        }
	}


}

void editStud( Student **headOfList, int studID)
{

    StudentPtr previousPtr;
	StudentPtr currentPtr;



	char tempName[10];
	int tempAge;
	double tempGpa;
	char tempSex[1];




	if ( studID == (*headOfList)->ID ) {


    cout << "Please enter the new name" << endl;
    cin >> tempName;
    cout << "Please enter the new age" << endl;
    cin >> tempAge;
    cout << "Please enter the new G.P.A." << endl;
    cin >> tempGpa;
    cout << "Please enter the new sex" << endl;
    cin >> tempSex;


    strcpy((*headOfList)->name, tempName);
    (*headOfList)->age = tempAge;
    (*headOfList)->gpa = tempGpa;
    strcpy((*headOfList)->sex, tempSex);


	}
	else {


		currentPtr = (*headOfList)->nextPtr;


		while (currentPtr->nextPtr != NULL && currentPtr->ID != studID ) {


          currentPtr = currentPtr->nextPtr;
		}


            cout << "Please enter the new name" << endl;
            cin >>tempName;
            cout << "Please enter the new age" << endl;
            cin >>tempAge;
            cout << "Please enter the new G.P.A." << endl;
            cin >>tempGpa;
            cout << "Please enter the new sex" << endl;
            cin >>tempSex;


            strcpy(currentPtr->name, tempName);
            (currentPtr)->age = tempAge;
            (currentPtr)->gpa = tempGpa;
            strcpy(currentPtr->sex, tempSex);

        }



	}

void printStud( Student *headOfList, int studID)
{

    StudentPtr previousPtr;
	StudentPtr currentPtr;



	if ( studID == (headOfList)->ID ) {

    cout<<"-------------------------------"<< endl;
    cout<<"Student ID:"<< headOfList->ID << endl;
    cout<<"Student name:"<< headOfList->name << endl;
    cout<<"Student age:"<< headOfList->age << endl;
    cout<<"Student G.P.A.:"<< headOfList->gpa << endl;
    cout<<"Student sex:"<< headOfList->sex << endl;
    cout<<"-------------------------------"<< endl;

	}
	else {


		currentPtr = (headOfList)->nextPtr;


		if(currentPtr == NULL){
		cout << "student not found" << endl;


		}


        else{

		while (currentPtr->nextPtr != NULL && currentPtr->ID != studID ) {


          currentPtr = currentPtr->nextPtr;
		}


           if(currentPtr->ID == studID){
			cout<<"-------------------------------"<< endl;
            cout<<"Student ID:"<< currentPtr->ID << endl;
            cout<<"Student name:"<< currentPtr->name << endl;
            cout<<"Student age:"<< currentPtr->age << endl;
            cout<<"Student G.P.A.:"<< currentPtr->gpa << endl;
            cout<<"Student sex:"<< currentPtr->sex << endl;
            cout<<"-------------------------------"<< endl;

            }

            else{

            cout << "student not found" << endl;

            }

        }




	}

  }



int main(void)
{
    int tempID;
    int studID;
    StudentPtr startptr = NULL;
    char choice;
    static int i;

    char name[50];
    int age;
    double gpa;
    char sex[1];
    i = 0;
    int yo=1;
    while(yo != 0)
	{

        fflush(stdin);
		system("cls");
	   	printf("\n       This is a program that will manipulate student data\n");
	   	printf("         in a database feel program.\n");
		printf("\n         **********      PROGRAM MENU      **********      \n");
		printf("\n     A. New student.");
		printf("\n     B. Verify student.");
		printf("\n     C. Edit student.");
		printf("\n     D. Remove student.");
		printf("\n     E. Student with the highest GPA.");
		printf("\n     F. Student with the lowest GPA.");
		printf("\n     G. Male students.");
		printf("\n     H. Female students.");
		printf("\n     I. Show all students.");
		printf("\n     J. GPA descending.");
		printf("\n     K. Age descending.");
		printf("\n\n     Q. Quit.");
	   	printf("\n\n                      Please make a choice: ");
		scanf("%c", &choice);


		switch (choice) {
 		   case 'a':
		   case 'A':



                 cout << "insert student last name" << endl;
                 cin >> name;
                 cout << "insert student age" << endl;
                 cin >> age;
                 cout << "insert student gpa" << endl;
                 cin >> gpa;
                 cout << "insert student sex" << endl;
                 cin >> sex;

                 insert( &startptr, name, age, gpa, sex);

                 printf("Press any key to return back to the menu.");
                 getch();
                 break;

          case 'b':
          case 'B':

                cout << "Please enter the id of the student you want to print:" << endl;
                cin >> studID;
                printStud( startptr, studID);




                    printf("Press any key to return back to the menu.");
		   		    getch();
                    break;

          case 'c':
          case 'C':

                    studID = 0;
                    cout << "Please enter the id of the student you want to edit:" << endl;
                    cin >> studID;

                    editStud( &startptr, studID);

                    printf("Press any key to return back to the menu.");
		   		    getch();
                    break;

          case 'd':
          case 'D':



          cout << "Please enter the id of the student you want to delete:" << endl;
          cin >> tempID;

          deleteNode( &startptr, tempID);

          case 'i':
          case 'I':


                   printList( startptr );
                   printf("Press any key to return back to the menu.");
                   getch();
                   break;

		}
	}
}

[scoob]

it seems to work.... but i have no idea if what i did had any effect :S

[geojia]

You should be able to see if it's working. For instance when you run the program after it calls the insert() and see if it prints all your couts. I do see some problem right now. Currently you are using a double pointer container to represent your linked list. And then you are making pointer node objects. But you are making objects.

StudentPtr newPtr;
	StudentPtr previousPtr;
	StudentPtr nextPtr;
	StudentPtr currentPtr;

to make them pointers do

StudentPtr *previousPtr;

For this program since you are not creating linked lists dynamically you don't need to have a double pointer, a single pointer pointed to the start of the list is enough.

[scoob]

i don't seem to get what you are telling me.... can you actually change my code so that i understand... and something else... have i eventually transformed my code to double linked list?