双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素
与单向链表相比，双向链表有新增两点

  • 节点新增 prev 指针

  • 链表增加 tail 标记（类比head）

    实现一个双向链表

    1. function DoublyLinkedList() {
    3.   let Node = function(element){
    4.       this.element = element;
    5.       this.next = null;
    6.       this.prev = null; //NEW
    7.   };
    9.   let length = 0;
    10.   let head = null;
    11.   let tail = null; //NEW
    13.   this.append = function(element){
    15.       let node = new Node(element),
    16.           current;
    18.       if (head === null){ //first node on list
    19.           head = node;
    20.           tail = node; //NEW
    21.       } else {
    23.           //attach to the tail node //NEW
    24.           tail.next = node;
    25.           node.prev = tail;
    26.           tail = node;
    27.       }
    29.       length++; //update size of list
    30.   };
    32.   this.insert = function(position, element){
    34.       //check for out-of-bounds values
    35.       if (position >= 0 && position <= length){
    37.           let node = new Node(element),
    38.               current = head,
    39.               previous,
    40.               index = 0;
    42.           if (position === 0){ //add on first position
    44.               if (!head){       //NEW
    45.                   head = node;
    46.                   tail = node;
    47.               } else {
    48.                   node.next = current;
    49.                   current.prev = node; //NEW {1}
    50.                   head = node;
    51.               }
    53.           } else  if (position === length) { //last item //NEW
    55.               current = tail;     // {2}
    56.               current.next = node;
    57.               node.prev = current;
    58.               tail = node;
    60.           } else {
    61.               while (index++ < position){ //{3}
    62.                   previous = current;
    63.                   current = current.next;
    64.               }
    65.               node.next = current;
    66.               previous.next = node;
    68.               current.prev = node; //NEW
    69.               node.prev = previous; //NEW
    70.           }
    72.           length++; //update size of list
    74.           return true;
    76.       } else {
    77.           return false;
    78.       }
    79.   };
    81.   this.removeAt = function(position){
    83.       //check for out-of-bounds values
    84.       if (position > -1 && position < length){
    86.           let current = head,
    87.               previous,
    88.               index = 0;
    90.           //removing first item
    91.           if (position === 0){
    93.               head = current.next; // {1}
    95.               //if there is only one item, then we update tail as well //NEW
    96.               if (length === 1){ // {2}
    97.                   tail = null;
    98.               } else {
    99.                   head.prev = null; // {3}
    100.               }
    102.           } else if (position === length-1){ //last item //NEW
    104.               current = tail; // {4}
    105.               tail = current.prev;
    106.               tail.next = null;
    108.           } else {
    110.               while (index++ < position){ // {5}
    112.                   previous = current;
    113.                   current = current.next;
    114.               }
    116.               //link previous with current's next - skip it to remove
    117.               previous.next = current.next; // {6}
    118.               current.next.prev = previous; //NEW
    119.           }
    121.           length--;
    123.           return current.element;
    125.       } else {
    126.           return null;
    127.       }
    128.   };
    130.   this.remove = function(element){
    132.       let index = this.indexOf(element);
    133.       return this.removeAt(index);
    134.   };
    136.   this.indexOf = function(element){
    138.       let current = head,
    139.           index = -1;
    141.       //check first item
    142.       if (element == current.element){
    143.           return 0;
    144.       }
    146.       index++;
    148.       //check in the middle of the list
    149.       while(current.next){
    151.           if (element == current.element){
    152.               return index;
    153.           }
    155.           current = current.next;
    156.           index++;
    157.       }
    159.       //check last item
    160.       if (element == current.element){
    161.           return index;
    162.       }
    164.       return -1;
    165.   };
    167.   this.isEmpty = function() {
    168.       return length === 0;
    169.   };
    171.   this. size = function() {
    172.       return length;
    173.   };
    175.   this.toString = function(){
    177.       let current = head,
    178.           s = current ? current.element : '';
    180.       while(current && current.next){
    181.           current = current.next;
    182.           s += ', ' + current.element;
    183.       }
    185.       return s;
    186.   };
    188.   this.inverseToString = function() {
    190.       let current = tail,
    191.           s = current ? current.element : '';
    193.       while(current && current.prev){
    194.           current = current.prev;
    195.           s += ', ' + current.element;
    196.       }
    198.       return s;
    199.   };
    201.   this.print = function(){
    202.       console.log(this.toString());
    203.   };
    205.   this.printInverse = function(){
    206.       console.log(this.inverseToString());
    207.   };
    209.   this.getHead = function(){
    210.       return head;
    211.   };
    213.   this.getTail = function(){
    214.       return tail;
    215.   }
    216. }