C Tutorial

Back to Tutorials

Next Lesson

 

Lesson 7: Linked Lists II

Lesson Requirements
A C compiler.

Instructions on using the LCCWin32 Compiler.

Lesson Summary
We continue from the 6th C Lesson on Linked Lists to create a full example.

Exercise Solution
Let's begin with a solution to the problem that was set in the previous Lesson. This solution will build a linked list containing the numbers 1 to 10 and then print them out. Nothing astounding but it should make things clearer. Firstly, we need a structure with two fields:

struct list_node
{
  // The 2 fields as specified
  int node_id;
  int value;

  // This provides the link
  struct list_node *next;
};

Next, we need a variable for the head (beginning) of the list:

struct list_node *head;

Now we need some functions to create and manipulate the list. Let's define a function AddItem() which will add an item to the list. We'll define AddItem() to take a "struct list_node *" parameter. Ie, it takes a pointer to a structure as it's parameter. We will define this pointer to be a pointer to the structure we want to add the item after. Did that make sense?

NOTE: We add items to the end of the list only in this example.

Here is our AddItem() function:

void AddItem(struct list_node *last_item)
{
  // Declare a pointer to a new node
  struct list_node *new_node;

  // Allocate the memory for the structure
  new_node = (struct list_node *) malloc(sizeof(struct list_node));

  // Add the item to the end of the list
  last_item->next = new_node;

  /* Assign some values to the fields. Note that
     node_count is a global integer that is used
     for the full example code.                  */
  new_node->node_id = node_count;

  new_node->value = 0;
}

At this point we want to create 10 nodes for the example:

// First deal with the base case, setting the head pointer
head = (struct list_node *) malloc(sizeof(struct list_node));
head->node_id = 1;

// Set a temp variable to our current last node
current_node = head;

// Add nine more nodes
for (i = 1; i < 10; i++)
{
  AddItem(current_node);

  // We now have another node after our current node so move   // one down the list
  current_node = current_node->next;

  // Increment our node count by one
  node_count++;
}

// Tidy up and add a NULL pointer to the end of the list
current_node->next = NULL;

Finally, we wish to scan the list and print out the numbers 1 to 10 (the node_id field of the structure).

// Copy the head pointer
temp = head;

while(temp != NULL)
{
  printf("Node number: %d\n", temp->node_id);
  temp = temp->next;
}

Putting it all together, we have: list.c (3k)

 

Back to Tutorials

Next Lesson

 


Copyright 1997, John Crickett & Neil Henderson.
Legal Information