Introduction: In daily life, people often use lists. For example, when we sometimes have to go shopping, in order to buy all the things we want to buy before we go, which is the list of the things we need to use. Or when we were in school when we were young, after each exam, the school will list the rankings and transcripts of the top ten students in this exam, etc. These are all lists of the list. We also use lists in our computers, so where is the list suitable for use? Where is it not suitable for use?
Suitable for use: When there are not many elements in the list, you can use the list because the efficiency is very high when searching or sorting the elements in the list. On the contrary, if there are many elements in the list, it is not suitable for use of the list.
1: Abstract data type definition of list
In order to design the abstract data type of a list, we need to give a definition of the list, including what attributes the list should have, what operations should be performed on the list, etc.
A list is an ordered set of data. The data items in each list are called elements. In javascript, the elements in the list can be of any data type. There is no prior agreement on how many elements can be saved in the list. However, the number of elements is limited by the program memory when actually used.
Now we want to design a list, then we can think about implementing a list. What attributes and methods should they contain? Of course, my designs below are designed based on the demos in the book "javascript data structures and algorithms". So we can learn how to design our own abstract classes as a reference when we write programs in the future. The most important thing we learn about demos in the book is to learn their design ideas and how to write code. They have the following attributes;
1. listSize (property): Use a listSize variable to save the number of elements in the list.
2. pos(property): The current position of the list, the index of the element.
3. dataStore(property): Initialize an empty array to save the number of elements. If we want to get the elements in the specific list, we can use the pos attribute above; such as dataStore[pos];
All methods; the following list will be explained, and will not be introduced one by one.
Two: How to implement list classes
Based on the list abstract data type defined above, we can implement the following List class, as follows through the constructor + prototype pattern.
The code copy is as follows:
function List() {
// Number of elements in the list
this.listSize = 0;
// What is the current position of the list
this.pos = 0;
// Initialize an empty array to save list elements
this.dataStore = [];
}
List.prototype = {
// Add an element to the end of the list
append: function(element) {
var self = this;
self.dataStore[this.listSize++] = element;
},
// Remove elements from the list
remove: function(element) {
var self = this;
var curIndex = self.find(element);
if(curIndex > -1) {
self.dataStore.splice(curIndex,1);
--self.listSize;
return true;
}
return false;
},
// Find elements in the list to return the index
find: function(element) {
var self = this;
for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i++) {
if(self.dataStore[i] == element) {
return i;
}
}
return -1;
},
// Return the number of elements in the list
length: function() {
return this.listSize;
},
// Show elements in the list
toString: function(){
return this.dataStore;
},
/*
* Insert an element after the specified element
* @param element Current element
* @param elementAfter Insert the current element behind this element
*/
insert: function(element,elementAfter){
var self = this;
var insertPos = self.find(elementAfter);
if(insertPos > -1) {
self.dataStore.splice(insertPos+1,0,element);
++self.listSize;
return true;
}
return false;
},
// Clear all elements in the list
clear: function() {
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
},
// Determine whether the given element is in the list
contains: function(element) {
var self = this;
for(var i = 0,ilen = self.dataStore.length; i < ilen; i++) {
if(self.dataStore[i] == element) {
return true;
}
}
return false;
},
// Move the current element in the list to the first position
front: function(){
this.pos = 0;
},
// Move the current element in the list to the last position
end: function(){
this.pos = this.listSize - 1;
},
// Move the current position one by one
prev: function(){
if(this.pos > 0) {
--this.pos;
}
},
// Move the current position one by one
next: function(){
if(this.pos < this.listSize - 1) {
++this.pos;
}
},
// Return to the current location of the list
curPos: function(){
return this.pos;
},
// Move the current position to the specified position
moveTo: function(n) {
this.pos = n;
},
// Return the element at the current position
getElement:function(){
return this.dataStore[this.pos];
}
};
As above: Implement a list class, including as many methods as above. Of course, we can also extend some other methods to enrich the implementation of the list class. The most important thing is to learn the encoding method as above.