# JavaScript数据结构04 - 链表

1. 单向链表
2. 双向链表
3. 循环链表

## 二、链表的实现

### 2.1 单向链表

```// SinglyLinkedList
function Node (element) {
this.element = element;
this.next = null;
}

var length = 0;

this.append = function (element) {};
this.insert = function (position, element) {};
this.removeAt = function (position) {};
this.remove = function (element) {};
this.indexOf = function (element) {};
this.isEmpty = function () {};
this.size = function () {};
this.toString = function () {};
this.print = function () {};
}

• append(element)：向链表尾部添加新项
• insert(position, element)：向链表的特定位置插入一个新的项
• removeAt(position)：从链表的特定位置移除一项
• remove(element)：从链表中移除一项
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1
• isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
• size()：返回链表包含的元素个数，与数组的length属性类似
• toString()：由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
• print()：打印链表的所有元素

```  // 向链表尾部添加一个新的项
this.append = function (element) {
var node = new Node(element);

// 判断是否为空链表
if (currentNode === null) {
// 空链表
} else {
while (currentNode.next) {
// 后面还有node
currentNode = currentNode.next;
}
currentNode.next = node;
}

length++;
};

// 向链表特定位置插入一个新的项
this.insert = function (position, element) {
if (position < 0 && position > length) {
// 越界
return false;
} else {
var node = new Node(element);
var index = 0;
var previousNode;

if (position === 0) {
node.next = currentNode;
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}

previousNode.next = node;
node.next = currentNode;
}

length++;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var index = 0;
var previousNode;

if (position === 0) {
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}

length--;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var index = 0;
var previousNode;

if (position === 0) {
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}

length--;

return true;
}
};

// 从链表中移除指定项
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
};

// 返回元素在链表的索引，如果链表中没有该元素则返回-1
this.indexOf = function (element) {
var index = 0;

while (currentNode) {
if (currentNode.element === element) {
return index;
}

index++;
currentNode = currentNode.next;
}

return -1;
};

// 如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
this.isEmpty = function () {
return length == 0;
};

// 返回链表包含的元素个数，与数组的length属性类似
this.size = function () {
return length;
};

// 获取链表头部元素
};

// 由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
this.toString = function () {
var string = '';

while (currentNode) {
string += ',' + currentNode.element;
currentNode = currentNode.next;
}

return string.slice(1);
};

this.print = function () {
console.log(this.toString());
};

```// 创建单向链表实例

### 2.2 双向链表

```// 创建双向链表DoublyLinkedList类
function Node (element) {
this.element = element;
this.next = null;
this.prev = null;        // 新增
}

var length = 0;
var tail = null;          // 新增
}

```  // 向链表尾部添加一个新的项
this.append = function (element) {
var node = new Node(element);
var currentNode = tail;

// 判断是否为空链表
if (currentNode === null) {
// 空链表
tail = node;
} else {
currentNode.next = node;
node.prev = currentNode;
tail = node;
}

length++;
};

// 向链表特定位置插入一个新的项
this.insert = function (position, element) {
if (position < 0 && position > length) {
// 越界
return false;
} else {
var node = new Node(element);
var index = 0;
var previousNode;

if (position === 0) {
tail = node;
} else {
node.next = currentNode;
currentNode.prev = node;
}
} else if (position === length) {
this.append(element);
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}

previousNode.next = node;
node.next = currentNode;

node.prev = previousNode;
currentNode.prev = node;
}

length++;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var index = 0;
var previousNode;

if (position === 0) {
// 移除第一项
if (length === 1) {
tail = null;
} else {
}
} else if (position === length - 1) {
// 移除最后一项
if (length === 1) {
tail = null;
} else {
currentNode = tail;
tail = currentNode.prev;
tail.next = null;
}
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
previousNode = currentNode.next.prev;
}

length--;

return true;
}
};

// 从链表中移除指定项
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
};

// 返回元素在链表的索引，如果链表中没有该元素则返回-1
this.indexOf = function (element) {
var index = 0;

while (currentNode) {
if (currentNode.element === element) {
return index;
}

index++;
currentNode = currentNode.next;
}

return -1;
};

// 如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
this.isEmpty = function () {
return length == 0;
};

// 返回链表包含的元素个数，与数组的length属性类似
this.size = function () {
return length;
};

// 获取链表头部元素
};

// 由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
this.toString = function () {
var string = '';

while (currentNode) {

string += ',' + currentNode.element;
currentNode = currentNode.next;
}

return string.slice(1);
};

this.print = function () {
console.log(this.toString());
};

```// 创建双向链表

## 三、结束

0 条评论

• ### JavaScript数据结构01 - 数组

PS：原始值是指固定而简单的值，存放在栈中的简单数据段，它们的值直接存储在变量访问的位置。

• ### JavaScript设计模式第3篇：抽象工厂模式

接着上一篇《JavaScript设计模式第2篇：工厂模式》，今天我们来看工厂模式的最后一种：抽象工厂。

• ### 尾调用和尾递归

尾调用是函数式编程中一个很重要的概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用。

• ### 嵌套数组的合并，扁平化数组

对于 [ [], [], [], ...] 数组里嵌套数组，有个需求：将里面的数组元素都放到外层数组，变成 , , , ...

• ### 漏洞告诉你：商家为什么都乐于提供免（diao）费（yu）WiFi？

作为一名小微商户，每天我除了要为经营小店忙得焦头烂额，还要想方设法地寻求提升用户体验。于是，我用了号称“营销神器”的某商用WiFi系统...... 然后不可...

• ### VR/AR/MR/XR 几种虚拟现实技术的区别

新兴技术发展越来越快，虚拟现实（VR）、增强现实（AR）、混合现实（MR）和扩展现实（XR）也不例外。这些缩略词有什么含义吗？以上几种用到了类似的技术。如，3D...

• ### 边玩游戏边学Python，原来编程如此有趣！

今年4月底，国内某知名招聘网站以4000万中高端人才为样本，时间跨度以2018年第一季度为主，发布了《2018第一季度中高端人才薪酬与流动大数据报告》（以下简称...

• ### 当初我要是这么学习操作系统就好了（附带思维导图）

现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成。

• ### 写给大忙人看的操作系统

现代计算机系统由一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成。