Detailed explanation of doubly linked lists and doubly circular linked lists in JavaScript

This article mainly introduces the implementation of JavaScript data structures doubly linked lists and doubly circular linked lists. It has certain reference value. Interested friends can refer to

The difference between doubly linked lists and ordinary linked lists. The reason is that in a linked list, a node only has a link to the next node, while in a doubly linked list, the links are bidirectional: one link goes to the next element, and the other link goes to the previous element.

Doubly linked lists provide two methods of iterating the list: from beginning to end, or vice versa. We can also access the next or previous element of a specific node. In a one-way linked list, if you miss the element you are looking for while iterating the list, you need to return to the starting point of the list and start iterating again. This is an advantage of doubly linked lists.

Doubly linked list: A one-way linked list can only traverse linked list nodes in one direction, but a doubly linked list with a forward pointer added to the node pointer field can traverse nodes in both directions. This allows a doubly linked list to traverse the entire linked list at any node.

function DoublyLinkedList() { 
  var Node = function(element) { 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = Node(element), 
      current, 
      previous; 
     
    if(!head){ 
      head = node; 
      tail = node; 
    }else{ 
      current = head; 
      while(current){ 
        previous = current; 
        current = current.next; 
      } 
 
      node.next = current; 
      current.prev = node; 
      previous.next = node; 
      node.prev = previous; 
    } 
 
    length++; 
    return true; 
  } 
 
  this.insert = function(position,element){ 
    if(position > -1 && position < length){ 
      var node = new Node(element), 
        current = head, 
        previous, 
        index = 0; 
 
      if(position === 0){ 
 
        if(!head){ 
          head = node; 
          tail = node; 
        }else{ 
          node.next = current; 
          current.prev = node; 
          head = node; 
        } 
 
      }else if (position === length -1){ 
        current = tail; 
        current.next = node; 
        node.prev = current; 
      }else { 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
        node.next = current; 
        previous.next = node; 
        current.prev = node; 
        node.prev = previous; 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
      var current = head, 
        index = 0, 
        previous; 
 
      if (position === 0) { 
        head = current.next; 
 
        if(length === 1){ 
          tail = null; 
        }else{ 
          head.prev = null; 
        } 
      }else if(position === length - 1){ 
        current = tail; 
        tail = current.prev; 
        tail.next = null; 
      } else{ 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
      }; 
      length-- ; 
 
      return current.element; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous; 
 
    if(current.element === element){ 
      head = current.next; 
    } 
    previous = current; 
    current = current.next; 
 
    while(current){ 
      if (current.element = element) { 
        previous.next = current.next; 
        current.next.prev = previous; 
      }else{ 
        previous = current; 
        current = current.next; 
      } 
    } 
    return false; 
  }; 
 
  this.remove = function(){ 
    if (length === 0) { 
      return false; 
    }; 
 
    var current = head, 
      previous; 
 
    if(length === 1){ 
      head = null; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(current){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = null; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if (current.element === element) { 
        return index; 
      }; 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      string = &#39;&#39;; 
 
    while(current){ 
      string += current.element; 
      current = current.next; 
    } 
    return string; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
}

Two-way circular linked list: Connect the head and tail pointers of the two-way linked list to form a two-way circular linked list. This kind of linked list can traverse nodes in two directions at the same time from any node, and the speed of querying nodes is also the fastest.

/*双向循环链表*/ 
function DoublyCircularLinkedList(){ 
  var Node = function(element){ 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = new Node(element), 
      current, 
      previous; 
 
    if (!head) { 
      head = node; 
      tail = node; 
      head.prev = tail; 
      tail.next = head; 
    }else{ 
      current = head; 
 
      while(current.next !== head){ 
        previous = current; 
        current = current.next; 
      } 
 
      current.next = node; 
      node.next = head; 
      node.prev = current; 
    }; 
 
    length++; 
    return true; 
  }; 
 
  this.insert = function(position, element){ 
    if(position >= 0 && position <= length){ 
      var node = new Node(element), 
        index = 0, 
        current = head, 
          previous; 
 
      if(position === 0){ 
         
        if(!head){ 
 
          node.next = node; 
          node.tail = node; 
          head = node; 
          tail = node; 
 
        }else{ 
 
          current.prev = node; 
          node.next = current; 
          head = node; 
          node.prev = tail; 
 
        } 
         
      }else if(position === length){ 
        current = tail; 
 
        current.next = node; 
        node.prev = current; 
        tail = node; 
        node.next = head; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        current.prev = node; 
        node.next = current; 
        previous.next = node; 
        node.prev = previous; 
 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
 
      var current = head, 
        index = 0, 
        previous; 
 
      if(position === 0){ 
 
        current.next.previous = tail; 
        head = current.next; 
 
      }else if(position === length - 1){ 
 
        current = tail; 
 
        current.prev.next = head; 
        head.prev = current.prev; 
        tail = current.prev; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
 
      } 
 
      length--; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous, 
      indexCheck = 0; 
 
    while(current && indexCheck < length){ 
      if(current.element === element){ 
        if(indexCheck === 0){ 
          current.next.prev = tail; 
          head = current.next; 
        }else{ 
          current.next.prev = previous; 
          previous.next = current.next; 
        } 
        length--; 
        return true; 
      } 
 
      previous = current; 
      current = current.next; 
      indexCheck++; 
    } 
 
    return false; 
  }; 
 
  this.remove = function(){ 
    if(length === 0){ 
      return false; 
    } 
 
    var current = head, 
      previous, 
      indexCheck = 0; 
 
    if(length === 1){ 
      head = null; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(indexCheck++ < length){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = head; 
    tail = previous.next; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if(current.element === element){ 
        return index; 
      } 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      indexCheck = 0, 
      string = &#39;&#39;; 
 
    while(current && indexCheck < length){ 
      string += current.element; 
      indexCheck++; 
      current = current.next; 
    }   
 
    return string; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
}

The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.

Related articles:

How to implement in Jstree that the disabled child nodes will also be selected when the parent node is selected

In vue. How to integrate the carousel chart in mint-ui in js

How to implement collection data traversal display in AngularJS

The above is the detailed content of Detailed explanation of doubly linked lists and doubly circular linked lists in JavaScript. For more information, please follow other related articles on the PHP Chinese website!