#include <windows.h>//for BOOL #include <stdio.h> //for printf #include <time.h> //to seed srand //------------------------------------------ // LINKED LISTS: Flexable data management //------------------------------------------ //This will be the total number of people created and polled for this example. //Feel free to mess with this number if it amuses you. :) const int TOTAL_PEOPLE = 15; /* Here we have the definition of a single Node of what will become a singly linked list. Make sure you understand structs and have read both struct examples and understand them completly before reading this. You'll notice that this struct contains a pointer to itself. This is what will make the list. The 'Next' pointer will be set to point to the Node that is created after it. All will become clear in time. */ struct PERSON { PERSON * Next; BOOL isHappy; }; //------------------------------------------ // MAIN //------------------------------------------ int main(void) { int i; int HappyPeople; //Seed the random number generator srand( (unsigned)time(NULL) ); /* We only need two pointers to create a singly linked list. One will keep track of where the first Node resides. This pointer will __always__ be set to point to the very first node in the list. Mess with that and you will explode. The second pointer of type PERSON will be pointing to whatever Node we frickin want it to, got it?! ;) We'll use that pointer to move through the list and look at everything. */ PERSON * FirstPerson; PERSON * ActivePerson; /* The first step in setting up a list is to allocate some memory for it. As a rule we should always muck around with ActivePerson and leave FirstPerson to just point. It will lead to less complications in larger and more complicated lists. We allocate space equal to the size of a PERSON struct by using new. Done. Next we set the data it contains. The Next pointer should _instantly_ and _always_ be set to NULL. This will indicate that there is nothing after this Node (which there isnt... yet) and reading along the list should stop here. Failure to set the Next pointer to NULL will result in horrible memory access demons coming out of your closest and eating your program. Lastly, we set whatever irrelevant data that this PERSON is supposed to have. In this case we randomly decide if this person is happy or not. Morbid, arent I? */ ActivePerson = new PERSON; ActivePerson->Next = NULL; ActivePerson->isHappy = rand() % 2; /* Remember that we have to always have FirstPerson pointing to the begining of the list. Very important. So here we assign FirstPerson to point to the same memory that ActivePerson is pointing to. Now we have two pointers to the same thing... Thats all about to change... */ FirstPerson = ActivePerson; /* Now we're going to start creating a whole bunch of PEOPLE Nodes and adding them to the list. So what to do? Well, we just allocate another section of memory same as before. We set the ActivePersons Next pointer to point to this new memory. Now we have another Node in the list. And of course the first thing we do is set the new PERSONs Next pointer to NULL. Yup, good jobby. Your probably looking at the ->Next->Next part and being a little confused. Well, look at it like this: ActivePerson is a pointer to a PERSON object. That PERSON object contains, as part of its description, a pointer to _another_ PERSON object. That means when we say ActivePerson->Next->Next we're just pointing to the Next pointer of the Node after ActivePerson. Then we set the crap data for fun. Then, we move the ActivePerson pointer up to the recently created Node. Now its at the end of the list and we can loop again and repeat the process. Do that until the do...while loop terminates. */ i = 0; do { ActivePerson->Next = new PERSON; ActivePerson->Next->Next = NULL; ActivePerson->Next->isHappy = rand() % 2; ActivePerson =ActivePerson->Next; i++; }while(i < TOTAL_PEOPLE); /* Now lets poll all the people and see whos happy! Lets start from the first person. Oh, look! Theres a pointer just lying around that happens to point to the very first Node in the list! So we set ActivePerson to point to the first Node again. Now start reading... We increment the number of Happy People every time we find one that is. Then we move our ActivePerson pointer along to the next Node and repeat. Do that until ActivePerson is suddenly NULL. This is why we kept setting all the Next pointers to NULL. Now, when ActivePerson is set to the Next pointer of the last Node it will become NULL. Thats how we know when to stop reading. Make sure not to do __anything__ to ActivePerson until it points to something again. Even saying ActivePerson->isHappy = 0; after that while loop will cause a crash. ActivePerson will = NULL at the end and NULL is nothing, nadda, zip, and thus has no memory attached. */ HappyPeople = 0; ActivePerson = FirstPerson; do { if (ActivePerson->isHappy) HappyPeople ++; ActivePerson = ActivePerson->Next; }while(ActivePerson != NULL); //Woohoo. It appears a disturbingly low number of people are happy. //Only about half (imagine that). Well, sucks to be them I guess. printf("Of %i people, %i of them are happy.\n", TOTAL_PEOPLE, HappyPeople); /* Now for the next important part. We've done everything we wanted to do. But we have some cleaning up to do. Memory was allocated and it needs to be deallocated or we'll have nasty memory leaks. Memory leaks from linked lists are easy to overlook and will probably be the worst and biggest leaks you'll get if you're not careful. So, starting at the first node again. So we again set ActivePerson to point to what FirstPerson is pointing to. Then we loop through the list again causing deallocation in our wake. The first thing we do is set FirstPerson to point to the next Node. Then directly after that we delete that Node. Now ActivePerson points to nothing. But since we reset FirstPerson, its still at the new beggining of the list. So we set ActivePerson to point to the first Node again and repeat. Eventually FirstPerson will be set to the Next pointer of the last Node and thus will = NULL. Then when we set ActivePerson to equal it, it too will = NULL. Thats when the loop ends. */ ActivePerson = FirstPerson; do { FirstPerson = ActivePerson->Next; delete ActivePerson; ActivePerson = FirstPerson; }while(ActivePerson != NULL); return 0; }