Linked List/Adding Element To Beginning of List

Printable View

12-31-2014
EricRoberts

Linked List/Adding Element To Beginning of List

I am teaching myself C and have a couple books on the subject. I am totally at a loss for exactly what this exercise is asking for.

Code:

// Write a function called insertEntry() to insert a new entry into a linked list. Have the procedure take as arguments a pointer to the list entry to be inserted (of type struct entry as defined in this chapter), and a pointer to an element in the list after which the new entry is to be inserted. // The function dveloped in exercise 2 only inserts an element after an existing element in the list, thereby prenting you from inserting a new entry at the front of the list. How can you use this same function and yet overcome this problem? (Hint: Think about setting up a special structure to point to the beginning of the list.) #include <stdio.h> struct entry1 { int value; struct entry1 *next; }; struct entry1 n0, n1, n2, n3, nInsert, *insert = &nInsert, *after = &n3, *list_pointer = &n1; void insertEntry(struct entry1 *insert, struct entry1 *after) { if (after->next == &n1) { insert->next = &n2; list_pointer = insert; } insert->next = after->next; after->next = insert; } int main (void) { n1.value = 100; n2.value = 200; n3.value = 300; nInsert.value = 20; n0.next = &n1; n1.next = &n2; n2.next = &n3; n3.next = (struct entry1 *) 0; insertEntry(insert, &n0); while (list_pointer != (struct entry1 *) 0) { printf("%i\n", list_pointer->value); list_pointer = list_pointer->next; } return 0; }

This is a working version of the exercise, but I don't think I'm doing what's asked. I was able to add an element to the beginning of the list using an if statement, not creating a special structure that points to the beginning of the list.

How would I go about creating a special structure that points to the beginning of the list to add a new element at the beginning of the list?

Thank you for your help.
12-31-2014
iMalc

Here is a little tip to point you in the right direction.
First consider:
How would you represent an empty list? And how would you insert an item into an empty list?

The answer to that should also tell you that the prototype of your insertEntry function is not right.
12-31-2014
rcgldr

For the second part, the problem apparently wants you to use an instance of a node (struct entry1) as a dummy node that points to the first node of a list, so that you only need the function that you write for the first part.

An alternative is to have the next pointer as the first member of the struct, since C / C++ guarantees that the address of the first member of struct is the same as the address of the struct. This would allow the dummy node to be a different structure that only contains a next pointer, but you'd have to cast it to use with the function written in the first part, and I don't know if this alternative would be allowed for this problem. and if this is homework, it might seem that you got too much help for this assignment.
12-31-2014
nul

Don't get too held up on the actual phrasing of the book. They want you to be able to use a function to add a node to a linked list using the prototype from the first exercise. How you do this is a matter of taste.

EDIT: The use of global's is not necessary for this problem.

Also, could you explain this conditional statement:

Code:

list_pointer != (struct entry1 *) 0
12-31-2014
rcgldr

Quote:

Originally Posted by nul

Don't get too held up on the actual phrasing of the book. They want you to be able to use a function to add a node to a linked list using the prototype from the first exercise.

The problem statement is pretty clear about this: The function dveloped in exercise 2 only inserts an element after an existing element in the list, thereby prenting you from inserting a new entry at the front of the list. How can you use this same function and yet overcome this problem? (Hint: Think about setting up a special structure to point to the beginning of the list.) .

So the existing function that inserts after an element is to be used to insert after a dummy element that is a pointer to the first element of the actual list. Not a very interesting way to handle this issue.

As an option if the function took a pointer to pointer to element it would eliminate needing special code to insert at the beginning of a list that only uses a single pointer to the first element of the list.

Code:

node * plist = NULL; /* initial list pointer for empty list */ /* ... */ node * pcurrent; node * plast; /* ... */ pcurrent = malloc(sizeof(node)); /* ... */ insertnode(&plist, pcurrent); plast = pcurrent; /* ... */ pcurrent = malloc(sizeof(node)); /* ... */ insertnode(&(plast->next), pcurrent); plast = pcurrent; /* ... */
01-01-2015
EricRoberts

Hi, you guys are awesome thanks for your replies and thanks for getting back to me.

I didn't do the best job describing this problem, but this book hasn't gotten into nodes yet (oh, never mind, now I see node is just referring to structure that make up a linked list).

I will try to answer these in order.

Quote:

Originally Posted by iMalc

Here is a little tip to point you in the right direction.
First consider:
How would you represent an empty list? And how would you insert an item into an empty list?

The answer to that should also tell you that the prototype of your insertEntry function is not right.

I still need to think about this more. I thought the prototype might not be right, but the first argument is definitely right because it says takes as argument a pointer to a definition of type structure entry as defined in this chapter.

structure entry as defined in the chapter by the way looks like this:

Code:

struct entry { int value; struct entry *next; };

(i have to add the struct entry1, because I get errors if I use the tag entry for the structure.)

2 variables of type struct entry are defined as follows.

Code:

struct entry n1, n2 n1.next = &n2;

The code given in the book to insert a struct entry called n2_3 after n2 in the list is a follows.

Code:

n2_3.next=n2.next; n2.next=&n2_3;

The first exercise was just a matter of getting this code to execute correctly with the arguments presented to the function. I thought perhaps the second argument shouldn't be a pointer to a structure and maybe just a pointer to an integer or something, but thinking about that sort of confuses me and I haven't had a chance to work with that idea yet.

But yeah, the first exercise was basically copying the code from the book and getting it to execute properly. I'm still pretty stuck on the second part.
01-01-2015
EricRoberts

Quote:

Originally Posted by rcgldr

For the second part, the problem apparently wants you to use an instance of a node (struct entry1) as a dummy node that points to the first node of a list, so that you only need the function that you write for the first part.

An alternative is to have the next pointer as the first member of the struct, since C / C++ guarantees that the address of the first member of struct is the same as the address of the struct. This would allow the dummy node to be a different structure that only contains a next pointer, but you'd have to cast it to use with the function written in the first part, and I don't know if this alternative would be allowed for this problem. and if this is homework, it might seem that you got too much help for this assignment.

Yes, I started doing what you are saying in the second paragraph, but I was confused as to why a structure would contain only one element--being the next pointer pointing to the structure written in the first part. It seemed like sort of a nonsensical way to approach the problem (I thought structures were supposed to group like elements together), so I figured I was totally on the wrong track with that idea.

It's not homework btw, I am just reading a text book and doing the exercises in the order presented and got stuck.
01-01-2015
EricRoberts

Quote:

Originally Posted by nul

Don't get too held up on the actual phrasing of the book. They want you to be able to use a function to add a node to a linked list using the prototype from the first exercise. How you do this is a matter of taste.

EDIT: The use of global's is not necessary for this problem.

Also, could you explain this conditional statement:

Code:

list_pointer != (struct entry1 *) 0

I think in some instances I am just getting caught up on the phrasing, because most of the solutions in this book are simple codes. Once things start getting too complex I figure I am on the wrong track.

Also, yeah that's correct, the global's weren't there in the original code, but I messed with it a lot and ended up moving them from the Main() Function to Global, thinking I might need to reference them in the InsertEntry Function.

Code:

list_pointer != (struct entry1 *) 0

According to the text, "You can use the null pointer to mark the end of a list by storing this value in the pointer field of the last entry in the list...You see in Chapter 12, how this assignment statement can be made a bit more readable."

"The statement that follows the printf() call, list_pointer = list_pointer->next; has the effect of taking the pointer from the next member of the structure pointed to by list_pointer and assigning it to list_pointer." The for loop is being executed until the list pointer is equal to the value of null, which is assigned to n3.next. When it reaches that point, the loop is stopping and is printing the values contained in each of the value fields.

The (struct entry1 *) 0 is the type cast operator, saying while list_pointer is not equal to the null value, and once it reaches the value of n3.next, it find the null value and exits the loop. Doing my best here to explain that, because I am pretty new to learning this haha.

It was a code presented in the book, I'm guessing there might be another way to write the same thing.
01-01-2015
EricRoberts

Quote:

Originally Posted by rcgldr

The problem statement is pretty clear about this: The function dveloped in exercise 2 only inserts an element after an existing element in the list, thereby prenting you from inserting a new entry at the front of the list. How can you use this same function and yet overcome this problem? (Hint: Think about setting up a special structure to point to the beginning of the list.) .

So the existing function that inserts after an element is to be used to insert after a dummy element that is a pointer to the first element of the actual list. Not a very interesting way to handle this issue.

As an option if the function took a pointer to pointer to element it would eliminate needing special code to insert at the beginning of a list that only uses a single pointer to the first element of the list.

Code:

node * plist = NULL; /* initial list pointer for empty list */ /* ... */ node * pcurrent; node * plast; /* ... */ pcurrent = malloc(sizeof(node)); /* ... */ insertnode(&plist, pcurrent); plast = pcurrent; /* ... */ pcurrent = malloc(sizeof(node)); /* ... */ insertnode(&(plast->next), pcurrent); plast = pcurrent; /* ... */

Hi yes, this is absolutely correct, the reading of the exercise. I started referencing another text on linked lists, and it seems to handle the issue more of the way in that you are presenting in your code. The original text I was reading though hadn't presented some of those ideas at that time.