JS implement double linked list

Before: humble just want to grasp the knowledge points, recorded, but convenient query and review their knowledge points, if there is anything wrong, I hope to be able to point out the mistakes.

There have been two or three months did not write digging blog, the front also wrote a little knowledge about data structure, also very fur, today to share the next linked list in the double linked list, the front also shared very rough single linked list knowledge points, can be quickly viewed.

** double linked list: ** is a kind of linked list, is a kind of pointer before and after, respectively pointing to the precursor node and the successor node, mainly to solve the problem of the previous node, in practical use, when we actually want to use the data of the last node, for the single linked list, is the need to iterate.

The structure of doubly linked lists

Double linked list implementation

This paper will implement several main methods of double linked list, respectively:

  • Append is added to the tail

  • IndexOf returns the position of an element

  • IndexEle returns the element at a location

  • Insert Inserts a position

  • RemoveAt Removes a location

  • RemoveEle removes an element

  • Remove Removes the last element

  • GetSize returns the length of the double-linked list

  • IsEmpty returns whether the doubly linked list isEmpty

  • GetHead returns the head of the double-linked list

  • GetTail returns the end of the double-linked list

  • String Returns a string.

  • GetCurrentAndPrev returns [current element, prev node]

defineNodenode

class Node {
	constructor(element) {
		this.element = element;
		this.next = null;
		this.prev = null; // Add a pre pointer to the list to keep track of the previous node.}}Copy the code

Define double-linked lists

  1. Because we need to recordheadandtailNodes, so we need to add more than a single linked listtailNode to record the last node.
class DoubleLinked {
	constructor() {
		this.head = null;
		this.tail = null;
		this.count = 0; }}Copy the code

appendAdd a tail element

  1. Judgment condition: Ifhead 为null, you need to set the value of the newly added node tohead
  2. ifheadDon’t fornull, you need to traverse to the last elementcurrentThat will benextAssignment, we need to modify itprevPointer tocurrent
  3. Each new addition needs to be addedcount+1
append(element) {
    const node = new Node(element);
    let current = this.head;
    if(! current) {this.head = node;
        this.tail = node;
    } else {
        while (current.next) {
            current = current.next
        }
        current.next = node;
        node.prev = current;
        this.tail = node; // You can also use this.tail.next = node;
    }
    this.count++;
}
Copy the code

insert: Inserts elements to a location

  1. Judge, consider the transgression situation
  2. whenposition = 0You need to determinethis.headPresence or absence of
  3. whenposition > 0 && position < this.countFind the last valuepreNode, point the tail pointer tonode.nodetheprevPoint to thepreNode.nodeThe tail pointer points tonextNode.nextNodetheprevPointer tonode.count+1
  4. whenposition = this.count, can be directly usedappendMethod,tailPoints to the additionnode
  5. position > this.count; returnfalse
Params {* element: the element to be inserted * position: the position to be inserted *} * Judge * 1. * position > 0 && position < this.count Find the last value preNode and point the tail pointer to node. The prev of a node points to a preNode, the tail of a node points to a nextNode, Append * position > this.count; Returns false * /
		
	 insert(element, position) {
		let current = this.head;
		const node = new Node(element);
		let previous = null;
		// position is 0, we need to consider whether head is null
		if(position === 0) {
			// If head is null
			if(! current) {this.head = node // Assign head directly to node
				this.tail = node // Also assign tail to node
			}else {
				node.next = current; // node replaces current with next pointer to current
				current.prev = node;
				this.head = node;
				// We don't use this.tail here because we're just replacing head, tail still refers to the last element;
			}
			this.count++;
		}else if (position > 0 && position <= this.count){
			// Find the element in position
			let index = 0
			while(index < position) {
				previous = current;
				current = current.next;
				index++;
			}
			// If length is the last element, current is null and node is the last element
			if(index ! = =this.count) {
				node.next = current;
				current.prev = node;
			}else {
				this.tail = node;
			}
				previous.next = node
				node.prev = previous;
				this.count++;
		}else {
			return false}}Copy the code

indexOf: Finds the index of the current element

  1. The judgment considers the boundary problem and returns if beyond is not found- 1
  2. Traverse to find, find returnsindexIndex, here is the default to find the first element, the following elements are not considered
// Find the element in the current position
	indexOf(element) {
		// Check current = current. Next
		let index = 0;
		let current = this.head;
		while(current && index < this.count){
			if(current.element === element) {
				return index
			}
			current = current.next;
			index++;

		}
		return -1;
	}
Copy the code

indexEle: Finds the element in the current position

  1. The judgment considers the boundary problem and returns if beyond is not foundfalse, returns the current element if found
indexEle(position) {
    let ele = null;
    if(position >= 0 && position < this.count){
        let current = this.head;
        while(position > 0) {
            current = current.next;
            position--;
        }
        ele = current;
    }
    return ele
}
Copy the code

removeAt: Delete the element

  1. Judge and consider the boundary overflow problem.
  2. whenposition===0 && head, you need to changeheadThe assignment forele.nextAnd at the same time willele.prevSet tonull
  3. whenposition > 0 && head && postion < count - 1When willprevious.next = current.next; current.next.prev = previous
  4. whenposition === count - 1, you only need to changeprevious.next = null; this.tail = previous;
  5. In other cases,! head || position > count-1Both returnfasle
/** * removeAt removes the element ** /
removeAt(position) {
    // Find the element in the current position
    let ele = this.indexEle(position);
    // We have already judged the transgression situation.
    if(ele) {
        // Set the prev pointer to null when poistion === 0 is considered
        if(position === 0) {
            this.head = ele.next;
            ele.prev = null;
        }else {
            // Find the previous pointer element
            let previous = this.indexEle(position - 1);
            // In the same case, next=null should be considered for the boundary case
            if(position === this.count - 1) {
                previous.next = null;
                this.tail = previous;
                // console.log({'tail': this.tail})
            }else {
                previous.next = ele.next;
                ele.next.prev = previous
            }
        }
        // Quantity minus one
        this.count--;
        return true
    }
    return false
}
Copy the code

removeEle: Delete element

  1. Consider element duplication, where all elements that are equal need to be deleted
/** * removeEle removes elements */
		removeEle(element){
			let current = this.head;
			let previous = null;
			let num = 0
			if(current.element === element) {
				// We need to remove the first element, because the next element is from current. Next, so we can't delete the element if the head has ele
				this.head = current.next;
				current.next.prev = null;
				this.count--;
				num++
			}
			previous = current;
			current = current.next;
			
			while(current) {
				if(current.element === element) {
					previous.next = current.next;
					// If it is not a tail pointer, it is necessary to execute a forepointer pointer
					if(current.next){
						current.next.prev = previous; 
					}else {
						this.tail = previous
					}
					this.count--; / / the length - 1
					num++
				}else {
					previous = current;
				}
				current = current.next;
			}
			return num === 0 ? -1 : num;
		}
Copy the code

removeDelete the last element

remove() {
    let current = this.head;
    // Head is null when deleted
    if(this.count === 0) {
        return false
    }else if (this.count === 1) { // Delete only head
        this.head = null;
        this.tail = null;
        this.count--;
        return current.element
    }else {
        // To delete the last one, reassign tail to previous
        let previous = null
        while(current.next) {
            previous = current;
            current = current.next;
        }
        previous.next = null;
        this.tail = previous;
        this.count--;
        returncurrent.element; }}Copy the code

stirng: Converts to a string

string() {
    let str = ' ';
    let current = this.head;
    while (current) {
        str += current.element;
        current = current.next;
    }
    return str;
}
Copy the code

getHead: Gets the head node

getHead() {
    return this.head && this.head.element || null;
}
Copy the code

getTail: Gets the last node

getTail() {
		return this.tail && this.tail.element || null;
	}
Copy the code

getSize: Gets the length

getSize() {
		return this.count;
	}
Copy the code

isEmpty: Checks whether the device is empty

	isEmpty() {
		return this.length === 0;
	}
Copy the code

getCurrentAndPrev: Gets the current element and the last node

getCurrentAndPrev() {
		const arr = [];
		let current = this.head;
		while (current) {
			arr.push([current.element, current.prev])
			current = current.next;
		};
		return arr
	}
Copy the code

The test data

const doubleLinked = new DoubleLinked()
// console.log(doubleLinked.string());


doubleLinked.append(2);
// console.log({'head1': doubleLinked.getHead()})
// console.log({'tail1': doubleLinked.getTail()})
doubleLinked.append(3);
console.log(doubleLinked.remove())
console.log(doubleLinked.remove())
// console.log({'head2': doubleLinked.getHead()})
// console.log({'tail2': doubleLinked.getTail()})

return;
doubleLinked.append(4);
doubleLinked.append('A');
doubleLinked.append('C');
doubleLinked.append('A');
// console.log({'head3': doubleLinked.getHead()})
// console.log({'tail3': doubleLinked.getTail()})
doubleLinked.insert('A'.0)
// console.log(doubleLinked.getSize())

doubleLinked.insert('B'.4)

doubleLinked.insert('C'.3)

console.log(doubleLinked.string());

// doubleLinked.removeAt(5)
// console.log(doubleLinked.indexEle(3))
// console.log(doubleLinked.indexOf('C'))
// console.log(doubleLinked.insert('D', 10)) // false
// console.log({'tail3': doubleLinked.getTail()})
console.log(doubleLinked.removeEle('A'))
console.log({'tail3': doubleLinked.getTail()})
console.log(doubleLinked.getSize())
console.log(doubleLinked.string());
console.log(doubleLinked.getCurrentAndPrev())
Copy the code