Record Insertion

The function addNameToLeafRecord() takes a single parameter, empNo. The parameter holds the sequential number of the inserted entry in the empList array. The function is a classic example of creating a link-list record and inserting it at the end of the list:

function addNameToLeafRecord(empNo) {
  var prevNamePtr, nextNamePtr;
  var tmpRecordPtr = new createRecord(empNo);
  var nextNamePtr = currentTrie[1];
  if (!nextNamePtr) {
	currentTrie[1] = tmpRecordPtr;
  }
  else {
    while (nextNamePtr) {
      prevNamePtr = nextNamePtr;
      nextNamePtr = nextNamePtr.next;
    }
    prevNamePtr.next = tmpRecordPtr;
  }
}

We first create a new record:

var tmpRecordPtr = new createRecord(empNo);

The record structure is very simple. It has two fields: the employee index in the empList array, and a pointer to the next record of the list:

function createRecord(empNumber) {
  this.empIndex = empNumber;
  this.next = null;
}

Every trie object is a 10-element array. The elements in indices 2 through 9 point to lower-level trie objects. The element in index 1 points to a link list of all entries belonging to the trie object. "Belonging" here means that the characters of the name can be traced through the data structure to this particular object. Since currentTrie is a global variable holding the current position in the trie data structure, currentTrie[1] is the head of the link list of name records. We remember it in nextNamePtr:

var nextNamePtr = currentTrie[1];

The simplest case is when the link list is empty, i.e. the head of the list is null. In this case, we just link the newly created record at the head of the list:

if (!nextNamePtr) {
  currentTrie[1] = tmpRecordPtr;
}

When the head of the list is not null, we need to trace the link list to its end. We do it by keep advancing nextNamePtr to its next field, until it becomes null:

while (nextNamePtr) {
  prevNamePtr = nextNamePtr;
  nextNamePtr = nextNamePtr.next;
}

The variable prevNamePtr remembers the previous record so we can link to it at the end:

prevNamePtr.next = tmpRecordPtr;

Next: How to prompt the user for a new name