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 Allocation

List nodes are created on demand. When data needs to be inserted, a new list node must be allocated to hold it. The malloc() function presented earlier is the basis for this allocation. The statement

newPtr = (node_ptr)malloc(sizeof(node_t));

or

newPtr = (node_t*)malloc(sizeof(node_t));

allocates our new node. Assuming that malloc() does not return NULL, we may now begin to assign the data portion of our node with values. Here's a quick example, using the coordinate node defined earlier:

newPtr->x = 10;

Now that we have the basis for allocating nodes, we create a function that will encapsulate all of the node allocation functionality into one block of code.

node_t* Allocate()
{
  node_t *newNode;            // our new node

  // request memory for our node
  newNode = (node_t*)malloc(sizeof(node_t));

  // error checking
  if (newNode == NULL)
    printf("Error: Unable to allocate new node.\n");
  else
    newNode->next = NULL;  // allocation succeeded, set the next link to NULL

  return newNode;
}

There we have our basic node allocation function. We use this function like so:

node_t *myNode;
myNode = Allocate();

Despite the fact that the function Allocate() prints out an error message if the pointer is NULL, we should still verify that myNode is not NULL before trying to use it. Should this be the case, you may now use the data portion of the node and fill it with values.

Initialization

Initialization of a linked list is very quick and easy. We simply assign the value of NULL to the head of the list. This function only needs to be called once, and some of you may choose to not even bother. However, for the sake of this article, we will use it.

void Initialize(node_t **ptr)
{
  *ptr = NULL;
}

Using the definition of head given earlier, you would call this function as

Initialize(&head);

Next : Node Insertion - Unsorted