Contents  Introduction  Getting Started  The Linked List  Node Design  Node Allocation  Node Insertion  - Unsorted  Linked List  Traversal  Searching  Node Deletion  End of File  Source code  Printable version  Adobe PDF version     The Series  Linked Lists

Node Insertion - Unsorted

We will now cover how to insert freshly allocated nodes into a linked list. Let's take a step back for a moment and consider insertion into an array. When using an array, you would typically add data to the end of the array, unless the data was sorted, in which case you would insert the data using some other method. We could do the same for an unsorted linked list, but this would require finding the last node because only the next to last node "knows" where the last node is located in memory. However, the head of the linked list points to the first node in the list, so a new node can be inserted at the front of the list without any extra work. You can see the steps of inserting three nodes into a linked list in Figure 1.3.

And now the code:

void InsertFront(node_t **head, node_t newRecord)
{
  node_t*  newNode;      // pointer to a new node
  newNode = Allocate();

  if (newNode == NULL)
  {
    printf("Error: Not enough memory to allocate node.\n");
    return;
  }

  // fill the node with data
  newNode->id = newRecord.id;

  // insert at the front of the list
  newNode->next = *head;

  // move the head of the list to the new node
  *head = newNode;
}

To try to sum up this function in English: a new node is allocated and its data is filled; the new node's next field is set to point to the head node; the head is then reset to point to the new node. This function also works if the list is empty (*head = NULL) since we want the list to be NULL-terminated.

Next : Linked List Traversal