Skip to main content

链表的定义及实现(ing)

一、 链表的定义

1、什么是链表

链表是由一组元素组成的集合,每个元素都使用一个对象的引用指向它的后继,其中指向另一个元素的引用叫做链。

2、链表的组成

链表每个元素(即节点)包含:

  • 存储的数据(任何有效数据类型)
  • 指向下一个节点的链

链表最前面有一个头节点,链表的尾元素指向一个 null 节点。

3、链表与数组的区别

JS 中数组被实现成了对象,且元素存储在特定的位置中,效率较低;而链表中的元素在内存中不是连续放置的,每个与元素由一个存储自身的节点和一个指向下一个元素的引用组成。因此,与数组相比,链表的一个好处在于添加或移除元素时不需要移动其他元素;然而链表需要使用指针,不像数组可以直接访问任何位置的元素,如果想访问链表中间的一个元素,需要从表头开始迭代链表直到找到所需的元素。

二、链表的创建

要实现链表数据结构,关键在于保存 head 元素(即链表的头元素)以及每一个元素的 next 指针,有这两部分就可以很方便地遍历链表从而操作所有的元素。可以把链表想象成一条锁链,锁链中的每一个节点都是相互连接的,只要找到锁链的头,整条锁链就都可以找到了。

首先我们需要一个辅助类,用来描述链表中的节点。这个类很简单,只需要两个属性,一个用来保存节点的值,一个用来保存指向下一个节点的指针:

let Node = function (element) {
this.element = element;
this.next = null;
};

下面是链表的实现:

class LinkedList {
constructor() {
this.head = new Node("head");
}

// 查找给定的节点
find(item) {
var currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}

// 查找给定的节点前面的节点
findPrevious(item) {
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element !== item)) {
currNode = currNode.next;
}
return currNode;
}

// 在链表的指定节点插入节点
insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item)
newNode.next = current.next;
current.next = newNode;
}

// 删除链表中的指定节点
remove(item) {
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}

// 显示链表中的元素
display() {
var currNode = this.head;
while (!(currNode.next == null)) {
console.log(currNode.next.element)
currNode = currNode.next;
}
}
}

https://vue3js.cn/interview/algorithm/structure.html#%E4%B8%80%E3%80%81%E6%98%AF%E4%BB%80%E4%B9%88

JS 数据结构与算法书

https://mind.ricky.moe/algorithm/algorithm-and-data-structure/ji-chu-zhi-shi/daobiao-shi-fa