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

Linked List fun!

Sign in to follow this  
wijnand

121 views

this last week my 3D game engine course started, my first assigment was to make a cute little Linked List in C++ that does a few things. I had a rought time getting it working, and I know a lot of people have issues with it, therefore I am posting it here. Also to illustrate I am STILL! alive , although sometimes my fridge does seem to get closed and closer to me...

[source code ="cpp"]
/* Linked List version 1.0 by Wijnand Dalmijn 20017368 */


// TODO: Clean up your code!!!

#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 so be carefull with it.

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

if (startlist == NULL)
{
cout << "There is no LinkedList yet, making a new one now! \n";

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;

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 ring.

return startlist;// return this value to the main()
}
else
{
//fill the correct pointer in first
nextlist->nextList = newList;

cout << "A start List was detected, making a new entry \n";

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;

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;
while(true) //loop so the program does not shutdown after first selection
{
makeSelection();
cin >> input;

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

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

case 2:
{
//Display everything that has been put in
bool loop = true;
LinkedList* showList = new LinkedList;
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)
{
loop = false;
cout << "The Complete listing has been shown! \n";
}
else
{
nextlist = showList->nextList;
showList = nextlist;
}

}

}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;
}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;
}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);
}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;
}
}

}break;

default:
{
cout << "Please select one of the numbers selected on the screen" << endl;
}break;
}

}


}

Sign in to follow this  


4 Comments


Recommended Comments

Good to hear that you're still alive and progressing! (And naturally, beware the refridgerators! [grin])

Share this comment


Link to comment
Nice to see that you got it working. [smile] However, there are some issues with your code.

You should be aware that you are leaking memory all over the place. You have code like this in several places:

LinkedList *list = new LinkedList();
list = /*someGlobal*/

This leaks the memory for the "newed LinkedList" stored in list. There is no reason to allocate a linked list object to iterate over one.

You really need to look into how you manage your memory. Seeing as you are not using a constructor/destructor for your linked list you have to be especially careful.

You should think about adding a few more helper functions, ones to add and remove elements from a given linked list. You should also have a function to free a linked list, it should destroy all the elements inside the list too.

I do not understand the need for a global LinkedList pointer. Im pretty sure you can get by without it.

A linked list is more usually made of 3 parts, the linked list data structure which describes the list as a single unit, the node data structure which describes each link in the list, and finally the "data" portion, which is the data stored inside each link.

Seperating these out gives you many advantages in your code. It seperates the idea of "having a linked list of something" from "iterating over a linked list of something".

e.g:

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

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

struct LinkedList
{
LinkedListNode *start;
int elementCount;
};



Seeing as you said this was for a course Ill refrain from going into more implementation detail, but if you are interested in this approach you could post any efforts you make or any problems you are having.

Share this comment


Link to comment
Nice to see that you got it working. [smile] However, there are some issues with your code.

You should be aware that you are leaking memory all over the place. You have code like this in several places:

LinkedList *list = new LinkedList();
list = /*someGlobal*/

This leaks the memory for the "newed LinkedList" stored in list. There is no reason to allocate a linked list object to iterate over one.

You really need to look into how you manage your memory. Seeing as you are not using a constructor/destructor for your linked list you have to be especially careful.

You should think about adding a few more helper functions, ones to add and remove elements from a given linked list. You should also have a function to free a linked list, it should destroy all the elements inside the list too.

I do not understand the need for a global LinkedList pointer. Im pretty sure you can get by without it.

A linked list is more usually made of 3 parts, the linked list data structure which describes the list as a single unit, the node data structure which describes each link in the list, and finally the "data" portion, which is the data stored inside each link.

Seperating these out gives you many advantages in your code. It seperates the idea of "having a linked list of something" from "iterating over a linked list of something".

e.g:

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

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

struct LinkedList
{
LinkedListNode *start;
int elementCount;
};




Seeing as you said this was for a course Ill refrain from going into more implementation detail, but if you are interested in this approach you could post any efforts you make or any problems you are having.

Share this comment


Link to comment
I already had assumed I was leaking memory all over the place, didn't know it was THAT bad though ;)

I will take your comments into consideration and think of a different approach, but this was just to get something workable on the table. The commands it does are the things it wanted to do, the original class assigment was to make a linked list with hard coded things, but I added a layer of difficulty to it by adding additional things and making the list self building so that I would understand how to fetch the pointers. The reason I made a global pointer was because I had no idea how to make it otherwise. But I realized now after not looking at it for 2 days (i worked on it for 6 hours in a row) that there are things I can improve on, but I guess thats normal on programming :P



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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!