javaScript数据结构--链表
实现一个链表还需要一个辅助的类：Node，Node对象有2个属性，element :当前元素；next:指向下一个对象的指针。
Node对象结构
链表结构
链表的实现：
function LinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.append = function(element) {
const node = new Node(element);
let current ;
if(head === null) {
head = node;
} else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}
length ++;
}
this.insert = function(position, element) {
if(position >= 0 && position <= length) {
const node = new Node(element);
let current = head,
previous,
index = 0;
if(position === 0) {
head.next = current;
head = node;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
}
this.remove = function(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
this.removeAt = function(position) {
if(position >= 0 && position <= length) {
var current = head,
previous,
index = 0;
if(position === 0) {
head = current.next;
}else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
}else {
return null;
}
}
this.isEmpty = function() {
return length === 0
}
this.size = function() {
return length;
}
this.toString = function() {
var current = head,
string = '';
while(current) {
string += String(current.element);
current = current.next;
}
return string;
}
this.indexOf = function(element) {
var current = head,
index = -1;
while(current) {
index++;
if(current.element === element) {
return index;
}
current = current.next;
}
return -1;
}
this.getHead = function() {
return head;
}
}
var l = new LinkedList();
l.append("a");
l.append("b");
l.append("c");
console.log(l.size()); // 3
console.log(l.toString()); // abc
l.insert(1, "d")
console.log(l.size()); // 4
console.log(l.toString()); // adbc
console.log(l.indexOf("e")); // -1
console.log(l.indexOf("b")); // 2
l.removeAt(2);
console.log(l.toString()); // adc
l.remove("a"); // dc
console.log(l.toString());
l.remove("dd");
console.log(l.toString()); // dc
