Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    67
  • comments
    82
  • views
    37011

Version 1.1 of the linked list

Sign in to follow this  
wijnand

351 views

Hopefully this is a little better then the last version, removed some redundant code and hopefully fixed a few o the memory leaks.

Wijnand



/* Linked List version 1.1 by Wijnand Dalmijn 20017368
Changes:

Cleaned up code a little bit
fixed a loop bug

TODO:

1.Figure out how to stop memory leaks
*/




#include <iostream>
#include <string>

using namespace std;

//making a structure where the initial information will be put.

struct LinkedList
{
string firstName, lastName, residence, adress, telephone; //standard variables for input
LinkedList* nextList ; // the pointer to the next structure
};


LinkedList* nextlist = NULL; // pointer where the next list is, this is a global pointer.

void makeSelection()// gives a list of the options someone can choose when he starts the program
{
cout << "Please make a selection: \n";
cout << "1: add a new linkedlist object \n";
cout << "2: List entire contents of List \n";
cout << "3: Display the third element \n";
cout << "4: Remove the third element from the list \n";
cout << "5: What is the adress of element 3? \n";
cout << "6: remove the first element \n";
cout << "7: What is the memory size of 1 Element? \n";
cout << "8: Display the names and adres of everyone \n";
cout << "0: Exit \n";

}
LinkedList* makeList(LinkedList* startlist)
{
LinkedList* newList = new LinkedList; //Create a new structure list

// fill up the list with information
cout << "What is your name? \n";
cin >> newList->firstName;

cout << "What is your last name? \n";
cin >> newList->lastName;

cout << "Where do you live? \n";
cin >> newList->residence;

cout << "What is your address? \n";
cin >> newList->adress;

cout << ("What is your phone number? \n");
cin >> newList->telephone;

if (startlist == NULL) // check if there is an existing pointer.
{
newList->nextList = NULL; //set the pointer in the struct to zero.
startlist = newList; //pointer where the list starts.
nextlist = newList; //pointer where the list starts, to continue in the next step.
return startlist;// return this value to the main()
}
else
{
//fill the correct pointer in first
nextlist->nextList = newList; // set the pointer in the struct to the next struct.

newList->nextList = NULL; // make sure this is set to NULL or else your memory gets gulped.
nextlist = newList;
return startlist;// return this value to main ();
}

}


// the main
int main()
{
LinkedList* startlist = NULL; //pointer to where the first variable goes to

char input;
bool mainloop = true; // boolean that stops the while.
while(mainloop) //loop so the program does not shutdown after first selection
{
makeSelection(); // display the input possible.

cin >> input; // get the input from the screen.

switch(input)
{
case '0':
{
mainloop = false; //exit the program
}break;

case '1':
{
startlist = makeList(startlist);
}break;

case '2':
{
//Display everything that has been put in the list.
bool loop = true;
LinkedList* showList = new LinkedList; // maak een nieuwe list aan.
showList = startlist;
while(loop)
{
cout << showList->firstName <<endl;
cout << showList->lastName <<endl;
cout << showList->adress <<endl;
cout << showList->residence <<endl;
cout << showList->telephone <<endl;

if(showList->nextList == NULL) // check if you reahed the end of the list
{
loop = false;
cout << "The Complete listing has been shown! \n";
}
else
{
nextlist = showList->nextList; //fill the information
showList = nextlist; // fill the struct so that the rest can be displayed
}
}
delete showList; // kill the list, it is no longer needed.
}break;

case '3':
{
// display the third element only
LinkedList* showList = new LinkedList;
showList = startlist;
for(int i = 0; i<2; i++)
{
nextlist = showList->nextList;
showList = nextlist;
}
//Display the third Element
cout << "Displaying the Third element! \n";
cout << showList->firstName <<endl;
cout << showList->lastName <<endl;
cout << showList->adress <<endl;
cout << showList->residence <<endl;
cout << showList->telephone <<endl;

delete showList; //remove from the memory.
}break;

case '4':
{
LinkedList* showList = new LinkedList;
LinkedList* removeList = new LinkedList;

showList = startlist;
removeList = startlist;
// find the address for the third pointer
for(int i = 0; i<2; i++)
{
removeList = removeList->nextList;
}

// find the second pointer
for (int i = 0; i<1; i++)
{
showList = showList->nextList;
}
showList->nextList = removeList->nextList;
delete removeList;
}break;

case '5':
{
// display the adress of the third element
LinkedList* showList = new LinkedList;
showList = startlist;
for(int i = 0; i<2; i++)
{
nextlist = showList->nextList;
showList = nextlist;
}
cout << "Showing the adres of the third element";
cout << showList->adress <<endl;

delete showList; // remove from the memory
}break;

case '6':
{
// remove the first Element
LinkedList* showList = new LinkedList;
LinkedList* removeList = new LinkedList;
showList = startlist;
removeList = startlist;
showList->nextList = removeList->nextList;
delete removeList;
}break;

case '7':
{
//the memory size of one element
LinkedList* showList = new LinkedList;
showList = startlist;
cout << "the Memory size of 1 element is" << sizeof(showList->firstName);
delete showList; // remove from memeory
}break;

case '8':
{
//Display The names and phone numbers of every list.
bool loop = true;
LinkedList* showList = new LinkedList;
showList = startlist;
while(loop)
{
cout << showList->firstName <<endl;
cout << showList->lastName <<endl;
cout << showList->telephone <<endl;

if(showList->nextList == NULL)
{
loop = false;
cout << "The Complete listing has been shown! \n";
}
else
{
nextlist = showList->nextList;
showList = nextlist;
}
}
delete showList;

}break;

default: // the default setting if something else is added.
{
cout << "Please select one of the numbers selected on the screen" << endl;
}break;
}

}


}

Sign in to follow this  


4 Comments


Recommended Comments

Linked lists are fun, aren't they. Glad to hear you are making progress.

Reason for the post - ref your last post there is an excellent article by Oluseyi right here about wrapping the Win32 API window stuff in a class. Hope this is of some interest. It is a very good article.

Share this comment


Link to comment
Test your program carefully, you have broken it!

For example, if you add 2 people, then list everyone, the add another person you lose the first person!

Strange behaviour to say the least. [smile]




I believe many of your errors stem from your global nextlist variable. I have difficulty seeing how you need it.

Here is a piece of code that I think is overly complex:

bool loop = true;
LinkedList* showList = new LinkedList; // maak een nieuwe list aan.
showList = startlist;
while(loop)
{
cout << showList->firstName << endl;
cout << showList->lastName << endl;
cout << showList->adress << endl;
cout << showList->residence << endl;
cout << showList->telephone << endl;

if(showList->nextList == NULL) // check if you reahed the end of the list
{
loop = false;
cout << "The Complete listing has been shown! \n";
}
else
{
nextlist = showList->nextList; //fill the information
showList = nextlist; // fill the struct so that the rest can be displayed
}
}
delete showList;



This could be re-written as:

LinkedList* showList = startlist;
while(showList != NULL)
{
cout << showList->firstName << endl;
cout << showList->lastName << endl;
cout << showList->adress << endl;
cout << showList->residence << endl;
cout << showList->telephone << endl;

showList = showList->nextList;
}
cout << "The Complete listing has been shown! \n";



You do not need to allocate memory to iterate over a list, the list already exists. As you do not need to allocate, you do not need to de-allocate at the end.

Finally the use of the global "nextList" is removed.

However, this may or may not work due to possible errors elsewhere in your code.




Again I encourage you to try seperating the LinkedList into 2 or more structures, I have coded up a linked list like yours to see what it was like, it weas quite workable once you seperate some of the logic into a few helper functions.

I found the following function set useful for use on the structures I made:

struct LinkedListData
{
string firstName, lastName, residence, adress, telephone;
};

struct LinkedListNode
{
LinkedListData data;
LinkedListNode *next;
};

struct LinkedList
{
// you dont need the size, but its useful
int size;
LinkedListNode *first;
};

// create an empty linked list
LinkedList *makeList();

// remove all the elements from this list
void clearList( LinkedList *list );

// destroy a linked list
void freeLinkedList( LinkedList *list );

// add the data to the front of the list
void addToLinkedList( LinkedList *list, const LinkedListData &data );

// remove this node from the list
void removeFromLinkedList( LinkedList *list, LinkedListNode *nodeToRemove );

// return the node at position "index" in the list
LinkedListNode *nodeAt( LinkedList *list, int index );



I made a version of your program using my linked list, it seems to work.

If you have handed up the assignment and are struggling trying to manage memory, you can have it as a reference if you want.

Share this comment


Link to comment
Test your program carefully, you have broken it!

For example, if you add 2 people, then list everyone, the add another person you lose the first person!

Strange behaviour to say the least. [smile]




I believe many of your errors stem from your global nextlist variable. I have difficulty seeing how you need it.

Here is a piece of code that I think is overly complex:

bool loop = true;
LinkedList* showList = new LinkedList; // maak een nieuwe list aan.
showList = startlist;
while(loop)
{
cout << showList->firstName << endl;
cout << showList->lastName << endl;
cout << showList->adress << endl;
cout << showList->residence << endl;
cout << showList->telephone << endl;

if(showList->nextList == NULL) // check if you reahed the end of the list
{
loop = false;
cout << "The Complete listing has been shown! \n";
}
else
{
nextlist = showList->nextList; //fill the information
showList = nextlist; // fill the struct so that the rest can be displayed
}
}
delete showList;




This could be re-written as:

LinkedList* showList = startlist;
while(showList != NULL)
{
cout << showList->firstName << endl;
cout << showList->lastName << endl;
cout << showList->adress << endl;
cout << showList->residence << endl;
cout << showList->telephone << endl;

showList = showList->nextList;
}
cout << "The Complete listing has been shown! \n";




You do not need to allocate memory to iterate over a list, the list already exists. As you do not need to allocate, you do not need to de-allocate at the end.

Finally the use of the global "nextList" is removed.

However, this may or may not work due to possible errors elsewhere in your code.




Again I encourage you to try seperating the LinkedList into 2 or more structures, I have coded up a linked list like yours to see what it was like, it weas quite workable once you seperate some of the logic into a few helper functions.

I found the following function set useful for use on the structures I made:

struct LinkedListData
{
string firstName, lastName, residence, adress, telephone;
};

struct LinkedListNode
{
LinkedListData data;
LinkedListNode *next;
};

struct LinkedList
{
// you dont need the size, but its useful
int size;
LinkedListNode *first;
};

// create an empty linked list
LinkedList *makeList();

// remove all the elements from this list
void clearList( LinkedList *list );

// destroy a linked list
void freeLinkedList( LinkedList *list );

// add the data to the front of the list
void addToLinkedList( LinkedList *list, const LinkedListData &data );

// remove this node from the list
void removeFromLinkedList( LinkedList *list, LinkedListNode *nodeToRemove );

// return the node at position "index" in the list
LinkedListNode *nodeAt( LinkedList *list, int index );




I made a version of your program using my linked list, it seems to work.

If you have handed up the assignment and are struggling trying to manage memory, you can have it as a reference if you want.

Share this comment


Link to comment
Thank you for your insightfull posts, it really seeems to clear things up for me. I will probably try and clean things up this weekend. I noticed I broke it, and my teacher said he was "impressed" at my first toss at the problem and said he would guide me through the errors.

But your advise seems to do a lot of help me aswell :) thank you, I will take a peek at the rest of your code and see if i understand it and can practically use it :)

Again thanks! :)

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!