Data structure - linked list

Data structure - linked list

Three, five, seven words

Don't let data structures become the ceiling

Relevant code address

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++;
    }
}

Tags: data structure linked list

Posted by Tentious on Fri, 06 May 2022 20:26:15 +0300