单向链表

  1. class Node {
  2.     constructor(element) {
  3.         this.element = element;
  4.         this.next = null;
  5.     }
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.         this.size = 0;
  11.         this.head = null;
  12.     }
  14.     /**
  15.      * @method 尾部追加数据
  16.      * @param {any} element 追加数据
  17.      */
  18.     append(element) {
  19.         let node = new Node(element);
  20.         if (this.head === null) {
  21.             this.head = node;
  22.         } else {
  23.             let current = this.getNode(this.size - 1);
  24.             current.next = node;
  25.         }
  26.         this.size++;
  27.     }
  29.     /**
  30.      * @method 指定位置追加数据
  31.      * @param {Number} position 位置
  32.      * @param {any} element 追加数据
  33.      */
  34.     appendAt(position, element) {
  35.         if (position < 0 || position > this.size) {
  36.             throw new Error("position out range");
  37.         }
  38.         let node = new Node(element);
  39.         if (position === 0) {
  40.             node.next = this.head;
  41.             this.head = node;
  42.         } else {
  43.             let pre = this.getNode(position - 1);
  44.             node.next = pre.next;
  45.             pre.next = node;
  46.         }
  47.         this.size++;
  48.     }
  50.     /**
  51.      * @method 删除指定位置数据
  52.      * @param {Number} position 位置
  53.      */
  54.     removeAt(position) {
  55.         if (position < 0 || position >= this.size) {
  56.             throw new Error("position out range");
  57.         }
  58.         let current = this.head;
  59.         if (position === 0) {
  60.             this.head = current.next;
  61.         } else {
  62.             let pre = this.getNode(position - 1);
  63.             current = pre.next;
  64.             pre.next = current.next;
  65.         }
  66.         this.size--;
  67.     }
  69.     /**
  70.      * @method 修改指定位置数据
  71.      * @param {Number} position 位置
  72.      * @param {any} element 追加数据
  73.      */
  74.     update(position, element) {
  75.         if (position < 0 || position >= this.size) {
  76.             throw new Error("position out range");
  77.         }
  78.         let pre = this.getNode(position);
  79.         pre.element = element;
  80.     }
  82.     /**
  83.      * @method 查找指定位置数据
  84.      * @param {Number} position 位置
  85.      * @return {any} 返回数据
  86.      */
  87.     getData(position) {
  88.         if (position < 0 || position >= this.size) {
  89.             throw new Error("position out range");
  90.         }
  91.         let pre = this.getNode(position);
  92.         return pre.element;
  93.     }
  95.     /**
  96.      * @method 查找指定数据索引
  97.      * @param {any} element
  98.      * @return {Number} 索引
  99.      */
  100.     indexOf(element) {
  101.         let current = this.head;
  102.         // let i = 0;
  103.         // while (current) {
  104.         //     if (current.element === element) return i;
  105.         //     current = current.next;
  106.         //     i++;
  107.         // }
  108.         for (let i = 0; i < this.size; i++) {
  109.             if (current.element === element) {
  110.                 return i;
  111.             }
  112.             current = current.next;
  113.         }
  114.         return -1;
  115.     }
  117.     /**
  118.      * @method 返回链表长度
  119.      * @return {Number} 链表长度
  120.      */
  121.     get length() {
  122.         return this.size;
  123.     }
  125.     getNode(index) {
  126.         if (index < 0 || index >= this.size) {
  127.             throw new Error("out range");
  128.         }
  129.         let current = this.head;
  130.         // let i = 0;
  131.         // while (i++ < index) {
  132.         //     current = current.next;
  133.         // }
  134.         for (let i = 0; i < index; i++) {
  135.             current = current.next;
  136.         }
  137.         return current;
  138.     }
  139. }
  141. let ll = new LinkedList();
  142. ll.append(1);
  143. ll.append(2);
  144. // ll.append(3);
  145. // ll.append(4);
  147. ll.appendAt(2, 3);
  148. ll.appendAt(3, 4);
  149. // ll.appendAt(3, 2);
  151. // ll.removeAt(0);
  152. // ll.removeAt(1);
  154. console.log(ll.getData(3));
  156. // console.log(ll.indexOf(1));
  157. // console.log(ll.indexOf(2));
  158. // console.log(ll.indexOf(3));
  159. // console.log(ll.indexOf(4));
  160. // console.log(ll.indexOf(5));
  162. console.dir(ll, {
  163.     depth: 100,
  164. });
  165. console.log(ll.length);
  167. // setTimeout(() => {
  168. //     ll.update(3, 9);
  169. //     console.dir(ll, {
  170. //         depth: 100,
  171. //     });
  172. // }, 1000);

双向链表

  1. class DoublyNode {
  2.     constructor(element) {
  3.         this.element = element;
  4.         this.prev = null;
  5.         this.next = null;
  6.     }
  7. }
  9. class DoublyLinkedList {
  10.     constructor() {
  11.         this.size = 0;
  12.         this.head = null;
  13.         this.tail = null;
  14.     }
  16.     /**
  17.      * @method 尾部追加数据
  18.      * @param {any} element 追加数据
  19.      */
  20.     append(element) {
  21.         let node = new DoublyNode(element);
  22.         if (this.head === null) {
  23.             this.head = node;
  24.             this.tail = node;
  25.         } else {
  26.             this.tail.next = node;
  27.             node.prev = this.tail;
  28.             this.tail = node;
  29.         }
  30.         this.size++;
  31.     }
  33.     /**
  34.      * @method 指定位置追加数据
  35.      * @param {*} position 位置
  36.      * @param {*} element 追加数据
  37.      */
  38.     appendAt(position, element) {
  39.         if (position < 0 || position > this.size) {
  40.             throw new Error("position out range");
  41.         }
  42.         let node = new DoublyNode(element);
  43.         if (position === 0) {
  44.             if (this.head === null) {
  45.                 this.head = node;
  46.                 this.tail = node;
  47.             } else {
  48.                 node.next = this.head;
  49.                 this.head.perv = node;
  50.                 this.head = node;
  51.             }
  52.         } else if (position === this.size) {
  53.             this.tail.next = node;
  54.             node.prev = this.tail;
  55.             this.tail = node;
  56.         } else {
  57.             let pre = this.getNode(position - 1);
  58.             pre.next = node;
  59.             node.prev = pre;
  60.             node.next = pre.next;
  61.             pre.prev = node;
  62.         }
  63.         this.size++;
  64.     }
  66.     /**
  67.      * @method 删除指定位置数据
  68.      * @param {*} position 位置
  69.      */
  70.     removeAt(position) {
  71.         if (position < 0 || position >= this.size) {
  72.             throw new Error("position out range");
  73.         }
  74.         let current = this.head;
  75.         if (position === 0) {
  76.             if (this.size === 1) {
  77.                 this.head = null;
  78.                 this.tail = null;
  79.             } else {
  80.                 this.head = current.next;
  81.                 this.head.prev = null;
  82.             }
  83.         } else if (position === this.size - 1) {
  84.             this.tail.prev.next = null;
  85.             this.tail = this.tail.prev;
  86.         } else {
  87.             let pre = this.getNode(position - 1);
  88.             current = pre.next;
  89.             pre.next = current.next;
  90.         }
  91.         this.size--;
  92.     }
  94.     /**
  95.      * @method 修改指定位置数据
  96.      * @param {Number} position 位置
  97.      * @param {any} element 追加数据
  98.      * TODO: 性能优化点 this.size / 2 > position 从头向后遍历, 反之则反
  99.      */
  100.     update(position, element) {
  101.         if (position < 0 || position >= this.size) {
  102.             throw new Error("position out range");
  103.         }
  104.         let pre = this.getNode(position);
  105.         pre.element = element;
  106.     }
  108.     /**
  109.      * @method 查找指定位置数据
  110.      * @param {Number} position 位置
  111.      * @return {any} 返回数据
  112.      * TODO: 性能优化点 this.size / 2 > position 从头向后遍历, 反之则反
  113.      */
  114.     getData(position) {
  115.         if (position < 0 || position >= this.size) {
  116.             throw new Error("position out range");
  117.         }
  118.         let pre = this.getNode(position);
  119.         return pre.element;
  120.     }
  122.     /**
  123.      * @method 查找指定数据索引
  124.      * @param {Number} element
  125.      * @return {Number} 索引
  126.      */
  127.     indexOf(element) {
  128.         let current = this.head;
  129.         for (let i = 0; i < this.size; i++) {
  130.             if (current.element === element) {
  131.                 return i;
  132.             }
  133.             current = current.next;
  134.         }
  135.         return -1;
  136.     }
  138.     /**
  139.      * @method 返回链表长度
  140.      * @return {Number} 链表长度
  141.      */
  142.     get length() {
  143.         return this.size;
  144.     }
  146.     getNode(index) {
  147.         if (index < 0 || index >= this.size) {
  148.             throw new Error("out range");
  149.         }
  150.         let current = this.head;
  151.         for (let i = 0; i < index; i++) {
  152.             current = current.next;
  153.         }
  154.         return current;
  155.     }
  156. }
  158. let ll = new DoublyLinkedList();
  159. ll.append(1);
  160. ll.append(2);
  161. ll.append(3);
  162. ll.append(4);
  163. // ll.appendAt(2, 3);
  164. // ll.appendAt(3, 4);
  165. // ll.appendAt(3, 2);
  166. // ll.removeAt(0);
  167. // ll.removeAt(1);
  169. // console.log(ll.getData(3));
  171. // console.log(ll.indexOf(1));
  172. // console.log(ll.indexOf(2));
  173. // console.log(ll.indexOf(3));
  174. // console.log(ll.indexOf(4));
  175. // console.log(ll.indexOf(5));
  177. console.dir(ll, {
  178.     depth: 100,
  179. });
  180. console.log(ll.length);
  182. setTimeout(() => {
  183.     ll.update(3, 9);
  184.     console.dir(ll, {
  185.         depth: 100,
  186.     });
  187. }, 1000);

单向循环链表

双向循环链表

环形链表