Data structure - linked list
Three, five, seven words
Don't let data structures become the ceiling
concept
Linked list is not only a linear structure, but also a natural recursive structure. Linked list structure can make full use of computer memory space and realize flexible dynamic memory management. However, the linked list loses the advantage of random reading of arrays. At the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of nodes.
purpose
Faster insertion and deletion, because you only need to operate the adjacent elements at the insertion and deletion position. If in a linear table, the position of subsequent elements needs to be adjusted after operating the elements at the middle position. Applications in javascript, such as prototype chain.
Basic properties
- element the value of the current node
- Next next node
Basic method
- insert(item, newitem) inserts a new element newitem after item
To insert an element, you need to point the next of the item element node to the new element, and the next of the new element to the subsequent element of the item element.
- remove(pos) removes an element from the queue head
When deleting a node, you need to point the next of its predecessor node to its successor node.
- find(element) queries the node location with the value of element
- findpre(element) queries the previous node of the node whose value is element
- display() displays the entire linked list
The basic features of linked list implement a LinkedList class
/**
* Basic properties
* element The value of the current node
* next Next node
* Basic method
* insert(item, newitem)Insert a new element after item newitem to insert an element, you need to point the next of the item element node to the new element, and the next of the new element to the subsequent element of the item element.
* remove(pos)Delete an element from the queue head. When deleting a node, you need to point the next of its predecessor node to its successor node.
* find(element)Query the node location with the value of element
* findpre(element)Query the previous node of the node whose value is element
* display()Display the entire linked list
*/
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
class LinkedList {
//Define the element attribute of the header node as' head ', and the next also points to null
constructor() {
this.head = new Node('head')
}
/**
* Add node
* Add a newItem after the item node
*/
insert(item, newItem) {
let itemNode = this.find(item)
let newNode
if (itemNode !== null) {
newNode = new Node(newItem)
newNode.next = itemNode.next
itemNode.next = newNode
}
}
//Delete element
remove(item) {
let preNode = this.findPre(item)
if (preNode !== null) {
preNode.next = preNode.next.next
}
}
//Find the location of the item element
find(item) {
let node = this.head
while (node !== null && node.element !== item) {
node = node.next
}
return node
}
//Is it an empty table
isEmpty() {
return this.head.next === null
}
//Find the previous node of the element
findPre(item) {
let node = this.head
let preNode = null
while (node !== null && node.element !== item) {
preNode = node
node = node.next
}
return preNode
}
//Display linked list
display() {
let result = 'head'
let node = this.head.next
while (node !== null) {
result += '-->' + node.element
node = node.next
}
return result
}
}
module.exports = LinkedList
//Test insertion method
// let link = new LinkedList();
// link.insert('head',1);
// link.insert('head',2);
// link.insert(2,3);
// let fresult = link.display();
// console.log(fresult)
// /// / test the deletion method
// link.remove(2);
// link.remove(3);
// let fresult2 = link.display();
// console.log(fresult2)
Two way linked list
features:
Each instance will record the predecessor node and successor node. The two-way linked list increases the ability of reverse traversal compared with the single linked list. Because the properties of the searched node contain the information of the predecessor and successor nodes, the same search method can be used when inserting and deleting nodes
/**
*Implement a two-way linked list TwoWayLinkedList class.
*/
class Node {
constructor(element) {
this.element = element
this.next = null
this.pre = null
}
}
class TwoWayLinkedList {
constructor() {
this.head = new Node('head')
}
//Is it an empty table
isEmpty() {
return this.head.next === null
}
/**
* Add node
* Add a newItem after the item node
*/
insert(item, newItem) {
let itemNode = this.find(item)
let newNode
if (itemNode !== null) {
newNode = new Node(newItem)
newNode.next = itemNode.next
//Temporarily ignore the processing of tail node null
if (itemNode.next) {
itemNode.next.pre = newNode
}
itemNode.next = newNode
newNode.pre = itemNode
}
}
//Find the location of the item element
find(item) {
let node = this.head
while (node !== null && node.element !== item) {
node = node.next
}
return node
}
//Delete element
remove(item){
let itemNode = this.find(item);
if(itemNode !== null){
itemNode.pre.next = itemNode.next;
itemNode.next.pre = itemNode.pre;
}
}
//Display linked list
display(){
let result ='head';
let node = this.head.next;
while(node !== null){
result += '-->' + node.element;
node = node.next;
}
return result;
}
}
module.exports = TwoWayLinkedList
//Test insertion method
let link = new TwoWayLinkedList();
link.insert('head',1);
link.insert('head',2);
link.insert('head',3);
let fresult = link.display();
console.log(fresult)
//Test deletion method
link.remove(2);
link.remove(3);
let fresult2 = link.display();
console.log(fresult2)
Circular linked list
features:
The characteristic of circular linked list is that the next pointer of the tail node points to the head node
/**
*Take the LinkedList class as the reference benchmark to implement a circular linked list CircularLinkedList class
The characteristic of circular linked list is that the next pointer of the tail node points to the head node
*
*/
//node
class Node{
constructor(element){
this.element = element;
this.next = null;
}
}
//Circular linked list
class CircularLinkedList{
//Define the element attribute of the header node as' head ', and the next also points to null
constructor(){
this.head = new Node('head');
this.head.next = this.head;
this.activeNode = null;
this.count = 0;
}
/**
* Add node
* Add a newItem after the item node
*/
insert(item, newItem){
let itemNode = this.find(item);
let newNode;
newNode = new Node(newItem);
newNode.next = itemNode.next;
itemNode.next = newNode;
this.count++;
}
//Is it an empty table
isEmpty(){
return this.head.next === this.head;
}
//Find the location of the item element
find(item){
let node = this.head;
while(node.element !== item){
node = node.next;
}
return node;
}
//Delete element
remove(item){
let preNode = this.findPre(item);
if(preNode !== null){
preNode.next = preNode.next.next;
this.count--;
}
}
//Find the previous node of the element
findPre(item){
let node = this.head;
let preNode = null;
while(node.element !== item){
preNode = node;
node = node.next;
}
return preNode;
}
//Display linked list
display(){
let result ='head';
let node = this.head.next;
while(node.element !== 'head'){
result += '-->' + node.element;
node = node.next;
}
return result;
}
//Set active node
setActive(item){
let itemNode = this.find(item);
if (itemNode !== null && itemNode !== this.head) {
this.activeNode = itemNode;
} else {
return 'Node does not exist';
}
}
//Test cycle pointing
testCircle(){
let result ='head';
let times = 1;
let node = this.head.next;
while(times < 3){
result += '-->' + node.element;
node = node.next;
if (node.element === 'head') {
times += 1;
}
}
return result;
}
}
module.exports = CircularLinkedList;
//Test insertion method
/*let link = new CircularLinkedList();
link.insert('head',1);
link.insert('head',2);
link.insert('head',3);
//let fresult = link.display();
let fresult = link.testCircle();
console.log(fresult)
//Test deletion method
link.remove(2);
link.remove(3);
//let fresult2 = link.display();
let fresult2 = link.testCircle();
console.log(fresult2)
*/
Algorithm exercise
It is said that during the Jewish War in the 1st century AD, the Jewish historian Flavio Josephus and his 40 compatriots were surrounded by Roman soldiers. The Jewish Soldiers decided to commit suicide rather than be prisoners, so they discussed a suicide plan. They form a circle, start from one person, count to the third person, kill the third person, and then count again until they kill everyone. Joseph and another person decide not to participate in this crazy game. They quickly calculate two positions and stand there to survive. Write a paragraph, surround n people in a circle, and the m person will be killed. Calculate which two people in a circle will survive in the end, and use the circular linked list to solve the problem.
/**
* It is said that during the Jewish War in the 1st century AD, the Jewish historian Flavio Josephus and his 40 compatriots were surrounded by Roman soldiers. The Jewish Soldiers decided to commit suicide rather than be prisoners, so they discussed a suicide plan. They form a circle, start from one person, count to the third person, kill the third person, and then count again until they kill everyone. Joseph and another person decide not to participate in this crazy game. They quickly calculate two positions and stand there to survive. Write a paragraph to surround n people in a circle, and the m-th person will be killed. Calculate which two people in a circle will last in stock, and use the circular linked list to solve the problem
*/
const CircularLinkedList = require('./circularlinkedList');
let link = new CircularLinkedList();
//Load 1-40 numbers
init();
//Start counting
start();
//initialization
function init() {
for(let i = 40;i; i--){
link.insert('head',i);
}
}
function start() {
//Set node 1 as active
link.setActive(1);
let index = 1;
while(link.count > 2){
if(index % 3 === 0){
link.remove(link.activeNode.element);
console.log('Suicide soldier No.:',link.activeNode.element);
console.log('Current queue:',link.display());
}
link.activeNode = link.activeNode.next === link.head ? link.head.next : link.activeNode.next;
index++;
}
}