单向链表
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.count = 0;
this.head = null;
}
// 链表尾部追加元素
append(value) {
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.getElementAt(this.count - 1);
currentNode.next = newNode;
}
this.count++;
}
// 在指定位置插入元素，越界返回false，表示插入失败
insert(index, value) {
if (index < 0 || index > this.count) {
return false;
}
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
} else if (index === 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let lastNode = this.getElementAt(index - 1);
newNode.next = lastNode.next;
lastNode.next = newNode;
}
this.count++;
return true;
}
// 移除指定元素。若找不到该元素，则返回false，表示移除失败
remove(value) {
let lastNode = null;
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
if (lastNode === null) {
this.head = this.head.next;
} else {
lastNode.next = currentNode.next;
}
this.count--;
return true;
}
lastNode = currentNode;
currentNode = currentNode.next;
}
return false;
}
// 移除指定位置上的元素。若找不到该位置，则返回false，表示移除失败
removeAt(index) {
if (index < 0 || index > this.count - 1) {
return false;
}
if (index === 0) {
this.head = this.head.next;
} else {
let lastNode = this.getElementAt(index - 1);
lastNode.next = lastNode.next.next;
}
this.count--;
return true;
}
// 返回指定位置的节点，越界返回undefined
getElementAt(index) {
if (index < 0 || index >= this.count) {
return undefined;
}
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
// 返回元素的索引值，若没改元素则返回-1
indexOf(value) {
let currentNode = this.head;
let index = 0;
while (currentNode) {
if (currentNode.value === value) {
return index;
}
currentNode = currentNode.next;
index++;
}
return -1;
}
// 返回链表元素个数
size() {
return this.count;
}
// 返回当前是否为空链表
isEmpty() {
return this.count === 0
}
// 清空链表
clear() {
this.count = 0;
this.head = null;
}
// 输出链表每项元素
toString() {
let arr = [];
let currentNode = this.head;
while (currentNode) {
arr.push(currentNode.value);
currentNode = currentNode.next;
}
return arr.join(",")
}
}
let linkedList = new LinkedList();
linkedList.append(1)
linkedList.append(3)
linkedList.append(5)
linkedList.append(7)
linkedList.insert(1, 2)
linkedList.insert(2, 0)
linkedList.insert(1, 10)
console.log(linkedList.toString())
// console.log(linkedList.indexOf(0))
// console.log(linkedList.removeAt(1))
console.log(linkedList.remove(7))
console.log(linkedList.toString())
// console.log(linkedList.insert(linkedList.size(), 1000))
// console.log(linkedList.toString())
JavaScript
INFO