相较于之前学习的 栈/队列 只关心 栈顶/首尾 的模式,链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同
下面是单链表的基本结构
类比:寻宝游戏,你有一条线索,这条线索是指向寻找下一条线索的地点的指针。你顺着这条链接去下一个地点,得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法,就是从起点(第一条线索)顺着列表寻找
链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类
// 节点基类
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
一般单链表有以下几种方法:
// 初始化链表
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
// 方法...
}
下面我们来实现几个重要的方法
在链表尾部添加一个新的元素可分为两种情况:
代码实现
// 在链表尾端添加元素
append(data) {
const newNode = new Node(data);
if (this._length === 0) {
this._head = newNode;
this._tail = newNode;
} else {
this._tail.next = newNode;
this._tail = newNode;
}
this._length += 1;
return true;
}
为方便验证,我们先实现print方法。方法虽简单,这里却涉及到链表遍历精髓
// 打印链表
print() {
let ret = [];
// 遍历需从链表头部开始
let currNode = this._head;
// 单链表最终指向null,作为结束标志
while (currNode) {
ret.push(currNode.data);
// 轮询至下一节点
currNode = currNode.next;
}
console.log(ret.join(' --> '));
}
// 验证
const link = new LinkedList();
link.append(1);
link.append(2);
link.append(3);
link.print(); // 1 --> 2 --> 3
获取指定索引位置的节点,依次遍历链表,直到指定位置返回
// 获取指定位置元素
getNode(index) {
let currNode = this._head;
let currIndex = 0;
while (currIndex < index) {
currIndex += 1;
currNode = currNode.next;
}
return currNode;
}
// 验证【衔接上面的链表实例】
console.log(link.getNode(0));
// Node { data: 1, next: Node { data: 2, next: Node { data: 3, next: null } } }
console.log(link.getNode(3)); // null
插入元素,需要考虑三种情况
代码实现
// 在链表指定位置插入元素
insert(index, data) {
// 不满足条件的索引值
if (index < 0 || index > this._length) return false;
// 插入尾部
if (index === this._length) return this.append(data);
const insertNode = new Node(data);
if (index === 0) {
// 插入首部
insertNode.next = this._head;
this._head = insertNode;
} else {
// 找到原有位置节点
const prevTargetNode = this.getNode(index - 1);
const targetNode = prevTargetNode.next;
// 重塑节点连接
prevTargetNode.next = insertNode;
insertNode.next = targetNode;
}
this._length += 1;
return true;
}
// 验证
link.insert(0, 0);
link.insert(4, 4);
link.insert(5, 5);
link.print(); // 0 --> 1 --> 2 --> 3 --> 4 --> 5
在指定位置删除元素同添加元素类似
代码实现
// 在链表指定位置移除元素
removeAt(index) {
if (index < 0 || index >= this._length) return false;
if (index === 0) {
this._head = this._head.next;
} else {
const prevNode = this.getNode(index - 1);
const delNode = prevNode.next;
const nextNode = delNode.next;
// 若移除为最后一个元素
if (!nextNode) this._tail = prevNode;
prevNode.next = nextNode;
}
this._length -= 1;
return true;
}
// 验证
link.removeAt(3);
link.print(); // 0 --> 1 --> 2 --> 4 --> 5
完整的链表代码,可点此获取
// 判断数据是否存在于链表内,存在返回index,否则返回-1
indexOf(data) {
let currNode = this._head;
let index = 0;
while (currNode) {
if (currNode.data === data) return index;
index += 1;
currNode = currNode.next;
}
return -1;
}
getHead() {
return this._head;
}
getTail() {
return this._tail;
}
size() {
return this._length;
}
isEmpty() {
return !this._length;
}
clear() {
this._head = null;
this._tail = null;
this._length = 0;
}
基于链表实现栈
class Stack {
constructor() {
this._link = new LinkedList();
}
push(item) {
this._link.append(item);
}
pop() {
const tailIndex = this._link - 1;
return this._link.removeAt(tailIndex);
}
peek() {
if (this._link.size() === 0) return undefined;
return this._link.getTail().data;
}
size() {
return this._link.size();
}
isEmpty() {
return this._link.isEmpty();
}
clear() {
this._link.clear()
}
}
基于链表实现队列
class Queue {
constructor() {
this._link = new LinkedList();
}
enqueue(item) {
this._link.append(item);
}
dequeue() {
return this._link.removeAt(0);
}
head() {
if (this._link.size() === 0) return undefined;
return this._link.getHead().data;
}
tail() {
if (this._link.size() === 0) return undefined;
return this._link.getTail().data;
}
size() {
return this._link.size();
}
isEmpty() {
return this._link.isEmpty();
}
clear() {
this._link.clear()
}
}
(1)迭代法
迭代法的核心就是currNode.next = prevNode,然后从头部一次向后轮询
代码实现
reverse() {
if (!this._head) return false;
let prevNode = null;
let currNode = this._head;
while (currNode) {
// 记录下一节点并重塑连接
const nextNode = currNode.next;
currNode.next = prevNode;
// 轮询至下一节点
prevNode = currNode;
currNode = nextNode;
}
// 交换首尾
let temp = this._tail;
this._tail = this._head;
this._head = temp;
return true;
}
(2)递归法
递归的本质就是执行到当前位置时,自己并不去解决,而是等下一阶段执行。直到递归终止条件,然后再依次向上执行
function _reverseByRecusive(node) {
if (!node) return null;
if (!node.next) return node; // 递归终止条件
var reversedHead = _reverseByRecusive(node.next);
node.next.next = node;
node.next = null;
return reversedHead;
};
_reverseByRecusive(this._head);
利用递归,反向输出
function _reversePrint(node){
if(!node) return;// 递归终止条件
_reversePrint(node.next);
console.log(node.data);
};
双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素,如下图
正是因为这种变化,使得链表相邻节点之间不仅只有单向关系,可以通过prev来访问当前节点的上一节点。相应的,双向循环链表的基类也有变化
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
继承单向链表后,最终的双向循环链表DoublyLinkedList如下【prev对应的更改为NEW】
class DoublyLinkedList extends LinkedList {
constructor() {
super();
}
append(data) {
const newNode = new DoublyNode(data);
if (this._length === 0) {
this._head = newNode;
this._tail = newNode;
} else {
newNode.prev = this._tail; // NEW
this._tail.next = newNode;
this._tail = newNode;
}
this._length += 1;
return true;
}
insert(index, data) {
if (index < 0 || index > this._length) return false;
if (index === this._length) return this.append(data);
const insertNode = new DoublyNode(data);
if (index === 0) {
insertNode.prev = null; // NEW
this._head.prev = insertNode; // NEW
insertNode.next = this._head;
this._head = insertNode;
} else {
// 找到原有位置节点
const prevTargetNode = this.getNode(index - 1);
const targetNode = prevTargetNode.next;
// 重塑节点连接
prevTargetNode.next = insertNode;
insertNode.next = targetNode;
insertNode.prev = prevTargetNode; // NEW
targetNode.prev = insertNode; // NEW
}
this._length += 1;
return true;
}
removeAt(index) {
if (index < 0 || index > this._length) return false;
let delNode;
if (index === 0) {
delNode = this._head;
this._head = this._head.next;
this._head.prev = null; // NEW
} else {
const prevNode = this.getNode(index - 1);
delNode = prevNode.next;
const nextNode = delNode.next;
// 若移除为最后一个元素
if (!nextNode) {
this._tail = prevNode;
this._tail.next = null; // NEW
} else {
prevNode.next = nextNode; // NEW
nextNode.prev = prevNode; // NEW
}
}
this._length -= 1;
return delNode.data;
}
}
循环链表可以像链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和链 表之间唯一的区别在于,单向循环链表最后一个节点指向下一个节点的指针tail.next不是引用null, 而是指向第一个节点head,双向循环链表的第一个节点指向上一节点的指针head.prev不是引用null,而是指向最后一个节点tail
链表的实现较于栈和队列的实现复杂许多,同样的,链表的功能更加强大
我们可以通过链表实现栈和队列,同样也可以通过链表来实现栈和队列的问题
链表更像是数组一样的基础数据结构,同时也避免了数组操作中删除或插入元素对其他元素的影响
据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。包括三个组成成分:数据的逻辑结构、物理结构(存储结构)、数据运算结构。
一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项
数组不总是组织数据的最佳数据结构,在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移。
图由边的集合及顶点的集合组成。边是有方向的是有序图(有向图),否则就是无序图(无向图)。图中的一系列顶点构成路径,路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。
Set 是ES6提供的一种新的数据结构,它允许你存储任何类型的唯一值,而且Set中的元素是唯一的。我们用new操作符来生成一个Set对象,set结构的实例有以下属性
集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:关于数的深度和高度的问题,不同的教材有不同的说法
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法,原理:就是把字符串变成数组
链表和数组的对比:在大多数语言中,数组的大小是固定的,从数组的起点或中间添加或删除元素的成本很高,因为需要移动元素,链表中的每一个元素在内存中不是连续放置的,和它左右两侧元素是没有关系的
什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!