单链表链表结构的实现

链表 - 图1

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.     }
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.         this.length = 0;
  11.         this.head = null;
  12.     }
  14.     equalsFn(a, b) {
  15.         return a === b;
  16.     }
  17. }

功能

  1. push(element)：向链表尾部添加一个新元素。
  2. insert(element, position)：向链表的特定位置插入一个新元素。
  3. getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。
  4. remove(element)：从链表中移除一个元素。
  5. indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
  6. removeAt(position)：从链表的特定位置移除一个元素。
  7. isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0 则返回false。
  8. size()：返回链表包含的元素个数，与数组的length 属性类似。
  9. toString()：返回表示整个链表的字符串。由于列表项使用了Node 类，就需要重写继承自JavaScript 对象默认的toString 方法，让其只输出元素的值。

push

  1.     push(val) {
  2.         let newNode = new Node(val);
  3.         let curr;
  4.         if (!this.head) {   // 刚开始链表为空，就把这个设置为head
  5.             this.head = newNode;
  6.         } else {
  7.             curr = this.head;
  8.             while (curr.next) {    // 一直找到链表末尾
  9.                 curr = curr.next;
  10.             }
  11.             curr.next = newNode;
  12.         }
  13.         this.length++;
  14.     }

removeAt

链表 - 图2

  1.     removeAt(index) {
  2.         if (index < this.length && index >= 0) {
  3.             let curr = this.head;
  4.             if (index === 0) {
  5.                 this.head = curr.next;
  6.             } else {
  7.                 // 找到index前一个后停止，下一个就是要删除的结点
  8.                 for (let i = 1; i < index; i++) {
  9.                     curr = curr.next;
  10.                 }
  11.                 let beRemove = curr.next;
  12.                 // 改变要被删除结点的上一个结点的指向
  13.                 curr.next = beRemove.next;
  14.                 this.length--;
  15.                 return beRemove;
  16.             }
  17.         }
  18.     }

getElementAt

  1.     getElementAt(index) {
  2.         if (index < this.length && index >= 0) {
  3.             let curr = this.head;
  4.             if (index === 0) return curr;
  5.             else {
  6.                 for (let i = 1; i <= index; i++) {
  7.                     curr = curr.next;
  8.                 }
  9.                 return curr;
  10.             }
  11.         }
  12.     }

重写removeAt

  1.     removeAt(index) {
  2.         let curr = this.getElementAt(index - 1);
  3.         curr.next = curr.next.next;

insert

链表 - 图3

  1.     insert(index, value) {
  2.         let newNode = new Node(value);
  3.         if (index < this.length && index >= 0) {
  4.             let curr = this.head;
  5.             if (index === 0) {  // index 为0，改变头结点指向就行了
  6.                 this.head = newNode;
  7.                 this.head.next = curr;
  8.             } else {
  9.                 // 找到插入位置的前一个，
  10.                 for (let i = 1; i < index; i++) {
  11.                     curr = curr.next;
  12.                 }
  13.                 let nextNode = curr.next;
  14.                 curr.next = newNode;
  15.                 newNode.next = nextNode;
  16.             }
  17.             this.length++;
  18.         }
  19.     }

indexOf

  1.     indexOf(value) {
  2.         let curr = this.head;   // 存入head
  3.         if (this.equalsFn(curr.value, value)) {
  4.             return 0;
  5.         }
  6.         for (let i = 1; i < this.length; i++) {
  7.             curr = curr.next;
  8.             if (this.equalsFn(curr.value, value)) {
  9.                 return i;
  10.             }
  11.         }
  13.         return -1;
  14.     }

removeValue

  1.     removeValue(value) {
  2.         let curr = this.head;
  3.         let prev = null;
  4.         if (this.equalsFn(curr.value, value)) {
  5.             this.head = curr.next;
  6.             this.length--;
  7.         }
  8.         for (let i = 1; i < this.length; i++) {
  9.             prev = curr;
  10.             curr = curr.next;
  11.             if (this.equalsFn(curr.value, value)) {
  12.                 prev.next = curr.next;
  13.                 this.length--;
  14.             }
  15.         }
  16.         return undefined;
  17.     }

toString

  1.     toString() {
  2.         let objString = "";
  3.         let curr = this.head;
  4.         if (!curr) {
  5.             return objString;
  6.         } else {
  7.             objString = `${curr.value}`;
  8.             for (let i = 1; i < this.length; i++) {
  9.                 curr = curr.next;
  10.                 objString = `${objString}, ${curr.value}`;
  11.             }
  12.             return objString;
  13.         }
  14.     }

完整代码

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.     }
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.         this.length = 0;
  11.         this.head = null;
  12.     }
  14.     equalsFn(a, b) {
  15.         return a === b;
  16.     }
  18.     push(val) {
  19.         let newNode = new Node(val);
  20.         let curr;
  21.         if (!this.head) {   // 刚开始链表为空，就把这个设置为head
  22.             this.head = newNode;
  23.         } else {
  24.             curr = this.head;
  25.             while (curr.next) {    // 一直找到链表末尾
  26.                 curr = curr.next;
  27.             }
  28.             curr.next = newNode;
  29.         }
  30.         this.length++;
  31.     }
  33.     removeAt(index) {
  35.         let curr = this.getElementAt(index - 1);
  36.         curr.next = curr.next.next;
  37.     }
  39.     getElementAt(index) {
  40.         if (index < this.length && index >= 0) {
  41.             let curr = this.head;
  42.             if (index === 0) return curr;
  43.             else {
  44.                 for (let i = 1; i <= index; i++) {
  45.                     curr = curr.next;
  46.                 }
  47.                 return curr;
  48.             }
  49.         }
  50.     }
  52.     insert(index, value) {
  53.         let newNode = new Node(value);
  54.         if (index < this.length && index >= 0) {
  55.             let curr = this.head;
  56.             if (index === 0) {  // index 为0，改变头结点指向就行了
  57.                 this.head = newNode;
  58.                 this.head.next = curr;
  59.             } else {
  60.                 // 找到插入位置的前一个，
  61.                 for (let i = 1; i < index; i++) {
  62.                     curr = curr.next;
  63.                 }
  64.                 let nextNode = curr.next;
  65.                 curr.next = newNode;
  66.                 newNode.next = nextNode;
  67.             }
  68.             this.length++;
  69.         } else {
  70.             throw "索引值错误";
  71.         }
  72.     }
  74.     indexOf(value) {
  75.         let curr = this.head;   // 存入head
  76.         if (this.equalsFn(curr.value, value)) {
  77.             return 0;
  78.         }
  79.         for (let i = 1; i < this.length; i++) {
  80.             curr = curr.next;
  81.             if (this.equalsFn(curr.value, value)) {
  82.                 return i;
  83.             }
  84.         }
  86.         return -1;
  87.     }
  89.     removeValue(value) {
  90.         let curr = this.head;
  91.         let prev = null;
  92.         if (this.equalsFn(curr.value, value)) {
  93.             this.head = curr.next;
  94.             this.length--;
  95.         }
  96.         for (let i = 1; i < this.length; i++) {
  97.             prev = curr;
  98.             curr = curr.next;
  99.             if (this.equalsFn(curr.value, value)) {
  100.                 prev.next = curr.next;
  101.                 this.length--;
  102.             }
  103.         }
  104.         return undefined;
  105.     }
  107.     toString() {
  108.         let objString = "";
  109.         let curr = this.head;
  110.         if (!curr) {
  111.             return objString;
  112.         } else {
  113.             objString = `${curr.value}`;
  114.             for (let i = 1; i < this.length; i++) {
  115.                 curr = curr.next;
  116.                 objString = `${objString}, ${curr.value}`;
  117.             }
  118.             return objString;
  119.         }
  120.     }
  122.     getHead() {
  123.         return this.head;
  124.     }
  126.     isEmpty() {
  127.         return this.length === 0 ? true : false;
  128.     }
  130.     size() {
  131.         return this.length;
  132.     }
  133. }
  135. let linkedList = new LinkedList();
  136. linkedList.push("a");
  137. linkedList.push("b");
  138. linkedList.push("c");
  139. // linkedList.removeAt(1);
  140. linkedList.insert(1, "aa");
  141. console.log(linkedList.getElementAt(2));
  142. console.log(linkedList.indexOf("a"));
  143. console.log(linkedList.removeValue("c"));
  144. console.log(linkedList.size());
  145. console.log(linkedList.isEmpty());
  146. console.log(linkedList);
  147. console.log(linkedList.toString());

双向链表的实现

链表 - 图4

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.         this.prev = null;
  6.     }
  7. }
  9. class DBLinkedList {
  10.     constructor() {
  11.         this.length = 0;
  12.         this.head = null;
  13.     }
  15.     equalsFn(a, b) {
  16.         return a === b;
  17.     }
  18. }

双向链表需要讨论的情况

  1. 当结点为头结点时
  2. 当结点为最后一个结点时
  3. 当结点有且只有一个结点时

重构链表方法

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.         this.prev = null;
  6.     }
  7. }
  9. class DBLinkedList {
  10.     constructor() {
  11.         this.length = 0;
  12.         this.head = null;
  13.     }
  15.     equalsFn(a, b) {
  16.         return a === b;
  17.     }
  19.     push(val) {
  20.         let newNode = new Node(val);
  21.         let prev = this.head;
  22.         let curr;
  23.         if (!this.head) {   // 刚开始链表为空，就把这个设置为head
  24.             this.head = newNode;
  25.         } else {
  26.             curr = this.head;
  27.             while (curr.next) {    // 一直找到链表末尾
  28.                 curr = curr.next;
  29.                 prev = curr;
  30.             }
  31.             curr.next = newNode;
  32.             newNode.prev = prev;
  33.         }
  34.         this.length++;
  35.     }
  37.     removeAt(index) {
  38.         if (index < this.length && index >= 0) {
  39.             let curr = this.head;
  40.             if (index === 0) {
  41.                 this.head = curr.next;
  42.                 if (this.length !== 1) {
  43.                     this.head.prev = null;
  44.                 }
  45.                 this.length--;
  46.             } else {
  47.                 // 找到index前一个后停止，下一个就是要删除的结点
  48.                 for (let i = 1; i < index; i++) {
  49.                     curr = curr.next;
  50.                 }
  51.                 let beRemove = curr.next;
  52.                 // 改变要被删除结点的上一个结点的指向
  53.                 curr.next = beRemove.next;
  54.                 if (index !== this.length - 1) {
  55.                     beRemove.next.prev = curr;
  56.                 }
  57.                 this.length--;
  58.                 return beRemove;
  59.             }
  60.         }
  61.     }
  63.     getElementAt(index) {
  64.         if (index < this.length && index >= 0) {
  65.             let curr = this.head;
  66.             if (index === 0) return curr;
  67.             else {
  68.                 for (let i = 1; i <= index; i++) {
  69.                     curr = curr.next;
  70.                 }
  71.                 return curr;
  72.             }
  73.         }
  74.     }
  76.     insert(index, value) {
  77.         let newNode = new Node(value);
  78.         if (index < this.length && index >= 0) {
  79.             let curr = this.head;
  80.             if (index === 0) {  // index 为0，改变头结点指向就行了
  81.                 this.head = newNode;
  82.                 this.head.next = curr;
  83.                 if (this.length > 1) {
  84.                     this.head.prev = null;
  85.                 }
  86.             } else {
  87.                 // 找到插入位置的前一个，
  88.                 for (let i = 1; i < index; i++) {
  89.                     curr = curr.next;
  90.                 }
  91.                 let nextNode = curr.next;
  92.                 curr.next = newNode;
  93.                 newNode.prev = curr;
  94.                 newNode.next = nextNode;
  95.                 if (index !== this.length - 1) {
  96.                     nextNode.prev = newNode;
  97.                 }
  98.             }
  99.             this.length++;
  100.         } else {
  101.             throw "索引值错误";
  102.         }
  103.     }
  105.     indexOf(value) {
  106.         let curr = this.head;   // 存入head
  107.         if (this.equalsFn(curr.value, value)) {
  108.             return 0;
  109.         }
  110.         for (let i = 1; i < this.length; i++) {
  111.             curr = curr.next;
  112.             if (this.equalsFn(curr.value, value)) {
  113.                 return i;
  114.             }
  115.         }
  117.         return -1;
  118.     }
  120.     removeValue(value) {
  121.         let curr = this.head;
  122.         let prev = null;
  123.         if (this.equalsFn(curr.value, value)) {
  124.             this.head = curr.next;
  125.             if (this.head) {
  126.                 this.head.prev = null;
  127.             }
  128.             this.length--;
  129.         }
  130.         for (let i = 1; i < this.length; i++) {
  131.             prev = curr;
  132.             curr = curr.next;
  133.             if (this.equalsFn(curr.value, value)) {
  134.                 prev.next = curr.next;
  135.                 if (curr.next) {
  136.                     curr.next.prev = prev;
  137.                 }
  138.                 this.length--;
  139.             }
  140.         }
  141.         return undefined;
  142.     }
  144.     toString() {
  145.         let objString = "";
  146.         let curr = this.head;
  147.         if (!curr) {
  148.             return objString;
  149.         } else {
  150.             objString = `${curr.value}`;
  151.             for (let i = 1; i < this.length; i++) {
  152.                 curr = curr.next;
  153.                 objString = `${objString}, ${curr.value}`;
  154.             }
  155.             return objString;
  156.         }
  157.     }
  159.     getHead() {
  160.         return this.head;
  161.     }
  163.     isEmpty() {
  164.         return this.length === 0 ? true : false;
  165.     }
  167.     size() {
  168.         return this.length;
  169.     }
  170. }

循环链表的概念

链表 - 图5

  • 循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。
  • 循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针不是引用undefined，而是指向第一个元素（head）