Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

Creating a Linked List

Let’s take a look at how you would create a simple linked list, add a node, delete a node, and search for an item with a given key. Here’s the basic node:

    typedef struct NODE_TYP

       {

       int id;         // id number of this object

       int age;        // age of person

       char name[32];  // name of person

       NODE_TYP *next; // this is the link to the next node

                        // more fields go here

       } NODE, *NODE_PTR;

To start the list off, you need a head pointer and a tail pointer that point to the head and tail of the list, respectively. However, the list is empty, so the pointers start off pointing to `NULL`:

    NODE_PTR     head = NULL,

               tail = NULL;

> Note: Some programmers like to start off a linked list with a dummy node that’s always empty. This is mostly a choice of taste. However, this changes some of the initial conditions of the creation, insertion, and deletion algorithms, so you might want to try it.

Traversing a Linked List

Ironically, traversing a linked list is the easiest of all operations:

  1. Start at the head pointer.
  2. Visit the node.
  3. Link to the next node.
  4. If it’s not `NULL`, repeat step 2.

And here’s the code:

    void Traverse_List(NODE_PTR head)

    {

    // this function traverses the linked list and prints out

    // each node

    // test if head is null

    if (head==NULL)

       {

       printf("\nLinked List is empty!");

       return;

       } // end if

    // traverse while nodes

    while (head!=NULL)

          {

          // visit the node, print it out, or whatever…

          printf("\nNode Data: id=%d", head->id);

          printf("\nage=%d,head->age);

          printf("\nname=%s\n",head->name);

          // advance to next node (simple!)

          head = head->next;

          } // end while

    print("\n");

    } // end Traverse_List

Pretty cool, huh? Next, let’s take a look at how you would add a node.

Adding a Node

The first step in adding a node is creating it. There are two ways to approach this: You could send the new data elements to the insertion function and let it build up a new node, or you could build up a new node and then pass it to the insertion function. Either way is basically the same.

Furthermore, there are a number of ways to insert a node into a linked list. The brute-force method is to add it to the front or the end. This fine if you don’t care about the order, but if you want the list to remain sorted, you should use a more intelligent insertion algorithm that maintains either ascending or descending order—an insertion sort of sorts. This will make searching much faster.

For simplicity’s sake, I’m going to take the easy way out and insert at the end of the list, but inserting with sorting is not that much more complex. You first need to scan the list, find where the new element should be inserted, and insert it. The only problem is keeping track of the pointers and not losing anything.

Anyway, here’s the code to insert a new node at the end of the list (a bit harder than inserting at the front of the list). Notice the special cases for empty lists and lists with a single element:

    // access the global head and tail to make code easier

    // in real life, you might want to use ** pointers and

    // modify head and tail in the function ???

    NODE_PTR Insert_Node(int id, int age, char *name)

    {

    // this function inserts a node at the end of the list

    NODE_PTR new_node = NULL;

    // step 1: create the new node

    new_node = (NODE_PTR)malloc(sizeof(NODE)); // in C++ use  new operator

    // fill in fields

    new_node->id  = id;

    new_node->age = age;

    strcpy(new_node->name,name); // memory must be copied!

    new_node->next = NULL; // good practice

    // step 2: what is the current state of the linked list?

    if (head==NULL) // case 1

       {

       // empty list, simplest case

       head = tail = new_node;

       // return new node

       return(new_node);

       } // end if

    else

    if ((head != NULL) && (head==tail)) // case 2

       {

       // there is exactly one element, just a little

       // finesse…

       head->next = new_node;

       tail = new_node;

       // return new node

       return(new_node);

       } // end if

    else // case 3

       {

       // there are 2 or more elements in list

       // simply move to end of the list and add

       // the new node

       tail->next = new_node;

       tail = new_node;

      // return the new node

      return(new_node);

      } // end else

    } // end Insert_Node

As you can see, the code is rather simple. But it’s easy to mess up because you’re dealing with pointers, so be careful! Also, the astute programmer will very quickly realize that with a little thought, cases two and three can be combined, but the code here is easier to follow. Now let’s remove a node.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.