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.
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 dataStore
looking 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.