链表
数据结构 - 链表。
// 链表实现
// ES5
var linkedList = function() {
// 链表头
var head = null;
// 链表长度
var length = 0;
// 辅助类:节点
var Node = function(element) {
this.element = element;
this.next = null;
};
// 链表尾追加元素
this.append = function(element) {
var node = new Node(element);
if (head == null) {
head = node;
} else {
var current = head;
while (current.next) {
current = current.next;
}
// while循环执行完后,current已经是链表的最后一项了
current.next = node;
}
length++;
};
// 链表某个位置添加元素
this.insert = function(position, element) {
// 越界
if (position > -1 && position < length) {
var node = new Node(element);
var current = head;
// 在链表头添加
if (position == 0) {
head = node;
head.next = current;
// 在其他位置添加
} else {
var index = 0;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = node;
node.next = current;
}
length++;
}
};
// 链表某个位置移除元素
this.removeAt = function(position) {
// 越界
if (position > -1 && position < length) {
var current = head;
if (position == 0) {
head = current.next;
} else {
var index = 0;
var previous = null;
while(index < position) {
previous = current;
current = current.next;
index++;
}
// while循环执行完后,index == position
previous.next = current.next;
}
length--;
return current;
}
return null;
};
// 获取元素在链表中的位置
this.indexOf = function(element) {
var index = 0;
var current = head;
while (current) {
if (current.element == element) {
return index;
}
current = current.next;
index++;
}
return -1;
};
// removeAt(position) 删除某个位置的元素
// indexOf(element) 获取某个元素的位置
this.remove = function(element) {
return this.removeAt(this.indexOf(element));
};
// 检查链表是否为空
this.isEmpty = function() {
return length == 0;
};
// 获取链表长度
this.size = function() {
return length;
};
// 检查链表头
this.getHead = function() {
return head;
};
};
var l = new linkedList();
l.append(1);
l.append(2);
l.append(3);
l.insert(1, 10);