CODEWITHSUNDEEP
clinked-listappend
LeTigre
LeTigre

Reputation: 460

append at end of linked list

I've been working on implementing linked lists in C. so before anyone yells at me: Yes this is "homework". I've been trying to solve and work on the "Linked List Basics" from Nick Parlante - freely available under: http://cslibrary.stanford.edu/103

Function: insert element at end of linked list

I stumbled on a Implementation Problem and managed to build a workaround: if I use a "EndPointer" in a LList I can use the return function to set the EndPointer of the function to hand over the new ReferencePointer and then change it within main.

Code - working fine but beeing a workaround:

// within main
lastPtrRef = _pushEnd(lastPtrRef, i);

// == function: push to end
node** _pushEnd(node **endRef, int value)
{
    // 1) allocate stack mem / make room for new element
    node *newNode = malloc(sizeof(node));

    // do the data work
    newNode->value = value;

    // 2) make  element point to NULL (fo beeing the new last element
    newNode->next = NULL;

    // 3) make old last element point to new element
    *endRef = newNode;

    return &(newNode->next); // more readable then vers. below
    // this returns the mem address only of the pointer of the node!!!
    //return (&((*endRef)->next));

}

==============================================================================

this is what i have so far as doing all the work within the function but it actually does not work. any hints on which point I'm not getting?!

void _pushEnd(node **endRef, int value)
{
// 1) allocate stack mem / make room for new element
node *newNode = malloc(sizeof(node));

// do the data work
newNode->value = value;

// 2) make  element point to NULL (fo beeing the new last element
newNode->next = NULL;

// 3) make old last element point to new element
*endRef = newNode;

}

Could it be, that I would actually need a pointer to the reference pointer to actually change the contents of the pointer to the last element (within scope: main), so that I currently seem only to be modifying the local variable "endRef" and not its contents?!

Any help would be appreciated...

Edit: The idea is to append without using a dummy node at the beginning of the LList.

my struct looks like this:

typedef struct node     {
int     value;
struct node *next;      } node;

main - local variables (stack):

node *head = NULL;
node **lastPtrRef = &head;

Edit: Most of the propositions ended up returning the refPointer anyway. But maybe that's not such a bad Idea anyway, as it wont require one further refPointer to the refPointer.

Thx for all your help and the many usefull comments!

Upvotes: 2

Views: 8787

Answers (4)

Bernd Elkemann
Bernd Elkemann

Reputation: 23550

_pushEnd is telling main what main already knows: where the pointer is stored.

You have many options, including:

  • pushEnd gets node* (not node**), returns the new pointer and main stores it in its variable

  • pushEnd gets node** and overwrites main's value by itself, no need to return anything.

EDIT:

Example for Point 1:

node* pushEnd(node* end, int entry); // returns new end.
int main() {
    node* end = newlist();
    int i=0;for(;i<10;++i) {
        end = pushEnd(end, i);
    }
}

Example for Point 2:

void pushEnd(node** ptrToEnd, int entry); // changes *ptrToEnd
int main() {
    node* end = newlist();
    int i=0;for(;i<10;++i) {
        pushEnd(&end, i);
    }
}

Upvotes: 3

wildplasser
wildplasser

Reputation: 44250

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

struct node *root = NULL
   , **lastPtrRef = &root;

 // within main
lastPtrRef = pushEnd(lastPtrRef, i);

//function: push to end; return new pointer to tail->next

struct node  **pushEnd(struct node **p, int value)
{
    struct node *p;

    // 0) is it really the end ?    
    while (*pp) {pp = &(*pp)->next; }

    // 1) allocate
    p = malloc(sizeof *p);

    // do the data work
    p->value = value;

    // 2) make  element point to NULL (fo beeing the new last element
    p->next = NULL;

    // 3) make old last element point to new element
    *pp = p;

    return &p->next;

}

Or remove the p variable, since it is not needed:

struct node  **pushEnd(struct node **p, int value)
{

    while (*pp) {pp = &(*pp)->next; }

    *pp = malloc(sizeof **pp);
    (*pp)->value = value;
    (*pp)->next = NULL;

    return &(*pp)->next;

}

Upvotes: 1

cnicutar
cnicutar

Reputation: 182639

*endRef = newNode;

Before you do that you have to make the old endRef->next point to newNode.

if (*endRef)
    (*endRef)->next = newNode;

*endRef = newNode;

Upvotes: 3

Noxbru
Noxbru

Reputation: 472

I think your problem is with the line of the return:

return (&((*endRef)->next));

As you have done before this *endRef = newNode; it is now returning the direction of the next element of the node you have just created.

Upvotes: 1

Related Questions