class Node { //结点内部一个next指针一个元素数据
constructor(element) {
this.next = null;
this.element = element;
}
}
class LinkedList {
constructor() { //链表类属性为一个长度一个头指针
this.count = 0;
this.head = null;
}
push(element) {
let node = new Node(element);
if (this.head == null) {
this.head = node;
} else {
let current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.count++;
}
getElementAt(index) {
if (index < 0 || index >= this.count) {
return undefined;
}
let current = this.head; //index===0时不进入循环，返回的current指向head
for (let i = 0; i < index; i++) {
current = current.next;
}
return current;
}
insert(element, index) {
if (index < 0 || index > this.count) {
return false;
}
let node = new Node(element);
if (index === 0) {
node.next = this.head;
this.head = node;
} else {
let current = this.getElementAt(index - 1);
node.next = current.next;
current.next = node;
}
this.count++;
return this.count;
}
removeAt(index) {
if (index < 0 || index >= this.count) {
return undefined;
}
let current = this.head;
if (index === 0) {
this.head = current.next;
return current.element;
}
let previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
this.count--;
return current.element;
}
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.count; i++) {
if (current.element === element) {
return i;
}
current = current.next;
}
return -1;
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
getHead() {
return this.head;
}
clear() {
this.head = undefined;
this.count = 0;
}
toString() {
if (this.count === 0) {
return "";
}
let current = this.head;
let objString = `${current.element}`;
while (current.next != null) {
current = current.next;
objString = `${objString},${current.element}`;
}
return objString;
}
}
//测试用例
let list = new LinkedList();
console.log('push element 15');
list.push(15);
console.log('list.indexOf(15) => ', list.indexOf(15));
console.log('push element 10');
list.push(10);
console.log('list.toString() => ', list.toString());
console.log('list.indexOf(10) => ', list.indexOf(10));
console.log('push element 13');
list.push(13);
console.log('list.toString() => ', list.toString());
console.log('list.indexOf(13) => ', list.indexOf(13));
console.log('list.indexOf(10) => ', list.indexOf(10));
console.log('push elements 11 and 12');
list.push(11);
list.push(12);
console.log('list.toString() => ', list.toString());
console.log('list.removeAt(1) => ', list.removeAt(1));
console.log('list.toString() => ', list.toString());
console.log('list.removeAt(3) => ', list.removeAt(3));
console.log('list.toString() => ', list.toString());
console.log('push element 14');
list.push(14);
console.log('list.toString() => ', list.toString());
console.log('insert element 16 pos 0 => ', list.insert(16, 0));
console.log('list.toString() => ', list.toString());
console.log('insert element 17 pos 1 => ', list.insert(17, 1));
console.log('list.toString() => ', list.toString());
console.log('insert element 18 pos list.size() => ', list.insert(18, list.size()));
console.log('list.toString() => ', list.toString());
console.log('remove element 16 => ', list.remove(16));
console.log('list.toString() => ', list.toString());
console.log('remove element 11 => ', list.remove(11));
console.log('list.toString() => ', list.toString());
console.log('remove element 18 => ', list.remove(18));
console.log('list.toString() => ', list.toString());