单链表封装 - 使用JavaScript封装

痛苦就是在蜕变吗

链表：

链表就是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列结点组成，结点可以在运行时动态的生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点：

1. 插入、删除数据效率 O(1)级别（只需要更改指针指向即可），随机访问效率低 O(n)级别 （需要从链头至链尾进行遍历）
2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

单链表：

每个节点只包含一个指针，即后继指针。

单链表的封装- JS封装：

<script>class Node {constructor(element) {this.element = element;this.next = null;}}class LinkedList {// #constructor() {this.count = 0;this.head = null;}// push 添加一个节点push (element) {const node = new Node(element);// header是空if (this.head === null) {this.head = node;} else {let current = this.head;while (current.next !== null) {current = current.next;}current.next = node;}this.count++;}// 指定位置删除 传入索引removeAt (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous;for (let i = 0; i < index; i++) {previous = current;current = current.next;}previous.next = current.next;}this.count--;return current.element;}return;}// 指定位置删除-方法二利用getNodeAt(index) 传入索引removeAt2 (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous = this.getNodeAt(index - 1);current = previous.next;previous.next = current.next;}this.count--;return current.element;}return;}// 根据索引获得节点nodegetNodeAt (index) {if (index >= 0 && index < this.count) {let node = this.head;for (let i = 0; i < index; i++) {node = node.next;}return node;}return;}// 判断是否相等equalFn (a, b) {// 暴力写法:// 也有缺陷 JSON.stringify({a:1,b:2}) !== JSON.stringify({b:2,a:1})return JSON.stringify(a) === JSON.stringify(b);// 可以使用第三方库}// 根据元素返回索引indexOf (element) {let current = this.head;for (let i = 0; i < this.count; i++) {if (this.equalFn(current.element, element)) {return i;}current = current.next;}}// 直接根据值删除remove (element) {// 根据数据返回索引的方法const index = this.indexOf(element);return this.removeAt(index);}// 指定位置插入内容insert (element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element);if (index == 0) {const current = this.head;node.next = current;this.head = node;} else {const previous = this.getNodeAt(index - 1);const current = previous.next;previous.next = node;node.next = current;}this.count++;return true;}return false;}// 判断是否为空isEmpty () {return this.size() === 0;}// 判断长度size () {return this.count;}// 返回链头getHead () {return this.head;}}let list = new LinkedList()
</script>

单链表的应用：

解决回文：

举个例子，当初判断回文的时候我们使用的双端队列，在这里使用单链表解决:

<script>class Node {constructor(element) {this.element = element;this.next = null;}}class LinkedList {// #constructor() {this.count = 0;this.head = null;}// push 添加一个节点push (element) {const node = new Node(element);// header是空if (this.head === null) {this.head = node;} else {let current = this.head;while (current.next !== null) {current = current.next;}current.next = node;}this.count++;}// 指定位置删除 传入索引removeAt (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous;for (let i = 0; i < index; i++) {previous = current;current = current.next;}previous.next = current.next;}this.count--;return current.element;}return;}// 指定位置删除-方法二利用getNodeAt(index) 传入索引removeAt2 (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous = this.getNodeAt(index - 1);current = previous.next;previous.next = current.next;}this.count--;return current.element;}return;}// 根据索引获得节点nodegetNodeAt (index) {if (index >= 0 && index < this.count) {let node = this.head;for (let i = 0; i < index; i++) {node = node.next;}return node;}return;}// 判断是否相等equalFn (a, b) {// 暴力写法:// 也有缺陷 JSON.stringify({a:1,b:2}) !== JSON.stringify({b:2,a:1})return JSON.stringify(a) === JSON.stringify(b);// 可以使用第三方库}// 根据元素返回索引indexOf (element) {let current = this.head;for (let i = 0; i < this.count; i++) {if (this.equalFn(current.element, element)) {return i;}current = current.next;}}// 直接根据值删除remove (element) {// 根据数据返回索引的方法const index = this.indexOf(element);return this.removeAt(index);}// 指定位置插入内容insert (element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element);if (index == 0) {const current = this.head;node.next = current;this.head = node;} else {const previous = this.getNodeAt(index - 1);const current = previous.next;previous.next = node;node.next = current;}this.count++;return true;}return false;}// 判断是否为空isEmpty () {return this.size() === 0;}// 判断长度size () {return this.count;}// 返回链头getHead () {return this.head;}}
</script>
<script>// 使用单链表解决回文问题function test (str) {const lowstr = str.toLocaleLowerCase().split(" ").join("");let list = new LinkedList();for (let i = 0; i < lowstr.length; i++) {list.push(lowstr[i]);}let isEqual = true;while (list.size() > 1) {if (list.removeAt(0) !== list.removeAt(list.size() - 1)) {isEqual = false;break;}}return isEqual;}test("D  a   d");
</script>

解决击鼓传花：

举个例子，当初击鼓传花的时候我们使用的队列，在这里使用单链表解决:

<script>class Node {constructor(element) {this.element = element;this.next = null;}}class LinkedList {// #constructor() {this.count = 0;this.head = null;}// push 添加一个节点push (element) {const node = new Node(element);// header是空if (this.head === null) {this.head = node;} else {let current = this.head;while (current.next !== null) {current = current.next;}current.next = node;}this.count++;}// 指定位置删除 传入索引removeAt (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous;for (let i = 0; i < index; i++) {previous = current;current = current.next;}previous.next = current.next;}this.count--;return current.element;}return;}// 指定位置删除-方法二利用getNodeAt(index) 传入索引removeAt2 (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous = this.getNodeAt(index - 1);current = previous.next;previous.next = current.next;}this.count--;return current.element;}return;}// 根据索引获得节点nodegetNodeAt (index) {if (index >= 0 && index < this.count) {let node = this.head;for (let i = 0; i < index; i++) {node = node.next;}return node;}return;}// 判断是否相等equalFn (a, b) {// 暴力写法:// 也有缺陷 JSON.stringify({a:1,b:2}) !== JSON.stringify({b:2,a:1})return JSON.stringify(a) === JSON.stringify(b);// 可以使用第三方库}// 根据元素返回索引indexOf (element) {let current = this.head;for (let i = 0; i < this.count; i++) {if (this.equalFn(current.element, element)) {return i;}current = current.next;}}// 直接根据值删除remove (element) {// 根据数据返回索引的方法const index = this.indexOf(element);return this.removeAt(index);}// 指定位置插入内容insert (element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element);if (index == 0) {const current = this.head;node.next = current;this.head = node;} else {const previous = this.getNodeAt(index - 1);const current = previous.next;previous.next = node;node.next = current;}this.count++;return true;}return false;}// 判断是否为空isEmpty () {return this.size() === 0;}// 判断长度size () {return this.count;}// 返回链头getHead () {return this.head;}}
</script>
<script>// 击鼓传花function game (list, num) {let List = new LinkedList();for (let i = 0; i < list.length; i++) {List.push(list[i]);}while (List.size() > 1) {for (let i = 0; i < num; i++) {List.push(List.removeAt(0));}console.log(List.removeAt(0), '淘汰了');}console.log('获胜的是：', List.removeAt(0));}game(['kitty', 'Alice', 'AK', 'Box', 'Whe'], 7);
</script>

十进制进制转换其他进制：

举个例子，当初十进制转换其他进制的时候我们使用的栈，在这里使用单链表解决:

<script>class Node {constructor(element) {this.element = element;this.next = null;}}class LinkedList {// #constructor() {this.count = 0;this.head = null;}// push 添加一个节点push (element) {const node = new Node(element);// header是空if (this.head === null) {this.head = node;} else {let current = this.head;while (current.next !== null) {current = current.next;}current.next = node;}this.count++;}// 指定位置删除 传入索引removeAt (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous;for (let i = 0; i < index; i++) {previous = current;current = current.next;}previous.next = current.next;}this.count--;return current.element;}return;}// 指定位置删除-方法二利用getNodeAt(index) 传入索引removeAt2 (index) {if (index >= 0 && index < this.count) {let current = this.head;if (index == 0) {this.head = this.head.next;} else {let previous = this.getNodeAt(index - 1);current = previous.next;previous.next = current.next;}this.count--;return current.element;}return;}// 根据索引获得节点nodegetNodeAt (index) {if (index >= 0 && index < this.count) {let node = this.head;for (let i = 0; i < index; i++) {node = node.next;}return node;}return;}// 判断是否相等equalFn (a, b) {// 暴力写法:// 也有缺陷 JSON.stringify({a:1,b:2}) !== JSON.stringify({b:2,a:1})return JSON.stringify(a) === JSON.stringify(b);// 可以使用第三方库}// 根据元素返回索引indexOf (element) {let current = this.head;for (let i = 0; i < this.count; i++) {if (this.equalFn(current.element, element)) {return i;}current = current.next;}}// 直接根据值删除remove (element) {// 根据数据返回索引的方法const index = this.indexOf(element);return this.removeAt(index);}// 指定位置插入内容insert (element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element);if (index == 0) {const current = this.head;node.next = current;this.head = node;} else {const previous = this.getNodeAt(index - 1);const current = previous.next;previous.next = node;node.next = current;}this.count++;return true;}return false;}// 判断是否为空isEmpty () {return this.size() === 0;}// 判断长度size () {return this.count;}// 返回链头getHead () {return this.head;}}
</script>
<script>// 十进制进制转换其他进制function convert (decNumber, base) {let list = new LinkedList();let string = "";let number = decNumber;let baseString = "0123456789ABCDEF"while (number > 0) {list.push(number % base);number = Math.floor(number / base);}while (!(list.isEmpty())) {string += baseString[list.removeAt(list.size() - 1)];}return string;}convert(50, 8)
</script>