list
When you don't need to find or sort elements in a long sequence.
Abstract data type definition of list
A list is an ordered set of data. (whether the data itself is in order or the index is in order)
Each data item in the list is called an element. Any data type can be in the list. The number of elements in the list is limited by the program memory.
A list that does not contain any elements is called an empty list.
attribute
length: number of list elements
listSize: the number of elements in the saved list
method
append(): you can add an element to the end of the list, or insert an element after a given element or at the beginning of the list
remove(): removes an element from the list.
clear(): clear all elements in the list.
toString(): displays all elements in the list.
getElement(): displays the current element.
The list has attributes that describe the location of the element. After the list has money.
next(): you can move from the current element to the next element.
prev(): you can move to the previous element of the current element.
moveTo(): move to the specified location
currPos(): current position in the list
end(): moves the current element to the last position
front(): move the current element to the first position
Implementation of list
function List() {
this.dataStore = [];
this.listSize = 0;
this.pos = 0;
this.length = this.dataStore.length;
}
List.prototype.append = function (element) {
this.dataStore[this.listSize++] = element;
}
List.prototype.remove = function (element) {
let result = this.dataStore.findIndex((ele)=>{
return ele === element;
});
this.dataStore.splice(result, 1);
this.listSize--;
return 1;
}
List.prototype.find = function (element) {
return this.dataStore.indexOf(element);
}
List.prototype.length = function () {
return this.listSize;
}
List.prototype.toString = function () {
return this.dataStore.toString();
}
// Insert an element after an element
List.prototype.insert = function (element, after) {
let index = this.dataStore.findIndex((ele)=>{
return ele === after
});
if(index > -1) {
this.dataStore.splice(index + 1, 0 ,element);
this.listSize++;
return true;
}
return false;
}
List.prototype.clear = function () {
delete this.dataStore;
this.dataStore.length = 0;
this.listSize = 0;
this.pos = 0;
}
List.prototype.contains = function (element) {
return this.dataStore.includes(element);
}
List.prototype.front = function () {
this.pos = 0;
}
List.prototype.end = function () {
this.pos = this.listSize-1;
}
List.prototype.getElement = function () {
return this.dataStore[this.pos];
}
List.prototype.prev = function () {
if(this.pos > 0){
this.pos--;
}
}
List.prototype.next = function () {
if(this.pos < this.listSize-1){
this.pos++;
}
}
// Return to current position
List.prototype.currPos = function () {
return this.pos;
}
// Move to the specified location
List.prototype.moveTo = function (index) {
this.pos = index;
}
Traversing the list using iterators
Advantages of using iterators
- Don't care about the underlying data storage structure
- When inserting data into a list, only the list is updated, and the iterator does not need to be updated
- Iterators provide a unified way to access lists
// Traverse from front to back
for(list.front(); list.curPos() < list.length(); list.next()){
console.log(list.getElement())
}
// Traverse from back to front
for(list.end(); list.curPos() >= 0; list.prev()){
console.log(list.getElement());
}
Stack
Operation on stack
Stack is a special kind of list. The stack can only be at one end of the list, which is called the top of the stack. Data in the stack comes in first and then out.
attribute
Top: position of stack top
length: records the number of elements in the stack
method
push(): push into stack
pop(): pop up stack
peak(): returns the top element of the stack
clear(): clear all elements
Implementation of stack
function Stack() {
this.stack = [];
this.top = 0;
this.length = 0;
}
Stack.prototype.push = function (element) {
this.stack[this.top] = element;
this.top++;
}
Stack.prototype.pop = function () {
this.stack.splice(this.top - 1, 1);
this.top--;
}
Stack.prototype.clear = function () {
this.top = 0;
}
Stack.prototype.peak = function () {
return this.stack[this.top - 1];
}
Stack.prototype.length = function () {
return this.top;
}
queue
A queue is a list. Pairs can only be inserted at the end of the queue and deleted at the head of the queue. Queues are used to store sequential data, first in, first out.
Operations on queues
The operation of inserting is called queuing, and the operation of deleting is called pairing.
method
peak(): read the element of the head of the queue
clear(): clear the queue
enquenen(): join the team
dequenen(): out of line
empty(): judge whether the queue is empty
front(): read the first element of the queue
end(): reads the last element of the queue
Implementation of queue
function Quenen() {
this.dataStore = [];
}
// Join the team
Quenen.prototype.enquenen = function (element) {
this.dataStore.push(element);
}
// Out of the team
Quenen.prototype.dequenen = function () {
this.dataStore.shift();
}
// Clear queue
Quenen.prototype.clear = function () {
this.dataStore = [];
}
Quenen.prototype.toString = function () {
return this.dataStore.toString();
}
// Judge whether it is an empty pair of columns
Quenen.prototype.empty = function () {
if(this.dataStore.length === 0){
return true;
} else {
return false;
}
}
// Returns the element at the head of the queue
Quenen.prototype.front = function () {
return this.dataStore[0];
}
// Returns the element at the end of the queue
Quenen.prototype.end = function () {
return this.dataStore[this.dataStore.length - 1];
}
Linked list
Disadvantages of arrays
- The length of the array is fixed, and it will be difficult to add when the array is filled
- Adding and deleting elements is troublesome. You need to move elements forward or backward
- Very slow
Define linked list
A linked list is a set of nodes. Each node uses a reference to an object to point to its successor, and a reference to another node is called a chain.
Array elements are referenced by their position, and linked lists are referenced by their relationship. The tail element of the linked list points to a null.
There is a head node at the front of the linked list.
Add element: the precursor of the current node points to the new node, and the new node points to the node to which the original precursor points.
Delete element: the precursor of the deleted element points to the node pointed by the deleted node, and the deleted node points to null.
operation
method
insert(): insert after a node
remove(): deletes a node according to its contents
findNode(): find a node according to its contents
Implementation of linked list
function Node(element) {
this.next = null;
this.element = element;
}
function LinkedList() {
this.head = new Node('head');
}
LinkedList.prototype.findNode = function (element) {
let head = this.head;
while(head){
if(head.element === element){
return head.next;
}
head = head.next;
}
return head;
}
LinkedList.prototype.findPrevNode = function (element) {
let head = this.head;
let currentNode = this.findNode(element);
while(head.next){
if(head.next.element === currentNode.element){
return head;
}
}
return null;
}
// Insert after node
LinkedList.prototype.insert = function (element, afterElement) {
let node = new Node(element);
// Find the node first
let currentNode = this.findNode(afterElement);
if(currentNode){
if(currentNode.next){
node.next = currentNode.next;
currentNode.next = ndoe;
} else {
currentNode.next = node;
node.next = null;
}
}
}
LinkedList.prototype.remove = function (element) {
let currentNode = this.findNode(element);
let prevNode = this.findPrevNode(element);
if(prevNode){
prevNode.next = currentNode.next;
currentNode.next = null;
}
}
Bidirectional linked list
function Node(element) {
this.element = element;
this.previous = null;
this.next = null;
}
function LLinkedList(){
this.head = new Node('head');
this.next = null;
this.previous = null;
}
LLinkedList.prototype.findNode = function (element) {
let head = this.head;
while(head){
if(head.element === element){
return head;
}
head = head.next;
}
return head;
}
LLinkedList.prototype.insert = function (element, afterElement) {
let node = new Node(element);
let currentNode = this.findNode(afterElement);
if(currentNode){
if(currentNode.next){
node.previous = currentNode;
node.next = node.previous.next;
node.next.previous = node;
node.previous.next = node;
} else {
node.next = null;
node.previous = currentNode;
currentNode.next = node;
}
}
}
LLinkedList.prototype.remove = function (element) {
let currentNode = this.findNode(element);
currentNode.previous.next = currentNode.next;
currentNode.next.previous = currentNode.previous;
currentNode.next = null;
currentNode.previous = null;
}
Circular linked list
function Node(element) {
this.element = element;
this.next = null;
}
function CycleLinkedList() {
this.head = new Node('head');
this.head.next = this.head;
}
CycleLinkedList.prototype.findNode = function (element) {
let head = this.head;
while(head){
if(head.element === element){
return head;
}
head = head.next;
}
return head;
}
CycleLinkedList.prototype.insert = function (element, afterElement) {
let node = new Node(element);
let currentNode = this.findNode(afterElement);
if(currentNode){
if(currentNode.next){
node.next = currentNode.next;
currentNode.next = node;
} else {
currentNode.next = node;
node.next = null;
}
}
}
Dictionaries
A dictionary is a data structure that stores data in the form of key value pairs. The dictionary class is based on the Array class, not the Object class.
Implementation of dictionary
function Dictionary() {
this.dataStore = new Array();
}
Dictionary.prototype.add = function (key,value) {
this.dataStore[key] = value;
}
Dictionary.prototype.find = function (key) {
return this.dataStore[key];
}
Dictionary.prototype.remove = function (key) {
delete this.dataStore[key];
}
Dictionary.prototype.showAll = function () {
for(let key in Object.keys(this.dataStore).sort()){
console.log(key + '->' + this.dataStore[key]);
}
}
Dictionary.prototype.count = function () {
let n = 0;
for(let key in Object.keys(this.dataStore)){
++n;
}
return n;
}
hash
The hashed data can be accessed quickly. The data structure used for hashing is a hash table. Insertion, deletion and retrieval are fast, but search is slow.
When storing data through a hash table, the key is mapped to a number through the hash function, which ranges from 0 to the length of the hash table.
When two keys are mapped to a value, it is called collision.
The array length of hash table should be a prime number.
Select hash function
The choice of hash function depends on the data type of the key value. Division and remainder method. If the key type is a string, divide the sum of the ASCII values of each character by the remainder of the length of the array.
Collision handling
Open chain method
In the underlying array that implements the hash table, each element is another data structure
Linear detection method
In case of collision, detect whether the next position of the hash table is empty. If it is empty, store the data in the position. If it is not empty, continue to detect the next position until an empty position is found. When the array of stored data is very large, the linear detection method is better than the open chain method.
If the size of the array is 1.5 times the number of data to be stored, the open chain method is used; If the size of the array is twice or more than the number of data to be stored, linear detection method is used.
aggregate
A collection is a data structure that contains different elements. Elements in a collection are called members. The members in the collection are out of order. The same elements are not allowed in the collection.
A set is composed of a group of disordered but related members. Each member can only appear once in the set.
Definition of set
- A set that does not contain any members is called an empty set, and a complete set is a set that contains all possible members.
- If two sets have exactly the same members, they are said to be equal.
- If all elements in one set are contained in another set, the former set is a subset of the latter set.
Operations on collections
- Union: merge the members of two sets to form a set
- Intersection: the common members in two sets form a new set
- Complementary set: a set of members belonging to one set but not to another
method
- add: adds a member to the collection
- remove: removes a member from the collection
- show: displays the members in the collection
Implementation of set class
function Set(){
this.dataStore = [];
this.size = 0;
}
// Tool function
Set.prototype.indexOf = function (element) {
return this.dataStore.indexOf(element);
}
Set.prototype.add = function (element) {
if(this.indexOf(element) !== -1){
return false;
} else {
this.dataStore.push(element);
}
}
Set.prototype.remove = function (element) {
let index = this.indexOf(element);
if(index !== -1){
this.dataStore.splice(index, 1);
} else {
return false;
}
}
Set.prototype.show = function () {
return this.dataStore.toString();
}
// intersection
Set.prototype.union = function (set) {
let unionSet = new Set();
let tempStore = set.dataStore;
for(let i = 0; i < this.dataStore.length; i++){
unionSet.dataStore.concat(set.dataStore.filter((ele) => {
return ele === this.dataStore[i];
}));
}
return unionSet;
}
// Union
Set.prototype.interset = function (set) {
let intersetSet = new Set();
let tempStore = set.dataStore;
for(let i = 0; i < this.dataStore.length; i++){
tempStore = tempStore.filter((ele) => {
return ele !== this.dataStore[i];
});
}
intersetSet.dataStore = intersetSet.dataStore.concat(this.dataStore, tempStore);
return intersetSet;
}
// Complement
Set.prototype.diference = function (set){
let difSet = new Set();
for(let i = 0; i < this.dataStore.length; i++){
if(set.dataStore.every((ele) => {
return ele !== this.dataStore[i];
})){
difSet.dataStore.push(this.dataStore[i]);
}
}
return difSet;
}
tree
Tree is a nonlinear retrieval data structure, which stores data in a hierarchical manner. Trees are used to store hierarchical data. Trees are also used to store sequence tables.
Definition of tree
A tree consists of nodes connected by edges. The top node of a tree becomes the root node. If a node connects multiple nodes, it is called the parent node, and the nodes below it become the child nodes. A node can have 0, 1 or more child nodes. Nodes without any child nodes become leaf nodes.
The number of child nodes of the node of the binary tree shall not exceed two. A set of edges from one node to another is called a path. Accessing all nodes in a particular order is called traversal of the tree. The tree can be divided into several levels. The root node is level 0. Any level node in the tree can be regarded as the root of the subtree. The number of layers of a tree is the depth of the tree. Each node has a value associated with it, usually a key.
The two nodes of a parent node become the left node and the right node respectively. In some binary tree implementations, the left node contains a specific set of values and the right node contains a specific set of values.
Binary lookup tree is a special binary tree. Its smaller value is placed in the left node and the larger value is saved in the right node.
Traversal of binary search tree
Middle order traversal
Access the nodes on the tree in ascending order according to the key values of the nodes.
Preorder traversal
First visit the root node, and then traverse the left and right subtrees in the same way.
Postorder traversal
First visit the leaf node, from the left subtree to the right subtree, and then to the root node.
Delete node
To delete a node, first judge whether the current node contains the data to be deleted. If so, delete the node; If not, compare the data of the current node with the data of the node to be deleted. If the data on the current node is less than the data of the node to be deleted, move to the left node of the current node to continue the comparison; If the data on the current node is larger than the data of the node to be deleted, move to the right node of the current node to continue the comparison.
If the deleted node is a leaf node, the link from the parent node to it points to null.
If the deleted node contains only one child node, the original link to it points to its child nodes.
If the deleted node contains two nodes, either find the maximum value of the left subtree of the node to be deleted or the minimum value of the right subtree of the node to be deleted.
chart
Definition of graph
A graph consists of a set of edges and a set of vertices. If the fixed-point pairs of a graph are ordered, it is called a directed graph. After sorting the vertex pairs of a directed graph, you can draw an arrow between the two vertices. A directed graph shows the flow direction of vertices.
If a graph is unordered, it is called an unordered graph or an undirected graph. A series of vertices in the graph form a path, and the vertices in the path are connected by edges. The length of the path is expressed by the number of edges from the first vertex to the last vertex.
A path consisting of vertices pointing to itself is called a ring, and the length of the ring is 0.
A circle is a path with at least one edge, and the first vertex of the path is the same as the last vertex. A circle without repeated vertices and edges is a simple circle. In addition to the first and last vertices, a circle with other repeated vertices in the path is called a trivial circle.
If there is path connectivity between two vertices, the two vertices are called strong connectivity.
If the vertices of a directed graph are strongly connected, then the graph is also strongly connected.
Modeling real systems with graphs
Represents an edge
We call the method of representing the edges of a graph adjacency table or adjacency table array. The edges are represented as an array of adjacent vertex lists with vertices, and the vertices are used as indexes.
Adjacency matrix is a two-dimensional array in which the elements indicate whether there is an edge between two vertices.
Use an array with the same length as the number of vertices to record the vertices, and create a sub array for each element to record the number of adjacent vertices.
function Map(v) {
this.vertices = v;// Total number of nodes
this.edges = 0;
this.adj = [];
this.edgeTo = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++){
this.adj[i] = [];
this.adj[i].push('');
}
for(let i = 0; i < this.vertices; i++){
this.marked[i] = false;
}
}
Map.prototype.addEdge = function (v,w){
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
Map.prototype.show = function () {
for(let i = 0; i < this.vertices; i++){
for(let j = 0; j < this.vertices; j++){
if(this.adj[i][j] !== undefined){
console.log(this.adj[i][j])
}
}
}
}
Map.prototype.pathTo = function (v) {
var source = 0;
if (!this.hasPathTo(v)) {
return undefined;
}
var path = [];
for (var i = v; i != source; i = this.edgeTo[i]) {
path.push(i);
}
path.push(s);
return path;
}
Map.prototype.hasPathTo = function (v) {
return this.marked[v];
}
Search graph
Those vertices can be reached from a specified vertex.
Depth first search
Start tracing from the starting vertex until the last vertex is reached, then trace back, start tracing the next path until the last vertex is reached, and so on until there is no path.
Map.prototype.dfs = function (v) {
this.marked[v] = true;
if(this.adj[v] !== undefined){
for(let key in this.adj[v]){
if(!this.marked[key]){
this.dfs[key];
}
}
}
}
Breadth first search
Starting with the first vertex, try to access the vertex as close to it as possible. First check the layer closest to the first vertex and gradually move down to the layer furthest from the first node.
Breadth search uses an abstract queue instead of an array to sort visited vertices.
Map.prototype.bfs = function (s) {
let quenen = [];
this.marked[s] = true;
quenen.push(s);
while(quenen.length > 0){
let v = quenen.shift();
if(v === undefined){
console.log(v+'undefined');
}
for(let i in this.adj[v]){
if(!this.marked[i]){
this.edgeTo[i] = v;
this.marked[i] = true;
quenen.push(i);
}
}
}
}
principle
Find unreachable vertices adjacent to the current vertex and add them to the accessed vertex list and queue.
Take the next vertex from the graph and add it to the accessed list vertex.
Add all unreachable vertices adjacent to V to the queue.
Find shortest path
Breadth first search shortest path
// bfs function
function bfs(s) {
var queue = [];
this.marked[s] = true;
queue.push(s); //Add to end of queue
while (queue.length > 0) {
var v = queue.shift(); //Remove from team leader
if (v == undefined) {
print("Visisted vertex: " + v);
}
for each(var w in this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
Topological sorting
Topological sorting sorts all vertices of a directed graph so that the directed edge points from the front vertex to the back vertex.