链表
链表是一种物理存储单元上非线性、非连续性的数据结构（它在数据逻辑上是线性的），它的每个节点由两个域组成：数据域和指针域。数据域中存储实际数据，指针域则存储着指针信息，指向链表中的下一个元素或者上一个元素。正是由于指针的存在，链表的存储在物理单元是非连续性的。
链表的优点和缺点同样明显。和线性表相比，链表在添加和删除节点上的效率更高，因为其只需要修改指针信息即可完成操作，而不像线性表（数组）那样需要移动元素。同样的，链表的长度在理论上也是无限的（在存储器容量范围内），并可以动态变化长度，相比线性表优势很大。 相应的，由于线性表无法随机访问节点，只能通过指针顺着链表进行遍历查询来访问，故其访问数据元素的效率比较低。
JS实现单链表
function LinkedList() {
let Node = function (ele) {
this.ele = ele;
this.next = null;
}
let length = 0,
head = null; //头指针
//向尾部追加元素
this.append = function (ele) {
let node = new Node(ele),
temp; //临时指针
if (!head) {
head = node;
} else {
temp = head;
while (temp.next) {
temp = temp.next
}
temp.next = node;
}
length++;
return true;
}
//插入到指定位置
this.insert = function (position, ele) {
if (position >= 0 && position < length) {
let node = new Node(ele),
temp = head,
index = 0,
previous;
if (position == 0) {
node.next = temp;
head = node;
} else {
while (index++ < position) {
previous = temp;
temp = temp.next;
}
node.next = temp;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
}
//删除指定位置元素
this.removeAt = function (position) {
if (position > -1 && position < length) {
let temp = head,
previous,
index = 0;
if (position == 0) {
head = head.next;
} else {
while (index++ < position) {
previous = temp;
temp = temp.next;
}
previous.next = temp.next;
}
length--;
return temp.ele;
} else {
return null;
}
}
//删除所有值为ele的元素
this.removeEle = function (ele) {
let temp = head,
previous,
num = 0;
if (ele == temp.ele) {
head = head.next;
length--;
num++;
}
while (temp.next) {
previous = temp;
temp = temp.next;
if (temp.ele == ele) {
previous.next = temp.next;
length--;
num++;
}
}
return num;
}
//删除最后一个元素
this.pop = function () {
let temp = head,
previous = temp;
if (length < 1) {
return false;
}
if (length == 1) {
head = null;
length--;
return temp.ele;
}
while (temp.next) {
previous = temp;
temp = temp.next;
}
previous.next = null;
length--;
return temp.ele;
}
this.indexOf = function (ele) {
let temp = head,
index = 0;
while (temp) {
if (temp.ele == ele) {
return index;
}
temp = temp.next;
index++;
}
return -1;
}
this.toString = function () {
let temp = head,
string = '';
while (temp) {
string += temp.ele + ' ';
temp = temp.next;
}
return string;
}
this.length = function () {
return length;
}
this.isEmpty = function () {
return length === 0;
};
this.getHead = function () {
return head.ele;
}
}
let mylist = new LinkedList();
mylist.append('A');
mylist.append('B');
mylist.append('C');
mylist.append('D');
mylist.append('C');
mylist.append('B');
mylist.append('A');
console.log(mylist.toString());
console.log(mylist.pop());
console.log(mylist.toString());
console.log('移除%d个C', mylist.removeEle('C'));
console.log(mylist.toString());
console.log(mylist.length());
console.log(mylist.getHead());
console.log(mylist.indexOf('C'))
JS实现单循环链表：
在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。
function CircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
head = null;
this.append = function(element){
var node = new Node(element),
current;
if (!head) {
head = node;
node.next = head;
}else{
current = head;
while(current.next !== head){
current = current.next;
}
current.next = node;
node.next = head;
};
length++;
return true;
};
this.insert = function(position, element){
if(position > -1 && position < length){
var node = new Node(element),
index = 0,
current = head,
previous;
if (position === 0) {
node.next = head;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
};
length++;
return true;
}else{
return false;
}
};
//移除指定位置元素
this.removeAt = function(position){
if(position > -1 && 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.remove = function (element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck == 0){
head = current.next;
length--;
return true;
}else{
previous.next = current.next;
length--;
return true;
}
}else{
previous = current;
current = current.next;
indexCheck++;
}
}
return false;
};
//移除最后一个元素
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
length--;
return previous.element; //返回移除的元素
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index < length){
if(current.element === element){
return index;
}else{
index++;
current = current.next;
}
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '',
indexCheck = 0;
while(current && indexCheck < length){
string += current.element;
current = current.next;
indexCheck++;
}
return string;
};
}
let mylist=new CircularLinkedList();
mylist.append('A');
mylist.append('B');
mylist.append('C');
mylist.append('D');
console.log(mylist.toString());
console.log(mylist.remove()); //D
console.log(mylist.toString());