CODEWITHSUNDEEP
cinsertlinked-list
mintbox
mintbox

Reputation: 167

C Linked List : How to insert node at front

In the textbook "Fundamentals of Data Structures in C", (by Horowitz Sahni Anderson-Freed)

they present the following code

as a method of inserting a node

after some arbitrary node x in a linked list :

void insertNode(nodePtr *listPtr, nodePtr insertLoc, int data)
{
   nodePtr temp = (nodePtr)malloc(sizeof(*temp));
   temp->data = data;
   if(*listPtr) // not empty
   {
       temp->next = insertLoc->next;
       insertLoc->next = temp;
   }
   else //empty
   {
       temp->next = NULL;
       *listPtr = temp;
   }

}

Therefore, the following calls would result to :

nodePtr head = NULL; insertNode(&head,head,10); // 10 insertNode(&head,head,20); // 10 -> 20 insertNOde(&head,head,30); // 10 -> 30 -> 20

My question : How is it possible to insert a node at the front of the list?

Upvotes: 1

Views: 2011

Answers (3)

wildplasser
wildplasser

Reputation: 44240

The function in the book is complete madness, IMHO. (maybe the book is about C++ ?)

  • hiding a pointer behind a typedef is confusing, and bad style
  • casting malloc()s return value is not needed, potentially dangerous, and bad style
  • parentheses after sizeof are not necessary
  • the function design is strange: passing three args where only two are needed, returning void.

A possible alternative function which could insert at the top, would be by using insertLoc instead of listPtr in the condition:

void insertNode(nodePtr *listPtr, nodePtr insertLoc, int data)
{
   nodePtr temp = malloc(sizeof *temp );
   temp->data = data;
   if (insertLoc) // Position requested
   {
       temp->next = insertLoc->next;
       insertLoc->next = temp;
   }
   else // No: insert at top
   {
       temp->next = *listPtr;
       *listPtr = temp;
   }
}

Upvotes: 2

Turo
Turo

Reputation: 4914

I changed the function, so a NULL insertLoc means insert as head

void insertNode(nodePtr *listPtr, nodePtr insertLoc, int data)
{
   nodePtr temp = (nodePtr)malloc(sizeof(*temp));
   temp->data = data;
   if(*listPtr) // not empty
   {
    if (!insertLoc) {
        temp->next = *listPtr;
        *listPtr = temp;
    } else {  
       temp->next = insertLoc->next;
       insertLoc->next = temp; 
    }
   }
   else //empty
   {
       temp->next = NULL;
       *listPtr = temp;
   }
}

Upvotes: 0

jforberg
jforberg

Reputation: 6752

Linked lists are a very simple data structure where each node contains a payload (int in your case) and a pointer to the next node. The list is terminated by a pointer to the special "NIL" node, in C usually just a NULL pointer.

from wikipedia Image: Yonkeltron at English Wikipedia

To prepend to the list you just create a new node and assign its NEXT pointer to the previous head.

Also, don't forget to check the return value of malloc. Or use g_malloc from glib which does this automatically.

nodePtr cons(nodePtr tail, int data)
{
  nodePtr head = malloc(sizeof(*nodePtr));
  assert(head);
  head->data = data;
  head->next = tail;
  return head;
}

Upvotes: 2

Related Questions