Singly-Linked Lists: Ultimate

[bsdpowa]

Hello all,
I'd like, very much, to understand linked-lists.I've read many texts on the subject and tried many source codes but none of them seemed to fit my needs (one from daniweb is pretty close but it's in C) so I, as desperate as I can be, beg you for mercy.
I'd like to tell you not to suggest me to look for STL lists or to search the forums or even to buy a book on data structures.I've seen it all and I've got it all, belive me.I wouldn't come here if I'd have another option, but I don't.
I have a C++ exam next month and I understand pretty much everything except these damned linked-lists.Many slepless nights and even more headaches so I've decided to try this forum (since they all refused/were too lazy or there was some unnatural power that forbid them to help me on other forums).

I'm going for C++ singly-linked lists with structures and basic operations (add beginning, add end, display, remove node, remove list).I'll provide some code and I'd like you to continue with adding code and explanation (I'd really appreciate a good and detailed explanation because I need to understand them, not just to get the source code) so some other time maybe others can learn from this thread, that's why I called it Ultimate singly-linked lists.

STARTING
We need a structure with data ofcourse.

struct node
{
char name[10];          //this is a char array where we will store the name user will input
int age;                   //we are going to store the age here

node* p_next;         //this is a pointer to the next node
}

Now we make a main and menu functions.I separated these two because when a user will finish his adding/deleting he might want to return to the menu for some more options.

int main()
{
menu();                  //we call the menu function 
return 0;
}

void menu()
{
node* p_beginning = new node;                //we create a new pointer which will point to the beginning of the list, that is first node
p_beginning = NULL;                                // and we set it to point to nothing at the momment

int input;
	do 
	{
		cout << "MENU" << endl << endl;
		cout << "[1] Add to the beginning" << endl;
		cout << "[2] Add to the end" << endl;
		cout << "[3] Display" << endl;
		cout << "[4] Delete a node" << endl;
		cout << "[0] Exit" << endl << endl;
		cout << "Option: ";
		cin >> input;

		switch (input)
		{
		case 1:
			{
				beginning();          //we call a function where we will add a node to the beginning
			}
		case 2:
			{
			}
		case 3:
			{
			}
		case 4:
			{
			}
		case 0:
			{
				return 0;
			}
		}
	} while (input!= 0);
}

That's everything I understand.Now questions:

1.In the menu we created a new pointer called p_beginning which will (in the future) point to the first node or to the beginning of the node but now we set it to point to nothing -> why is that?
2.Is that everything or should we add some more lines to the code (stick to the stuff related to linked-lists)?

OK, can anyone now make similar stuff like I did.
Now our next job is to start adding the nodes, right? At the beginning.Now we will make a function "void beginning()" and I'm sure we'll have to add some parameters to the menu call function beginning().

So...

void beginning()
{
}

It doesen't matter if 15 people reply to this post about the beginning() function, more the better.It's good to see how one would make this by himself.So, can you help?

[Drowzee]

1. Think of it like this: The pointer to the beginning is the anchor, and what you use it for is to point to the first entry in your singly-linked list (SLL). Until you use it, however, it's a good idea to set it to point to NULL just so you don't accidentally use an uninitalized pointer later on, which could point to an area of memory you don't want it to.

2. If you're using C++, adding nodes is easy.

struct node
{
      node *next;//Points to the next node
};

int main()
{  
   node* head;//Pointer to be used to point to first element
   node* trans;//Pointer to currently-viewed node (Optional, but I like it.)
   head = NULL;
   trans = NULL;
   
   //To build the first item, it's like this:
  head = new node;
  trans = head;
  trans->next = NULL; //For safety purposes

  //To add a node:
  trans->next = new node;
  trans = trans->next; //Advance to point at new node.
  trans->next = NULL; //Now that you're in the new node, set the pointer for safety.

//To delete entire list:
  trans = head; //Go back to start.
  while(trans->next !=NULL) //As long as there's another node...
  { 
     head = trans;
     trans=trans->next;
     delete head;
     head = NULL;
  }
  //Cleanup last node: head is NULL, trans is at last node.
  delete trans;
  trans = NULL;
return 0;
}

Does that help?

[bsdpowa]

I didn't understand that.There isn't any input data so I don't know how would I put data into the list.
If I understood correctly we must first put some data into the list and don't care about it just so we know next time where to start?
I'm sorry but I didn't get a thing what you were saying, that's why I wanted to make SSL together with you because everyone do the lists by their own way and I get even more confused.
Could you try to implement your way into the beginning() function or at least try to explain what you were doing there and why?

[Drowzee]

S'okay. Let's expand the node I wrote.

struct node
{
   int blar[3];
   node *next;
}

To put data in:

int main()
{
   node* head;//Pointer to be used to point to first element
   node* trans; /*Pointer to currently-viewed node (Optional, but I like
 it.)*/
   head = NULL;
   trans = NULL;
/*Let's make a node! Declare an instance of node with keyword new.
 That allocates the amount of memory needed to hold the struct.*/

head = new node; 

/*The head pointer now refers to the first node in the list, which has 
the elements of int blar[3] and node*next.*/

trans = head;
 /*The second pointer, the TRANSverse, is used to, well, transverse the
 linked list more simply, and aids in cleanup. Think of it like as a 
bookmark, to help you keep your place. By assigning it to 'head', the 
trans pointer now also points to the first node. Let's do some things to 
the array now.*/


/* To change values in the node, you can use the arrow operator (->) 
to access the elements like so:*/
trans->blar[0] = 10;
trans->blar[1] = 23;
trans->blar[2] = -9;
/*These values are now stored in the blar array of the first node. 
Notice that it's exactly the same sort of code you're used to with array 
assignments. Just remember that you need to use the arrow operator if 
you're working with a pointer to a struct, and a dot operator if you're 
working with the struct directly (i.e., if you just declared a node called 
'nyaaaw' in main and wanted to work on blar, you'd do nyaaaw.blar[0] =
 15;).*/

trans->next = NULL;
/*Generally, you'd do this immediately after creating the node, but I 
don't want to rewrite this again. What you're doing here is not only safe
 coding practice (you're not pointing to some random location in memory
 that you might screw up if you make a mistake with your pointers), but
 it's also helpful when the time comes to locate the end of the SLL, 
because only the final 'next' pointer will be NULL.*/

/*Moving on, make a node on the end of the SLL. 
Since we're already pointing trans to the current node, we can declare 
another instance of node and hook it to the existing node by using 
trans->next, which is equivalent to head->next, because they point to 
the same place.*/

trans->next = new node;
trans=trans->next;

/*trans->next was assigned a new value to a valid piece of memory, 
and is no longer null. So, we can tell trans to give itself the reference 
for this new piece of memory, moving it along the linked list. At this 
point, head and trans are no longer equal, but head->next and trans 
ARE equal (that is, they point to the same location in memory).*/

/*Remember to be a good clean coder, set the pointer to the next node (which doesn't exist) to NULL.*/
trans->next = NULL.

//Poppa's got a brand new blar! Let's fill it.
trans->blar[0]=1;
trans->blar[1]=2;
trans->blar[2]=1000; 

/*At this point, check the value of trans->blar[2] to the value of 
head->next->blar[2]. They are the same, because they point to the 
same area in memory.*/

/*Make one more node for good measure.*/
trans->next = new node;
trans=trans->next;
trans->next =NULL;
trans->blar[0]=0;
trans->blar[1]=1;
trans->blar[2]=2;
/*Whee! Now, trans->blar[2] is equal to head->next->next->blar[2]! 
OMGEUREKAPWNZED!*/

/*Now, you can get fancier with this, but let's go through the deletion 
process. If you don't clean up after yourself, you create a memory leak,
 which can constrain system resources until reboot if your compiler isn't
 smart enough to pick up after you.  Because you keep setting 
trans->next to NULL in the last node of the SLL, you have a great way 
to tell if you are at the end of the list, so you can automate the 
deletion process.*/

//To delete entire list:
  trans = head; /*Go back to start, trans and head both point to the 
first node.*/

/*As long as there's another node, run the loop below.*/
  while(trans->next !=NULL) 

  { 
     head = trans; /*Move the head to refrence the node currently referenced by trans8?
     trans=trans->next; /*Move trans to the next node (guaranteed to be valid by the while loop!) */

     delete head; /*Free the memory that head points to. Head is now 
not pointing to valid memory.*/
     head = NULL; /*Just to be safe, NULL head. It's not necessary at 
all, but I want to make a point that you never let your pointers dangle.*/
  }
/*The above loop will systematically delete all nodes except for the 
last. The reason for this is that the while loop checks for trans->next to
 be NULL, terminating the loop before the code inside runs. So, there's a
 little more cleanup to do. head is already nulled, so no need to worry 
about that.*/

  //Cleanup last node: head is NULL, trans is at last node.
  delete trans; //Free the last piece of memory
  trans = NULL; //make trans safe.
return 0; //get the heck outta dodge.
}

Is that clearer? I don't think I can be any more clear without pictures.

[bsdpowa]

I didn't look at the explanation yet, just wanted to run it first and....what the heck is "test" since it's not initialized? Thank you very much for your time.

[jhdobbins]

i just wanted to say i loved the line..

/*Whee! Now, trans->blar[2] is equal to head->next->next->blar[2]!
OMGEUREKAPWNZED!*/

thank you for that Drowzee :)

[Drowzee]

Whoops. Test is supposed to be 'trans'. I wrote this all without a compiler, so I didn't catch the typo.

Fixed it.

And I also started to smile at 'OMGEUREKAPWNZD!'. I think I'll start using that on another forum.

[bsdpowa]

I think I understand, thank you very much.
I'm sure I'll have a question or two tommorow.