Thread: 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.

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.

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.

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.