The definition of a List

A list is an ordered set of data. The data items in each list are called elements. In JavaScript, the elements in a list can be of any data type. There is no limit to how many elements can be stored in the list, and the actual number of elements used is limited by program memory.

A list that contains no elements is called an empty list. The number of elements in a list is called the length of the list. In the internal implementation, a variable called listSize is used to hold the number of elements in the list. You can append an element at the end of the list, or you can insert an element after a given element or at the beginning of the list. Remove elements from the list using the remove method and clear all elements from the list using the clear method.

You can also use the toString() method to display all the elements in the list and the getElement() method to display the current element. Lists have attributes that describe the location of elements. The list has front and end (front and end, respectively). Use the next() method to move from one element to the next, and the prev() method to move to the previous element of the current element. You can also use the moveTo(n) method to move directly to a specified position, where n means to moveTo the NTH position. The currPos attribute represents the current position in the list.

Abstract data type definition for a list

Implementing a list class

Based on the List abstract data type defined above, you can directly implement a List class. Let’s start by defining the constructor, although it is not itself part of the list abstract data type definition:

class List {
    constructor() {
        this.dataSource = [];
        this.listSize = 0;
        this.pos = 0;
    }
    clear() {}
    find() {}
    toString() {}
    insert() {}
    append() {}
    remove() {}
    front() {}
    end() {}
    prev() {}
    next() {}
    length() {}
    currPos() {}
    moveTo() {}
    getElement() {}
    contains(){}}Copy the code

Append: Adds an element to the list

append(element) {
    this.dataStore[this.listSize++] = element;
}
Copy the code

When the new element is in place, the variable listSize is increased by 1.

Find: Searches for an element in a list

The find() method iterates through the array object dataStore to find the given element. If found, the element’s position in the list is returned, otherwise -1 is returned, which is the standard value returned when the specified element is not found in the array. We can use this value for error checking in the remove() method.

find(element) {
    for (let i = 0, len = this.dataStore.length; i < len; ++i) {
        if (this.dataStore[i] == element) {
            returni; }}return -1;
}
Copy the code

Remove: Remove elements from the list

The remove() method is one of the more difficult methods in the List class to implement. First, you need to find the element in the list, then delete it, and adjust the underlying array object to fill in the space left by the deletion. The good news is that you can simplify this process by using the splice() method for arrays.

remove(element) {
    const index = this.find(element);
    if (index === -1) {
        return false
    }
    this.dataStore.splice(index, 1);
    --this.listSize;
    return true;
}
Copy the code

Length: How many elements are in the list

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

length() {
    return this.listSize;
}
Copy the code

ToString: Displays the elements in the list

Now it’s time to create a method that displays the elements in the list.

toString() {
    return this.dataStore.toString();
}
Copy the code

Insert: Inserts an element into the list

The next method to discuss is insert(). What if you deleted an element in the middle of the List, but now you want to put it back? The insert() method needs to know where to insert the element, so for now let’s assume that insert means after an element in the list.

insert(element, index) {
    const index = this.find(element);
    if (index === -1) {
        return false;
    }
    this.dataStore.splice(index + 1.0, element);
    ++this.listSize;
    return true;
}
Copy the code

Clear: Clear all elements in the list

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

Contains: Determines whether the given value is in the list

The contains() method becomes useful when you need to determine whether a given value is in a list.

contains(element) {
    for (let i = 0, len = this.dataStore.length; i < len; ++i) {
        if (this.dataStore[i] == element) {
            return true; }}return false;
}
Copy the code

You can also use the previously implemented find method

Traverse the list

The last set of methods allows the user to move freely across the list

front() {
    this.pos = 0;
}
end() {
    this.pos = this.listSize - 1;
}
prev() {
    if (this.pos > 0{-this.pos; }}next() {
    if (this.pos < this.listSize - 1) {
        ++this.pos; }}currPos() {
    return this.pos;
}
moveTo(position) {
    this.pos = position;
}
getElement() {
    return this.dataStore[this.pos];
}
Copy the code

Use iterators to access lists

Iterators allow you to traverse lists without worrying about how the data is stored internally. The aforementioned methods front(), end(), prev(), next(), and currPos implement an iterator for the List class. Here are some of the advantages of using iterators as opposed to indexing arrays.

You don’t have to worry about the underlying data store structure when accessing list elements.

When you add an element to the list, the index is not the right value, and only the list is updated, not the iterator.

The List class can be implemented in different types of data stores, and iterators provide a uniform way to access the elements in the List. With these advantages in mind, let’s look at an example of iterating through a list:

for(lists.front(); lists.currPos() < lists.length(); lists.next()) { 
    console.log(lists.getElement());
} 
Copy the code

At the beginning of the for loop, set the current position of the list to the first element. As long as the value of currPos is less than the length of the list, the loop continues, each time calling the next() method to move the current position forward by one bit.

Similarly, you can iterate through the list from back to front, as follows:

for(lists.end(); lists.currPos() >= 0; lists.prev()) { 
    console.log(lists.getElement()); 
} 
Copy the code

The loop starts at the last element of the list, and calls the prev() method to move back one bit when the current position is greater than or equal to zero.

Iterators should only be used to move around the list and should not be used with any method that adds or removes elements from the list.

Complete List implementation code

class List {
    constructor() {
        this.dataStore = [];
        this.listSize = 0;
        this.pos = 0;
    }
    clear() {
        delete this.dataStore;
        this.dataStore = [];
        this.listSize = this.pos = 0;
    }
    find(element) {
        for (let i = 0, len = this.dataStore.length; i < len; ++i) {
            if (this.dataStore[i] == element) {
                returni; }}return -1;
    }
    toString() {
        return this.dataStore.toString();
    }
    insert(element, index) {
        const index = this.find(element);
        if (index === -1) {
            return false;
        }
        this.dataStore.splice(index + 1.0, element);
        ++this.listSize;
        return true;
    }
    append(element) {
        this.dataStore[this.listSize++] = element;
    }
    remove(element) {
        const index = this.find(element);
        if (index === -1) {
            return false;
        }
        this.dataStore.splice(index, 1);
        --this.listSize;
        return true;
    }
    length() {
        return this.listSize;
    }
    contains(element) {
        for (let i = 0, len = this.dataStore.length; i < len; ++i) {
            if (this.dataStore[i] == element) {
                return true; }}return false;
    }
    front() {
        this.pos = 0;
    }
    end() {
        this.pos = this.listSize - 1;
    }
    prev() {
        if (this.pos > 0{-this.pos; }}next() {
        if (this.pos < this.listSize - 1) {
            ++this.pos; }}currPos() {
        return this.pos;
    }
    moveTo(position) {
        this.pos = position;
    }
    getElement() {
        return this.dataStore[this.pos]; }}Copy the code

The resources

• Data structures and algorithms described in JavaScript