CODEWITHSUNDEEP
cdata-structureslinked-list
bks4line
bks4line

Reputation: 515

Writing a proper push() function for a singly-linked list.

http://cslibrary.stanford.edu/103/

Please find some time to go through the wrong push function in this linked list basics document. I just followed the same implementation of this function. So according to the document the addition of data to the head of the list shouldn't happen. But mine works perfectly fine with the way they said it has to be implemented. I am very confused about finding out what the problem is?

Here is the code:

#include<stdio.h>
#include<stdlib.h>

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

typedef struct node Node; /* Utilize a typedef for Node rather than typing
                             struct Node everytime we declare a node. */

Node* BuildOneTwoThree() {
    Node* head =NULL;   // pointer called head.
    Node* second =NULL; // pointer to second memory block
    Node* third = NULL; // pointer to third memory block

    head = (Node*)malloc(sizeof(Node));   //allocate a memory block of size node
                                          //in the heap and head pointer will 
                                          //point to this memory.
    second = (Node*)malloc(sizeof(Node)); //allocate a memory block of size node 
                                          //in the heap and second pointer will 
                                          //point to this memory
    third = (Node*)malloc(sizeof (Node)); //allocate a memory block of size node 
                                          //in the heap and third pointer will 
                                          //point to this memory

    head->data = 1;
    head->next = second; //the next pointer of node type will point to another 
                         //pointer of node type which is second!!

    second -> data = 2;
    second -> next = third;

    third -> data = 3;
    third -> next = NULL;
    return head;
}


Node* WrongPush(Node* head, int data) {

    Node* newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode; // NO this line does not work!
    return head;
}

Node* WrongPushTest() {
    Node* head = BuildOneTwoThree();
    Node* current = WrongPush(head, 4);
    return current;
}

int main(){
    Node* ptr = WrongPushTest(); //My question is why does the wrong push 
                                 //test implementation that I setup work?
    while(ptr!=NULL) {
        printf("%d\n",ptr->data);
        ptr=ptr->next;
    }
}

Upvotes: 2

Views: 1576

Answers (1)

embedded_guy
embedded_guy

Reputation: 1967

The first thing I notice is that you actually changed the implementation as written in the document you referenced. The document implements WrongPush as follows (which I modified to use your structure definition):

void WrongPush (Node * head, int data) {
    Node * newNode = malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = head;
    head = newNode;  /* This will not work because you are not
                        modifying head in the calling function. */
}

The problem with your implementation is that it is not easily scalable. For example, using your code, try WrongPushTest as follows:

Node * WrongPushTest() {
    Node * head = BuildOneTwoThree();
    Node * current = WrongPush(head, 4);
    current = WrongPush(head, 5);
    current = WrongPush(head, 6);
}

The output will not be something that the programmer had intended. The goal is to have a push function that utilizes the original head without having to create a new node everytime you push another node onto the linked list. The example they use in the document is as follows:

void Push(Node** headRef, int data) {
    Node * newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}

Notice that I am not returning a pointer to the newly created head as was done in your example. The above allows us to always push a new node onto the head of the original linked list by directly manipulating the original head pointer.

Node * PushTest() {
    Node * head = BuildOneTwoThree();
    Push (&head, 4);
    Push (&head, 5);
    Push (&head, 6);
    return head;
}

Hopefully this helps to clear things up for you!

Upvotes: 2

Related Questions