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

Linked List Node Design

Now we will discuss the design of the node that can be used in your linked list implementations. The data placed inside a node is dependent upon the application of the list. For instance, let's say that you would like to use a linked list to keep track of the enemy ships that are currently alive and flying around in your space shooter. There are several ways to represent enemy ships with your nodes, but for the sake of simplicity, we will let each node hold the x and y coordinate of the ship on the screen.

In this example, we will create a struct to package the data.

typedef struct node
{
  int x, y;           // x and y coordinate
  struct node *next;  // pointer ("link") to the next node
} node_t;

There we have our basic node structure with the type defined as node_t. Note that you specify struct node *next; because it is a pointer to an incomplete type. The following code demonstrates how we can use this type to declare our variables.

node_t  nodeRec;            // a single node
node_t  *head;              // head node of a linked list
typedef node_t  *node_ptr;  // create a node pointer type
node_ptr  head;             // head node of a linked list

The first declaration, node_t nodeRec, declares a variable of the node structure. You can't really use this for your linked lists.

The second declaration, node_t *head, is what we're looking for. This declares a node pointer that we will use for the head of the linked list.

The third and fourth declarations are fairly self-explanatory. They create a new pointer type that allows for better code readability, and then declare the head of the linked list using this new pointer type.

Also keep in mind that the second and fourth lines are equivalent.

In Figure 1.2, you can see the visual representation of a single node. We will use this representation throughout the series for all the nodes in all the data structures we explore. The node has a data area, where all the node's information is stored, as well as a link area, where the links to other nodes are defined.

When designing nodes, keep in mind that nodes have a data portion and a link portion. You can put any type of data that you want in the data portion, including pointers, structs, classes, or the more common ordinal types. However, for the link portion of the node, you must only create variables that will be used as links to other nodes. Here in the basic design of the linked list node, we created a single link that links to the next node in the list. In future articles, we will expand on this idea and add more links for more complex data structures.

In the meantime however, we need to discuss some of the basic operations that you can perform on linked lists.

Next : Node Allocation & Initialization