Inserting node in linked list in C++ : Linked List – 1

Question. We are given a linked list pointed to by head. We wish to insert a given node at the head of the linked list.

Solution.

Let each node of the linked be of type Node defined thus:

typedef struct Node

{

struct Node *next;//pointer to next element in list.

void *data; //data contained in the node.

} Node;

—–

Note that we need to write: struct Node *next instead of simply Node *next inside the struct definition since the typedef is not valid at that stage.

——

We can write the insert_at_head function as follows:

—–

// data contains the data to be inserted.

// function returns true if insertion succeeds, else it returns false.

bool insert_at_head ( Node **head, void *data)

{

Node *myNode = new Node;

if (! myNode)

// memory allocation failed.

return false;

myNode -> data = data;

myNode -> next = *head;

*head = myNode;

return true;

}

——

Note that we need to take a pointer to a pointer as argument (for head). That is because these arguments are passed by value. Hence if we wrote Node *head instead of Node **head, a copy of the pointer to the first element of the linked list would be passed to the insert function. The function would then change the contents of the local copy (i.e. make it point to myNode). However, the original head pointer would be unaffected and would continue to point to where it was pointing to earlier. Hence we need to pass a pointer to the head pointer as argument.

—-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: