Javascript List

Lists are one of the most common organizing tools people use in their day-to-day lives. We have to-do lists, grocery lists, top-ten lists, bottom-ten lists, and many other types. Our computer programs can also use lists, particularly if we only have a few items to store in list form. Lists are especially useful if we don’t have to perform searches on the items in the list or put them into some type of sorted order. When we need to perform long searches or complex sorts, lists become less useful, especially with more complex data structures.

This article presents the creation of a simple list class. We start with the definition of a list abstract data type (ADT) andthen demonstrate how to implement the ADT. We wrap up the article  with some problems that are best solved with lists

A List ADT

In order to design an ADT for a list, we have to provide a definition of the list, including its properties, as well as the operations performed on it and by it.

A list is an ordered sequence of data. Each data item stored in a list is called an element. In JavaScript, the elements of a list can be of any data type. There is no predetermined number of elements that can be stored in a list, though the practical limit will be the amount of memory available to the program using the list.

A list with no elements is an empty list. The number of elements stored in a list is called the length of the list.Internally, the number of elements in a list is kept in a listSize variable. You can append an element to the end of a list, or you can insert an element into a list after an existing element or at the beginning of a list. Elements are deleted from a list using a remove operation. You can also clear a list so that all of its current elements are removed.

The elements of a list are displayed using either a toString() operation, which displays all the elements, or with a getElement() operation, which displays the value of the current element.

Lists have properties to describe location. There is the front of a list and the end of a list. You can move from one element of a list to the next element using the next() operation, and you can move backward through a list using the prev()operation. You can also move to a numbered position in a list using the moveTo(n) operation, where n specifies the position to move to. The currPos property indicates the current position in a list.

The List ADT does not specify a storage function for a list, but for our implementation will use an array named dataStore.

listSize(property)

Number of elements in list

pos (property)

Current position in list

length(property)

Returns the number of elements in list

clear (function)

Clears all elements from list

toString(function)

Returns string representation of list

getElement(function)

Returns element at current position

insert(function)

Inserts new element after existing element

append(function)

Adds new element to end of list

remove(function)

Removes element from list

front (function)

Sets current position to first element of list

end (function)

Sets current position to last element of list

prev (function)

Moves current position back one element

next (function)

Moves current position forward one element

currPos(function)

Returns the current position in list

moveTo(function)

Moves the current position to specified position

A List Class Implementation

A List class implementation can be taken straight from the List ADT we just defined. We’ll start with a definition of a constructor function, though it is not part of the ADT:

function List() {
   this.listSize = 0;
   this.pos = 0;
   this.dataStore = []; // initializes an empty array to store list elements
   this.clear = clear;
   this.find = find;
   this.toString = toString;
   this.insert = insert;
   this.append = append;
   this.remove = remove;
   this.front = front;
   this.end = end;
   this.prev = prev;
   this.next = next;
   this.length = length;
   this.currPos = currPos;
   this.moveTo = moveTo;
   this.getElement = getElement;
   this.length = length;
   this.contains = contains;
}

Append: Adding an Element to a List

The first function we’ll implement is the append() function.This function appends a new element onto the list at the next available position, which will be equal to the value of the listSize variable:

function append(element) {
   this.dataStore[this.listSize++] = element;
}

After the element is appended, listSize is incremented by 1.

Remove: Removing an Element from a List

Next, let’s see how to remove an element from a list. remove() is one of the harder functions to implement in the List class. First, we have to find the element in the list, and then we have to remove it and adjust the space in the underlying array to fill the hole left by removing an element. However, we can simplify the process by using the splice() mutator function. To start, let’s define a helper function, find(), for finding the element to remove:

function find(element) {
   for (var i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
         return i;
      }
   }
   return -1;
}

Find: Finding an Element in a List

The find function simply iterates through dataStorelooking for the specified element. If the element is found, the function returns the position where the element was found. If the element wasn’t found, the function returns -1, which is a standard value to return when an element can’t be found in an array. We can use this value for error checking in the remove() function.

The remove() function uses the position returned by find() to splice the dataStore array at that place. After the array is modified, listSize is decremented by 1 to reflect the new size of the list. The function returns true if an element is removed, and false otherwise. Here is the code:

function remove(element) {
   var foundAt = this.find(element);
   if (foundAt > -1) {
      this.dataStore.splice(foundAt,1);
      --this.listSize;
      return true;
   }
   return false;
}

Length: Determining the Number of Elements in a List

The length() function returns the number of elements in a list:

function length() {
   return this.listSize;
}

toString: Retrieving a List’s Elements

Now is a good time to create a function that allows us to view the elements of a list. Here is the code for a simple toString() function:

function toString() {
    return this.dataStore;
}

Strictly speaking, this function returns an array object and not a string, but its utility is in providing a view of the current state of an object, and just returning the array works adequately for this purpose.

Let’s take a break from implementing our List class to see how well it works so far. Here is a short test program that exercises the functions we’ve created so far:

var names = new List();
names.append('Cynthia');
names.append('Raymond');
names.append('Barbara');
print(names.toString());
names.remove('Raymond');
print(names.toString());

The output from this program is:

Cynthia,Raymond,Barbara
Cynthia,Barbara

Insert: Inserting an Element into a List

The next function to discuss is insert(). What if, after removing Raymond from the preceding list, we decide we need to put him back where he was to begin with? An insertion function needs to know where to insert an element, so for now we will say that insertion occurs after a specified element already in the list. With this in mind, here is the definition of the insert() function:

function insert(element, after) {
   var insertPos = this.find(after);
   if (insertPos > -1) {
      this.dataStore.splice(insertPos+1, 0, element);
      ++this.listSize;
      return true;
   }
   return false;
}

insert() uses the helper function find() to determine the correct insertion position for the new element by finding the element specified in the after argument. Once this position is found, we use shift() to insert the new element into the list. Then we increment listSize by 1 and return true to indicate the insertion was successful.

Clear: Removing All Elements from a List

Next, we need a function to clear out the elements of a list and allow new elements to be entered:

function clear() {
   delete this.dataStore;
   this.dataStore = [];
   this.listSize = this.pos = 0;
}

The clear() function uses the delete operator to delete the dataStore array, and the next line re-creates the empty array. The last line sets the values of listSize and pos to 0 to indicate the start of a new list.

Contains: Determining if a Given Value Is in a List

The contains() function is useful when you want to check a list to see if a particular value is part of the list. Here is the definition:

function contains(element) {
   for (var i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
         return true;
      }
   }
   return false;
}

Traversing a List

This final set of functions allows movement through a list, and the last function, getElement(), displays the current element in a list:

function front() {
   this.pos = 0;
}

function end() {
   this.pos = this.listSize-1;
}

function prev() {
   if (this.pos > 0) {
      --this.pos;
   }
}

function next() {
   if (this.pos < this.listSize-1) {
      ++this.pos;
   }
}

function currPos() {
   return this.pos;
}

function moveTo(position) {
   this.pos = position;
}

function getElement() {
   return this.dataStore[this.pos];
}

Let’s create a new list of names to demonstrate how these functions work:

var names = new List();
names.append('Clayton');
names.append('Raymond');
names.append('Cynthia');
names.append('Jennifer');
names.append('Bryan');
names.append('Danny');

Now let’s move to the first element of the list and display it:

names.front();
print(names.getElement()); // displays Clayton

Next, we move forward one element and display the element’s value:

names.next();
print(names.getElement());  // displays Raymond

Now we’ll move forward twice and backward once, displaying the current element to demonstrate how the prev() function works:

names.next();
names.next();
names.prev();
print(names.getElement()); // displays Cynthia

The behavior we’ve demonstrated in these past few code fragments is captured in the concept of an iterator. We explore iterators in the next section.

Iterating Through a List

An iterator allows us to traverse a list without referencing the internal storage mechanism of the List class. The functions front(), end(), prev(), next(), and currPos provide an implementation of an iterator for our List class. Some advantages to using iterators over using array indexing include:

• Not having to worry about the underlying data storage structure when accessing list elements
• Being able to update the list and not having to update the iterator, where an index becomes invalid when a new element is added to the list
• Providing a uniform means of accessing elements for different types of data stores used in the implemenation of a List class

With these advantages in mind, here is how to use an iterator to traverse through a list:

for(names.front(); names.currPos() < names.length(); names.next()) {
   print(names.getElement());
}

The for loop starts by setting the current position to the front of the list. The loop continues while the value of currPos is less than the length of the list. Each time through the loop, the current position is moved one element forward throu

The loop starts at the last element of the list and moves backward using the prev() function while the current position is greater than or equal to 0.

Iterators are used only to move through a list and should not be combined with any functions for adding or removing items from a list.

gh the use of the next() function.

We can also traverse a list backward using an iterator. Here is the code:

for(names.end(); names.currPos() >= 0; names.prev()) {
   print(names.getElement());
}

The loop starts at the last element of the list and moves backward using the prev() function while the current position is greater than or equal to 0.

Iterators are used only to move through a list and should not be combined with any functions for adding or removing items from a list.