Tutorial: Linked Lists in ROBOTC

I really love data structures.  That sounded a lot less geeky in my head, but it’s true.  It was my favourite subject when studying computer science and I have a few good books on the subject.  I don’t pretend to understand the math behind most of them.  In any case, when ROBOTC implemented pointers, I started working on a little implementation of a linked list in ROBOTC.  Please note that some of the images are based on the ones found in the original WikiPedia article on linked lists.

Please note that this is the second instalment of a multi-part tutorial on how you can use pointers in ROBOTC.  I will also be covering things like queues, binary trees and other fun stuff.  You can read about pointers in this tutorial: [LINK].  If you want to know more about stacks, you should check out part 2: [LINK]

What makes up a list

What is a linked list, you say?  Consider the image below.

Each list element contains a number and a reference (or pointer) to the next node in the list, a bit like a chain of nodes.  If you were looking at the node with “99” in it, and you wanted to know which one’s the next in line, you’d simply follow the pointer to the next node.  The last pointer in the list is nothing, or NULL.  This signifies the end.  Of the list, of course, not the world.

In ROBOTC, you could represent such a list node with a struct like this:

struct tListNode 
{ 
  tListNode *next;   // neighbouring node 
  ubyte value;       // value held by node 
} tListNode;

You need something to keep track of all the node, so in order to do that, we create a List struct:

struct tList 
{ 
  tListNode *head;   // pointer to the node at the head of the list 
  tListNode *tail;   // pointer to the node at the top of the list 
  int size;          // current size of the list 
} tList;

So why the head and tail?  That just makes things easier; it’s always nice to be able to quickly get to the first and last node of a list.  The node array is necessary because we cannot allocate things dynamically, so we pre-allocate a fixed array of nodes and use them as a pool. An array of booleans is used to keep track of which ones are allocated.  You’ll see how I use those in a little bit.

Inserting a new node

A list is no good if you can’t add anything to it, this is called insertion.  So how do you add a new node?  Consider the drawing below:

On the left you can see a node with a neighbour (node.next) and a new node.  If we want to insert it between these two, we simply point the node’s “next” pointer to the new node and make the new  node’s “next” pointer point to the node that was previously known as node.next.  Now the list has a new node added to.  It’s not all that complicated, as you can see.  In code it’s a bit more complex, because we also need to deal with special cases, like:

• Inserting a new node at the beginning of the list (and whether or not that’s the first one)
• Adding a node at the end of the list

void insertNode(tList *list, tListNode *node, tListNode *newNode) 
{ 
  // Is the list empty? 
  if (list->size == 0) 
  { 
    list->head = newNode; 
    list->tail = newNode; 
    list->size++; 
  } 
  // node == NULL, so put the newNode at the start 
  // of the list 
  else if (node == NULL) 
  { 
    newNode->next = list->head; 
    list->head = newNode; 
    list->size++; 
  } 
  // Insert the newNode into the list, after the node 
  else 
  { 
    newNode->next = node->next; 
    node->next = newNode; 
    // if the node was the tail, update this pointer to the newNode 
    if (list->tail == node) 
      list->tail = newNode; 
    list->size++; 
  } 
}

Deleting a node

Deleting a node is pretty simple operation.  Just point the previous node’s next pointer to the next node of the one you wish to delete.

We have a few special cases, though:

• Deleting the last node (the tail)
• Deleting the first node (the head)
• Deleting the last node

When you translate that to code, it looks like this:

void deleteNode(tList *list, tListNode *obsoleteNode) 
{ 
  tListNode *nodePtr;

  // We only have one node! 
  if (list->size == 1) 
  { 
    list->head = NULL; 
    list->tail = NULL; 
    list->size--; 
    FREE(obsoleteNode); 
  } 
  // The node we want to delete is the head of the list 
  else if (list->head == obsoleteNode) 
  { 
    list->head = obsoleteNode->next; 
    list->size--; 
    FREE(obsoleteNode); 
  } 
  else 
  { 
    // we need to start looking for the obsoleteNode's 
    // left neighbour 
    nodePtr = list->head; 
    while (nodePtr != NULL) 
    { 
      // The nodePtr's neighbour is the node we're looking for 
      if (nodePtr->next == obsoleteNode) 
      { 
        // Check if it is also the tail 
        if(obsoleteNode == list->tail) 
        { 
          list->tail = nodePtr; 
        } 
        // Update the node's left neighbour 
        nodePtr->next = obsoleteNode->next; 
        list->size--; 
        FREE(obsoleteNode); 
        return; 
      } 
      // advance to the next node 
      nodePtr = nodePtr->next; 
    } 
  } 
}

Sorting the list

Using pointer magic, you can have all sorts of fun with your list.  If you want to sort your list from small to large, you can easily do this with a bubble sort.  Details about how that works can be read in a previous tutorial: [LINK].  To make it work, we’ll need a way to swap nodes.  Consider the list below.  If we wish to swap the nodes  “99” and “37”, we’ll have to do some serious pointer swapping:

There are some special cases again, of course:

• Swapping two nodes in a list with just those two nodes
• Swapping two nodes, with one of them being the tail
• Swapping two nodes with one of them being the head

In code, it looks like this:

void swapNodes(tList *list, tListNode *nodeA, tListNode *nodeB)
{
  writeDebugStream("swapping nodes %p (%d)", nodeA, nodeA->value);
  writeDebugStreamLine("and %p (%d)", nodeB, nodeB->value);
  tListNode *nodePtr;

  // If the list is less than two nodes big, there's not much point
  if (list->size < 2)
    return;
  // If the list if exactly two nodes big, just swap 'em around
  else if (list->size == 2)
  {
    nodeB->next = nodeA;
    nodeA->next = NULL;
    list->head = nodeB;
    list->tail = nodeA;
    return;
  }

  // If the first node is the list's head,
  // swap 'em and update the list's head pointer.
  if (list->head == nodeA)
  {
    writeDebugStreamLine("nodeA is head");
    nodeA->next = nodeB->next;
    nodeB->next = nodeA;
    list->head = nodeB;
    return;
  }
  // The first node is a node somewhere in the list
  else
  {
    // We'll have to iterate through to find the
    // node, whose next pointer points to our
    // first node.
    // Start at the head and go through until we reach the end
    nodePtr = list->head;
    while(nodePtr != NULL)
    {
      writeDebugStreamLine("nodePtr: %p (%d)", nodePtr, nodePtr->value);
      // We've found the node, start swapping
      if (nodePtr->next == nodeA)
      {
        writeDebugStreamLine("nodePtr->next == nodeA");
        nodePtr->next = nodeB;
        nodeA->next = nodeB->next;
        nodeB->next = nodeA;
        // If the second node was the tail, update the tail pointer
        if (list->tail == nodeB)
        {
          writeDebugStreamLine("nodeB is tail");
          list->tail = nodeA;
        }
        return;
      }
      // go to the next node
      nodePtr = nodePtr->next;
    }
  }
}

The actual sorting function now looks like this:

void sortList(tList *list) 
{ 
  writeDebugStreamLine("sortList"); 
  tListNode *nodePtr; 
  // Don't bother to sort a list smaller than 2 nodes big 
  if (list->size == 1) 
  { 
    return; 
  }

  // This is a bubble sort, for details on how this works, check out 
  // http://botbench.com/blog/2012/07/21/tutorial-sorting-your-data/ 
  for(int i = 0; i < list->size; i++) 
  { 
    // Iterate through the list, start at the head 
    nodePtr = list->head; 
    while(nodePtr != list->tail) 
    { 
      // The next node is bigger than the current one, 
      // so swap them around 
      if (nodePtr->value > nodePtr->next->value) 
      { 
        swapNodes(list, nodePtr, nodePtr->next); 
      } 
      // Update the nodePtr 
      else if (nodePtr->next != NULL) 
      { 
        nodePtr = nodePtr->next; 
      } 
    } 
  } 
}

Using a resource pool of nodes

As I mentioned earlier, ROBOTC does not have dynamically allocated memory, so no new() or free().  To simulate something like it, you can use an array of list nodes and keep track of their allocated status in another array of booleans.

tListNode _listNodePool[MAX_LIST_SIZE]; // array of nodes 
bool _allocStatus[MAX_LIST_SIZE];       // Array to keep track of allocation 
                                        // status of nodes. 
                                        // true == node is allocated

When a node becomes used, the status gets updated, when it becomes available again, the contents are cleared and the status is set to free.

tListNode * NEW() 
{ 
  for (int i = 0; i < MAX_LIST_SIZE; i++) 
  { 
    // Return the node if it is not already allocated 
    if (!_allocStatus[i]) 
    { 
      writeDebugStreamLine("NEW: found node[%d]: %p", i, _listNodePool[i]); 
      _allocStatus[i] = true; 
      return _listNodePool[i]; 
    } 
  } 
  // No free nodes available 
  writeDebugStreamLine("NEW: no free nodes left"); 
  return NULL; 
}

void FREE(tListNode *node) 
{ 
  for (int i = 0; i < MAX_LIST_SIZE; i++) 
  { 
    if (_allocStatus[i]) 
    { 
      if (node == _listNodePool[i]) 
      { 
        writeDebugStreamLine("FREE: deleting node[%d]: %p", i, _listNodePool[i]); 
        _allocStatus[i] = false; 
        memset(node, 0, sizeof(tListNode)); 
        return; 
      } 
    } 
  } 
  writeDebugStreamLine("FREE: could not find node: %p", node); 
}

You can find the complete source code here: [LINK].