Page 1 of 9 123 ... LastLast
Results 1 to 10 of 82

Thread: Horror of horrors! Linked lists in C

  1. #1
    Join Date
    Mar 2011
    Location
    South Dakota
    Beans
    1,134
    Distro
    Ubuntu 13.10 Saucy Salamander

    Arrow Horror of horrors! Linked lists in C

    My instructor just isn't breaking things down in enough detail and I don't know what to do about it. Trying to ask more questions is like beating a dead horse. There comes a point where there's no point anymore at all.

    What I'd like help doing is tracking through, line by line and assignment by assignment, what is happening with assignments when we change head to temp and then assign head's pointer to NULL. One distinction I need to pull out of this (or have recognized if you will) is the distinction between the whole struct and a member in the struct when talking about the assigment being made. In the end, another thing is seeing where there is an equivalent way to describe one or more of the assignments that occured.

    I attached the file containing the entire example code we were given. I'll use two lines of code from within the function called "void insert(int num)" below.

    So, now to try and give a more specific question(s) using two lines of code from our example code (location referenced in the paragraph above).

    If we say something like:

    Head = temp;
    Head -> nextPtr = NULL;

    When we use "Head" in the first line we are referring to the entire structure right? (That would mean everything in it as well right? The int and the pointer it contains).


    [Comment: By that, I meant to say: "hey, lets look at this "whole" in the context of being something that has stuff in it - not just make some generalization about it."]

    Then, in the second line, we are referring to just one of the two members in that struct - namely the pointer in it.

    [Comment: By this point (the point of considering that second line of code, in addition to the first - yes I'm looking at it as what the two lines are doing, together in my mind now) when I get to that second line, I'm seeing 3 things involved in my picture here, not just two. (1) The whole struct "Head" (2) The whole struct "temp" (3) The member "nextPtr"]

    I understand that Head is a *pointer* to memory but there [still] has to be some way to think of the difference between setting values to the entire thing and referring to just a member in it (pointer to memory or not).

    [Comment: The paragraph below ties in what I'm more concerned about. I can visualize the differenct between a whole something an a member inside it - I'm not a retard. It's sequentially tracking the assignments being made in the context of what it's being made to (whole or member) and especially what that means/ what it results in. Then it's to see if there is an equivalent way to view it (for instance if the whole "Head" equals the whole "temp" then when we later say "Head -> nextPtr = NULL" isn't that the same as saying "temp -> nextPtr = NULL" because Head was made equal to temp before that? See below...]

    It's not just to make that distinction but to grasp it in the context of what is actually happening with the assignments we make. (In the first line Head is being assigned the value of temp (which is itself an instance of this struct), and in the second line, just an element in Head is being assigned the value NULL - but we already assigned Head the value of temp so does that mean it's really the nextPtr in temp that is set to NULL?).

    Additionally but much lower priority: I know they always say it's not accurate to do this, but if I just had some image of something I already know that I could use to visualize linked lists and structs (linked list AND structs - one involves the other)... Something familiar to attach this new concept to... Some analogy... One that is simple in real life - boxes inside boxes not complicated thinkgs like skyscrapers, etc. You know? A good analogy.
    Attached Files Attached Files
    Last edited by ClientAlive; February 18th, 2012 at 11:28 PM.
    “ The best method for accelerating a computer is the one that boosts it by 9.8 m/s2. ”
    - Anonymous

  2. #2
    Join Date
    May 2008
    Location
    UK
    Beans
    1,450
    Distro
    Ubuntu 8.04 Hardy Heron

    Re: Horror of horrors! Linked lists in C

    in your code sample :
    Code:
    Head = temp;
    Head -> nextPtr = NULL;
    When we use "Head" in the first line we are referring to the entire structure right? (That would mean everything in it as well right? The int and the pointer it contains).
    You are not assigning the whole of temp into the Head variable.

    judging my the code snippet - both Head and temp are pointers, so what you are doing is setting Head to point to whatever temp is pointing to.

    Assuming that before that line Head pointed to another item in memory, that memory would still be intact, it just would not have Head pointing to it any more, and so long as something else was pointing to it - you will not loose that data.

    If you want to change the entire structure, you can change it element by element (like the 2nd line changes the nextPtr element), or you can change it all in one go :

    Code:
    *Head = *temp
    Will replace the content of the structure pointed at by Head, with the contents of the structure pointed at by temp (but the pointers stay pointing at the same areas of memory.

    I hope this helps.
    Tony - Happy to try to help.
    Unless otherwise stated - all code posted by me is untested. Remember to Mark the Thread as Solved.
    Ubuntu user number # 24044 Projects : TimeWarp - on the fly Backups

  3. #3
    Join Date
    Sep 2007
    Location
    Oklahoma, USA
    Beans
    2,271
    Distro
    Xubuntu 14.04 Trusty Tahr

    Re: Horror of horrors! Linked lists in C

    I'll probably regret this, Jake, but here's the analogy you asked for: A treasure hunt.

    That is, the game kind where you're given a note that says "Look in the hollow tree." You find the hollow tree, and there's another note in it that says "Try the refrigerator." In the refrigerator, you get still another saying "Go to the pantry." Finally in the pantry, you find the treasure you're looking for.

    Now you want to make the hunt a bit more complicated, so you go to the hollow tree, take out its note, replace it with a new one that says "Go to the woodshed" and finally hide the original tree note in the woodshed.

    That's how the multiple pointers and struct definitions work, using memory addresses rather than notes. To put your two lines into context you have to go back to the "malloc" call at the start of the function. This gets a block of memory just the right size to hold the "node" struct, and stores its memory address in the pointer "temp" for future reference. The "Head = temp" line copies that address into a second pointer "Head" and the next line then uses the struct definition's "nextPtr" value to determine which area of the struct to use, and stores NULL at that location.

    Yes, it's still the same memory area to which "temp" points. The reason for using two pointers instead of just one is to protect against possible failures. The "Head" pointer is more or less global and defines the entire list, which is a linked chain of "node" structs. If you're out of memory so that the malloc call cannot insert yet another node into the chain, it returns "NULL" rather than a valid memory address. Since you don't want to destroy the chain when this happens, you use the "temp" pointer to get the result, and copy it over to "Head" only if it contains a valid address.

    A better analogy for the linked list might be a physical chain, where each link corresponds to an entire "node" struct. In fact, that analogy is where the name "linked" originated back in the late 50s.
    --
    Jim Kyle in Oklahoma, USA
    Linux Counter #259718
    Howto mark thread: https://wiki.ubuntu.com/UnansweredPo.../SolvedThreads

  4. #4
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    2,112
    Distro
    Kubuntu 14.04 Trusty Tahr

    Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by ClientAlive View Post
    My instructor just isn't breaking things down in enough detail and I don't know what to do about it. Trying to ask more questions is like beating a dead horse. There comes a point where there's no point anymore at all.
    http://en.wikipedia.org/wiki/Linked_list

    No?

  5. #5
    Join Date
    Mar 2011
    Location
    South Dakota
    Beans
    1,134
    Distro
    Ubuntu 13.10 Saucy Salamander

    Arrow Re: Horror of horrors! Linked lists in C

    Quote Originally Posted by Tony Flury View Post
    in your code sample :
    Code:
    Head = temp;
    Head -> nextPtr = NULL;
    You are not assigning the whole of temp into the Head variable.

    judging my the code snippet - both Head and temp are pointers, so what you are doing is setting Head to point to whatever temp is pointing to.

    Assuming that before that line Head pointed to another item in memory, that memory would still be intact, it just would not have Head pointing to it any more, and so long as something else was pointing to it - you will not loose that data.

    If you want to change the entire structure, you can change it element by element (like the 2nd line changes the nextPtr element), or you can change it all in one go :

    Code:
    *Head = *temp
    Will replace the content of the structure pointed at by Head, with the contents of the structure pointed at by temp (but the pointers stay pointing at the same areas of memory.

    I hope this helps.

    That makes sense. You know, I think I was confusing myself about something. Conceptually, one would think theres something like that mirror within a mirror thing going on because of the fact that there's a struct within a struct (the next pointer). After I drew this diagram (attached to this post), and got to dwelling on it a little, I realized that you can't have memory within memory. When it comes to allocating memory it is just one level. Still, how does the compiler know when to stop? How is it that your compiler wouldn't enter something like an infinite loop and start allocating memory for memory for memory, add infinitum?

    So, in the end, I think I'm starting to grasp this. Also, I think maybe there is an important differece to be recognized between a pointer and a regular variable that isn't a pointer. A distinction that ties into the difference in behavior.

    Something I just pondered, I wonder if you were to assign a value to the next pointer in the struct's definition (an address) you would get that sort of thing => (Now the compiler probably wouldn't do it; but, conceptually, it would be like telling it to assingn memory within memory within memory, add infinitum). But we don't do that. We only decalare the next pointer in the struct's definition. Maybe that's why it stops at just one/ one level.


    Quote Originally Posted by JKyleOKC View Post
    I'll probably regret this, Jake, but here's the analogy you asked for: A treasure hunt.

    That is, the game kind where you're given a note that says "Look in the hollow tree." You find the hollow tree, and there's another note in it that says "Try the refrigerator." In the refrigerator, you get still another saying "Go to the pantry." Finally in the pantry, you find the treasure you're looking for.

    Now you want to make the hunt a bit more complicated, so you go to the hollow tree, take out its note, replace it with a new one that says "Go to the woodshed" and finally hide the original tree note in the woodshed.

    That's how the multiple pointers and struct definitions work, using memory addresses rather than notes. To put your two lines into context you have to go back to the "malloc" call at the start of the function. This gets a block of memory just the right size to hold the "node" struct, and stores its memory address in the pointer "temp" for future reference. The "Head = temp" line copies that address into a second pointer "Head" and the next line then uses the struct definition's "nextPtr" value to determine which area of the struct to use, and stores NULL at that location.

    Yes, it's still the same memory area to which "temp" points. The reason for using two pointers instead of just one is to protect against possible failures. The "Head" pointer is more or less global and defines the entire list, which is a linked chain of "node" structs. If you're out of memory so that the malloc call cannot insert yet another node into the chain, it returns "NULL" rather than a valid memory address. Since you don't want to destroy the chain when this happens, you use the "temp" pointer to get the result, and copy it over to "Head" only if it contains a valid address.

    A better analogy for the linked list might be a physical chain, where each link corresponds to an entire "node" struct. In fact, that analogy is where the name "linked" originated back in the late 50s.

    That's a pretty good analogy. I think I can work with that, thanks. Nice to see you around Jim.
    -------------------------

    On the attachment here - probably just illustrates my confusion, I'm getting past it though. It's starting to make sense. Thanks guys.
    Attached Files Attached Files
    “ The best method for accelerating a computer is the one that boosts it by 9.8 m/s2. ”
    - Anonymous

  6. #6
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,297
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Horror of horrors! Linked lists in C

    I think your main problem is you haven't yet grasped the concept of pointers.

    The entire instance of struct Node called “Head” is set to null.
    No, Head is a pointer. It is not an instance of struct Node, it's just the memory address of one.

    It contains two members: an int
    Called “x” and another instance of struct Node called nextPtr. NextPtr, in turn must have two
    Members in it since it's based off the same template “Node”.
    No, it contains a pointer to another instance of struct Node. It's just an integer storing the address of the next node. It is not the node itself.
    Last edited by Bachstelze; February 19th, 2012 at 02:37 AM.
    「明後日の夕方には帰ってるからね。」


  7. #7
    Join Date
    Sep 2007
    Location
    Oklahoma, USA
    Beans
    2,271
    Distro
    Xubuntu 14.04 Trusty Tahr

    Re: Horror of horrors! Linked lists in C

    That link posted by ofnuts is an excellent description of exactly how a linked list works, although I would pick a bone with the history it contains. I believe that the idea was invented independently at about the same time by a leading British computer scientist whose name escapes me at the moment, and by Newell, Simon, and Shaw. I even did so a decade later, not knowing it already existed, to make it easier to edit text files!

    To get along with C and any of its variations, you have to get the concept of pointers very clear in your mind. It's almost the central nervous system of the language. Many current systems make use of pointers to pointers to pointers (and so on, ad nauseum), and it's very easy to get lost.

    Drawing diagrams is the best way I know to deal with this. In your sample code, represent the "node" struct by a box that has two parts; one is the value itself and the other is a pointer to another instance of the node struct. What your two lines are doing is simply creating an instance of the struct, saving its address in "Head" and setting the pointer part to NULL to indicate that this is the last instance in the chain. The specific two lines you chose are executed only once, when creating the linked list originally. Other lines of the program are executed when adding or deleting links.

    Study the diagrams in that wikipedia article until you grok it well, and things will be a lot simpler!
    --
    Jim Kyle in Oklahoma, USA
    Linux Counter #259718
    Howto mark thread: https://wiki.ubuntu.com/UnansweredPo.../SolvedThreads

  8. #8
    Join Date
    Jun 2007
    Location
    Malvern, UK
    Beans
    992
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Horror of horrors! Linked lists in C

    Something I just pondered, I wonder if you were to assign a value to the next pointer in the struct's definition (an address) you would get that sort of thing => (Now the compiler probably wouldn't do it; but, conceptually, it would be like telling it to assingn memory within memory within memory, add infinitum). But we don't do that. We only decalare the next pointer in the struct's definition. Maybe that's why it stops at just one/ one level.
    The compiler doesn't magically know when to stop iterating over the list. Look at your printList() method to see how it doesn't print forever.

    Also, I think maybe there is an important differece to be recognized between a pointer and a regular variable that isn't a pointer.
    You bet there's a difference.

  9. #9
    Join Date
    Mar 2011
    Location
    South Dakota
    Beans
    1,134
    Distro
    Ubuntu 13.10 Saucy Salamander

    Arrow Re: Horror of horrors! Linked lists in C

    Well, after thinking about what's been said so far, and thinking about that diagram I'd drawn up, I had a couple realizations about what's really going on (at least I thought I did). I dug in and was off to a great start (at least I thought I was).

    So I have this awful habit of pulling these hail mary stunts with my code and not testing until I've written way too much in. Then, I figure I have all this time and effort into what I've done so far; and, when 3 pages of compiler errors burst onto the screen (ok it's not really 3 pages, but a lot), when that happens, I don't want to pare anything down. So I did it again.

    I got about half the code written, tried to compile and got a lot of errors. Was able to sort out almost all of them but two. Started out, I tried what I thought the fix to the problem was; then, when that didn't work I just started trying variation of syntax I could think of. Now I see either one, certain, compile error or annother - depending on how I change the syntax. I'm pretty sure I'm mostly on target (though there's likely a much simpler/ better allaround design). Well, I'll post my code just in case someone feels like giving me a little love... (I'm teasing)


    Code:
    /*
    Objective: Create a doubly linked list. Use a design in which it is the
    current node that is used to create a new node or to delete. Prev and Next
    are there for navigation and searching.
    
    Tip: 
    
    Status: 
    
    Next steps: 
    */
    
    #include <ctype.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct
    {
    	char Name[32];
    	char Phone[18];
    	struct Node *Prev;
    	struct Node *Next;
    }Node;
    
    Node *Curr = NULL;
    
    void Menu(); //Done
    char ValidSelection(char S); //Done
    void Insert(char InsName[], char InsPhone[]); //Done
    //Delete();
    //Search();
    void Print(int Selection); //Done
    
    int main(void)
    {
    	Menu();
    	char Selection = ' ';
    
    	Selection = getchar();
    	ValidSelection(Selection);
    
    	switch(Selection)
    	{
    		case 'A':
    		case 'a':
    		{
    			//insert
    
    			char Name[32];
    			char Phone[18];
    
    			printf("Enter a name...");
    			fgets(Name, 31, stdin);
    			printf("Enter a phone number...");
    			fgets(Phone, 17, stdin);
    
    			Insert(Name, Phone);
    
    			break;
    		}
    
    		case 'D':
    		case 'd':
    		{
    			//delete
    			break;
    		}
    
    		case 'S':
    		case 's':
    		{
    			//search
    			break;
    		}
    
    		case 'P':
    		case 'p':
    		{
    			//print
    
    			int Selection = 0; //initialize to zero?
    
    			printf("Would you like to: Print [A]ll or Print [E]ntry ?\n");
    			Selection = getchar();
    			ValidSelection(Selection);
    			Print(Selection);
    
    			break;
    		}
    	} //end switch
    
    return 0;
    } //end main
    
    void Menu()
    {
    	//display menu to user
    
    	printf("Please select one of the following...");
    	printf("[A]dd an entry\n");
    	printf("[D]elete an entry\n");
    	printf("[S]earch for an entry\n");
    	printf("[P]rint entries\n");
    	printf("[Q]uit\n");
    	printf("\n");
    } //end function
    
    char ValidSelection(char S)
    {	//accept user's selection - include validation
    
    	const char ValidSelection[13] = {'E', 'e', 'A', 'a', 'D', 'd', 'S', 's', 'P', 'p', 'Q', 'q', '\0'};
    	int i;
    
    	if(isalpha(S) != 0)
    	{
    		while(ValidSelection[i] != '\0')
    		{
    			if(S == ValidSelection[i])
    			{
    			return S;
    			}
    
    			else
    			{
    				printf("Invalid selection. Please enter your selection again...\n");
    				printf("\n");
    			}
    
    			++i;
    		}
    	}
    
    	else
    	{
    		printf("Invalid Selection. Please enter your selection again...\n");
    		printf("\n");
    	}
    } //end function
    
    void Insert(char InsName[], char InsPhone[])
    {
    	//create a new node with data entered by user
    
    	Node *Temp;
    	Temp = (Node *)malloc(sizeof(Node));
    
    	if(Temp != NULL)
    	{
    		Temp->Name = *InsName;
    		Temp->Phone = *InsPhone;
    
    		if(Curr == NULL)
    		{
    			Curr = Temp; //insert to curr - first entry
    			Curr->Prev = NULL; //make this the beginning of the list
    			Curr->Next = NULL; //make this the end of the list
    		}
    
    		else
    		{
    			Curr->Next = Temp; //insert to end of list
    			Temp->Next = NULL; //make temp the new end of the list
    		}
    	}
    } //end function
    
    //Delete()
    //{
    	//removwe an existing struct instance
    //} //end function
    
    //Search()
    //{
    	//search for a specific, existing instance and print the entire instance
    //} //end function
    
    void Print(int Selection)
    {
    	Node *Pointer = Curr;
    
    	if(Selection == 'A' || Selection == 'a') //user entered [A[ll)
    	{
    		//Print entire list
    
    		while(Pointer != NULL)
    		{
    			printf("%s", Pointer->Name);
    			printf("%s", Pointer->Phone);
    		}
    	}
    
    	else if(Selection == 'E' || Selection == 'e')//user entered [E]ntry
    	{
    		//code to print a single entry - use search function call
    	}
    
    	else
    	{
    		printf("Invalid entry\n");
    		printf("Please enter your selection again...\n");
    	}
    } //end function

    The two bolded lines in the "Insert()" function are the lines referred to in the compiler output. I also bolded the part in main that's tied to it.

    //Compiler output

    shine@BashBox ~/Programming/ProgrammingPlayground/LabPads > gcc LabPad[05].c -Wall -Werror -o LabPad[05].bin
    LabPad[05].c: In function ‘Insert’:
    LabPad[05].c:149: error: incompatible types when assigning to type ‘char[32]’ from type ‘char’
    LabPad[05].c:150: error: incompatible types when assigning to type ‘char[18]’ from type ‘char’
    cc1: warnings being treated as errors
    LabPad[05].c:161: error: assignment from incompatible pointer type
    ---------------------------

    Edit:

    Well, not sure this is the right solution, but it did get rid of my first two compile errors. Still doesn't run though.

    I changed those two lines to:

    Code:
    *Temp->Name = *InsName;
    *Temp->Phone = *InsPhone;
    Now I get some kind of syntax error when I try to run it. Good grief...

    ./LabPad[05).bin
    bash: syntax error near unexpected token `)
    -----------------------

    Edit:

    This thing the compiler is saying about an "assignement from incompatible pointer type" - I have no idea what it's talking about.

    I found another post here on the forums: http://ubuntuforums.org/showthread.php?t=673631

    In a response there he is told it's because he's not using malloc correctly. As for me, I'm pretty sure I'm using it exactly as the example code we were given:

    //Example code we were given:

    temp = (struct Node *) malloc (sizeof(struct Node));
    Code:
    //My line of code for that - note that I used typdef in my struct definition
    
    Temp = (Node *)malloc(sizeof(Node));
    What gives?
    Last edited by ClientAlive; February 21st, 2012 at 01:38 AM.
    “ The best method for accelerating a computer is the one that boosts it by 9.8 m/s2. ”
    - Anonymous

  10. #10
    Join Date
    May 2007
    Location
    East Yorkshire, England
    Beans
    Hidden!

    Re: Horror of horrors! Linked lists in C

    The incompatible pointer type is because Prev and Next are of type "struct Node*", but the compiler has no idea what a "struct Node" is. You haven't defined it. What you have done, is defined an anonymous struct, and typedef'd it.

    The incompatible types are because you're trying to assign to a char[] from a char. These are clearly not the same type.
    Website | Blog | The Arch Hurd Project

    If you want to ask about something I posted, send a PM, as I don't watch many threads

Page 1 of 9 123 ... LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •