Операции с двусвязным списком

Реализация операций с помощью JavaScript

В двусвязном списке можно перемещаться вперед и назад при обходе списка.

Если вам интересно узнать об основах связанного списка, посетите мой блог.

Вот изображение того, как выглядит двусвязный список:

Создание класса узла

// By creating this node class, you avoid repeating the same steps
    //You just have call this class when you want to create or add a node

class Node {
  constructor(value){
    this.value = value
    this.next = null
    this.previous = null 
  }
}

Создание нового связанного списка

class DoublyLinkedList {
  constructor(value) {

    // create new Node using the Node class
    // point the head and tail to the new Node
    // keep track of the length 

    const newNode = new Node(value)
    this.head = newNode
    this.tail = this.head
    this.length = 1
  }
}

Добавление узла в конец списка

//PROCESS
  //takes in 1 argument: the value of the new Node

  //use the Node Class to create a new Node

  //if list is empty:
    //point the head and tail to the New Node
  //else:
    //have the current last Node point to the New Node
    //connect the new Node back to what had been the last Node in the list
    //set the tail to equal the new Node

  //increase length by 1
  //return the entire linked list
  
  push(value){

    const newNode = new Node(value)

    if(!this.head){
      this.head = newNode
      this.tail = newNode
    }else {
      this.tail.next = newNode
      newNode.previous = this.tail
      this.tail = newNode
    }

    this.length++
    return this
  }

Удаление узла в конце списка

//PROCESS:
  //if list is empty:
    //return undefined

  //create variable and set it equal to the tail

  //if list only has 1 item
    //set the head and tails equal to null

  //else
    //change the tail to point to the second to last Node
      //this will set it as the new last Node
  
    //remove the connection between the new last Node and the old last Node
       //set the tail.next to equal null
       //set the oldlastNode.previous equal null
   
  //reduce length by 1
  //return the Node that has been removed
  
  pop() {
    if(this.length === 0) return undefined
    
    let temp = this.tail
    
    if(this.length === 1){
      this.head = null
      this.tail = null
    }else {  
      this.tail = this.tail.previous
      this.tail.next = null
      temp.previous = null
    }
    this.length--
    return temp
  }
 

Добавление узла в начало списка

 //PROCESS:
   //takes in 1 argument: the value of the new Node
  
  //create new node using the Node class

  //if list is empty
    //set the head and tail equal to the new Node
  //else
    // set the new Node to point to the first Node in list
    //set the first Node to point back to the new Node
    //set the new Node as the first Node in list

  //increase length by 1
  //return entire list 

  
  unshift(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.head = newNode
      this.tail = newNode
    }else {
      newNode.next = this.head
      this.head.previous = newNode
      this.head = newNode
    }
    this.length++
    return this
  }

Удаление первого узла из списка

//PROCESS:
  //if list is empty:
    //return undefined

  //create variable and set it equal to the head      
      //this will be used to point to the node that you want to delete
  
  //if list has one item
    //set the head and tail equal to null
  //else 
    //set the head equal to the 2nd Node in list
    //set the new first Node to point back to null
    //set the previous first Node to point to null

  //reduce length by 1
  //return the deleted Node

  shift() {
    if(this.length === 0) return undefined

    let temp = this.head
    
    if(this.length === 1){
      this.head = null
      this.tail = null
    } else {
      this.head = this.head.next
      this.head.previous = null
      temp.next = null
    }
    this.length--
    return temp
  }

Получение узла из определенного индекса

//PROCESS:
  //takes in 1 argument: the specific index

  //if index is outside range
    //return undefined

  //create a new variable and set it equal to head

  //if the index is less than half of the length of list
    //traverse list from the head
 //else
   //traverse list from the tail

//return the Node for the specific index

  get(index){
    if(index < 0 || index >= this.length){
      return undefined
    }

    let temp = this.head

    if(index < this.length / 2){
      for(let i = 0; i < index; i++){
        temp = temp.next
      }
    } else {
      temp = this.tail
      
      for(let i = this.length - 1; i > index ; i--){
      temp = temp.previous
      }
    }
    return temp
  }

Изменение значения определенного индекса

//PROCESS:
  //takes in 2 arguments: 
    //the specific index, and the new value of that Node

  //use the GET method to find the specific Node
    //instead of typing the code again
  
   //if Node exists in the list:
    //set its value equal to the new value
    //return true
  //else
    //return false

  set(index, value){
    let temp = this.get(index)

    if(temp){
      temp.value = value
      return true
    }
    return false
  }

Вставка нового узла в определенный индекс

 //PROCESS:
  //takes two arguments: specific index and new value

  //if index === 0
    //use the UNSHIFT method

  //if index === length of list
    //use the PUSH method

  //if index is outside range
    //return undefined

  //else
    //create new Node using the Node Class
    //create two variables
      //one is used to point to the previous Node in list
     //use the GET METHOD to find this Node
      //the other is  used to point to the next Node in list

    // change the previous Node to point to the new Node
    //set the new Node to point back to the previous Node 
    //set the new Node to point to the next Node
    //change the next Node to point back to the new Node
  
    //increase length by 1
    //return true
  
  insert(index, value){
    if(index === 0) return this.unshift(value)

    if(index === this.length) return this.push(value)

    if(index < 0 || index >= this.length){
      return undefined 
    }

    const newNode = new Node(value)
    const before = this.get(index - 1)
    const after = before.next

    before.next = newNode
    newNode.previous = before
    newNode.next = after
    after.previous = newNode

    this.length++
    return true
  }

Удаление узла по определенному индексу

 //PROCESS:
 //takes in 1 argument: the specified index

  //if specified index === 0:
    //use the SHIFT method

  //if specified index is the last Node in list:
    //use the POP method

  //if specified index outside the range of list
    //return undefined

  //else
    //find the specific Node using the GET method
  
    //connect the previous Node to the Node that's after the specified Node
    //remove the specified node from list
  
    //reduce length by 1
    //return the deleted node
    
  remove(index){
    if(index === 0) return this.shift()
    if(index === this.length -1) return this.pop()

    if(index < 0 || index >= this.length){
      return undefined
    }

  const temp = this.get(index)

  temp.previous.next = temp.next 
  temp.next.previous = temp.previous
  temp.next = null
  temp.previous = null

  this.length--
  return temp
  }

Вот как это выглядит вместе:

//USED TO CREATE NEW NODE
class Node {
  constructor(value) {
    this.value = value
    this.next = null
    this.previous = null
  }
}

class DoublyLinkedList {
  //USED TO CREATE NEW LIST
  constructor(value) {
    const newNode = new Node(value)
    this.head = newNode
    this.tail = this.head
    this.length = 1
  }


  //ADDING NEW NODE TO END OF LIST
  push(value){
    const newNode = new Node(value)

    if(!this.head){
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      newNode.previous = this.tail
      this.tail = newNode
    }
    this.length++
    return this
  }


  //REMOVING NODE FROM THE END OF LIST
  pop() {
    if(this.length === 0) return undefined
    
    let temp = this.tail
    
    if(this.length === 1){
      this.head = null
      this.tail = null
    } else {  
      this.tail = this.tail.previous
      this.tail.next = null
      temp.previous = null
    }
    this.length--
    return temp
  }

  
  //ADDING NODE AT THE BEGINNING OF LIST
  unshift(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.head = newNode
      this.tail = newNode
    }else {
      newNode.next = this.head
      this.head.previous = newNode
      this.head = newNode
    }
    this.length++
    return this
  }

  //DELETING FIRST NODE FROM LIST
  shift() {
    if(this.length === 0) return undefined

    let temp = this.head
    
    if(this.length === 1){
      this.head = null
      this.tail = null
    } else {
      this.head = this.head.next
      this.head.previous = null
      temp.next = null
    }
    this.length--
    return temp
  }
  
  //GETTING NODE FROM A PARTICULAR INDEX
  get(index){
    if(index < 0 || index >= this.length){
      return undefined
    }

    let temp = this.head

    if(index < this.length / 2){
      for(let i = 0; i < index; i++){
        temp = temp.next
      }
    }else {
      temp = this.tail
      
      for(let i = this.length - 1; i > index ; i--){
      temp = temp.previous
      }
    }
    return temp
  }

  //CHANGING VALUE AT A PARTICULAR INDEX
  set(index, value){
    let temp = this.get(index)

    if(temp){
      temp.value = value
      return true
    }
    return false
  }

  //INSERTING NEW NODE AT A PARTICULAR INDEX
  insert(index, value){
    if(index === 0) return this.unshift(value)

    if(index === this.length) return this.push(value)

    if(index < 0 || index >= this.length){
      return undefined 
    }

    const newNode = new Node(value)
    const before = this.get(index - 1)
    const after = before.next

    before.next = newNode
    newNode.previous = before
    newNode.next = after
    after.previous = newNode

    this.length++
    return true
  }
  
  //REMOVING NODE AT A PARTICULAR INDEX
  remove(index){
    if(index === 0) return this.shift()
    if(index === this.length -1) return this.pop()

    if(index < 0 || index >= this.length){
      return undefined
    }

  const temp = this.get(index)

  temp.previous.next = temp.next 
  temp.next.previous = temp.previous
  temp.next = null
  temp.previous = null

  this.length--
  return temp
  }
  
}

// creates new instance of the linked list
const newDoublyList = new DoublyLinkedList(1)

// adds new Node to the 'newDoublyList' instance
newDoublyList.push(2)

Цитирование