链表特点
查找O(n)，插入O(n)，删除O(n)
链表结构
{
head: {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: null
}
}
}
}
构造链表
function Node(val, next) {
this.val = val;
this.next = next;
}
function LinkList() {
this.head = null;
}
链表方法
LinkList.prototype = {
isEmpty() {
return this.head === null;
},
find(val) {
if (this.isEmpty()) {
return null;
}
var curr = this.head;
while (curr) {
if (val === curr.val) {
break;
}
curr = curr.next;
}
return curr;
},
remove(val) {
if (this.isEmpty()) {
return false;
}
var curr = this.head;
var parent = curr;
while (curr) {
if (val === curr.val) {
parent.next = curr.next;
return true;
}
parent = curr;
curr = curr.next;
}
return false;
},
addHead(val) {
if (this.isEmpty()) {
this.head = new Node(val, null);
return;
}
this.head = new Node(val, this.head);
},
addTail(val) {
if (this.isEmpty()) {
this.head = new Node(val, null);
return;
}
var curr = this.head;
while (curr) {
if (curr.next === null) {
curr.next = new Node(val, null);
break;
}
curr = curr.next;
}
},
insertBefore(val, oVal) {
if (this.isEmpty()) {
this.head = new Node(val, null);
return true;
}
var curr = this.head;
var parent = curr;
while (curr) {
if (oVal === curr.val) {
parent.next = new Node(val, curr);
return true;
}
parent = curr;
curr = curr.next;
}
return false;
},
insertBehind(val, oVal) {
if (this.isEmpty()) {
this.head = new Node(val, null);
return true;
}
var curr = this.head;
while (curr) {
if (oVal === curr.val) {
curr.next = new Node(val, curr.next);
return true;
}
curr = curr.next;
}
return false;
}
};
测试代码
var l = new LinkList();
l.addHead(1);
l.addTail(2);
l.addHead(0);
l.addTail(3);
l.insertBefore(100, 2);
l.insertBehind(200, 100);
l.remove(100);
console.log(l.find(200));
