javascript 数据结构系列 (一) 单向链表
文章目录
Singly linked list
本章主要介绍单向链表,具体讲解实现之前,首先说一下,单向链表实现相关列 node 具体结构技术实现
node 包含下一个节点与上一个节点引用,代码实现如下:
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}其次,看一下Singly linked list 类实现过程
构造函数
constructor() {
this.first = null; // head/root element
}addLast 添加元素到链表末端
addLast(value) {
const node = new Node(value);
if (this.first) {
let currentNode = this.first;
while (currentNode && currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
} else {
this.first = node;
}
}removeLast 移除最后一个元素
removeLast() {
let current = this.first;
let target;
if (current && current.next) {
while (current && current.next && current.next.next) {
current = current.next;
}
target = current.next;
current.next = null;
} else {
this.first = null;
target = current;
}
if (target) {
return target.value;
}
}addFirst 添加第一个元素
addFirst(value) {
const node = new Node(value);
node.next = this.first;
this.first = node;
}removeFist 移除第一个元素
removeFirst() {
const first = this.first;
if (first) {
this.first = first.next;
return first.value;
}
}contains 查找链表中包含的元素,并且返回该元素位置
contains(value) {
for (let current = this.first, index = 0; current; index++, current = current.next) {
if (current.value === value) {
return index;
}
}
}removeAt 删除指定位置元素
removeAt(nth) {
if (nth === 0) {
return this.removeFirst();
}
for (let current = this.first, index = 0; current; index++, current = current.next) {
if (index === nth) {
if (!current.next) { // if it doesn't have next it means that it is the last
return this.removeLast();
}
current.previous = current.next;
return current.value;
}
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论