一、什么是链表
链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。可以参考火车,由一节一节车厢链接起来。 相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表是需要额外注意。在数组中我们可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,则需要从起点(表头)开始迭代链表直到找到所需的元素。
二、创建链表
- 1、LinkedList类的骨架
import { defaultEquals } from '../util'; // 判断两个元素是否相等
import { Node } from '../util'; // 创建元素节点
class LinkedList {
// 可以自定义传入比较元素相等的方法,如果没有使用defaultEquals
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表数量
this.head = undefined; // 第一个元素
his.equalsFn = equalsFn; // 判断两个元素是否相等
}
push(element) {} // 向链表尾部添加一个新元素
insert(element,position) {} // 向链表特定位置插入一个新元素
getElementAt(index) {} // 返回链表特定位置的元素
remove(element) {} // 从链表中移除一个元素
indexOf() {} // 返回元素在链表中的索引,没有则返回-1
removeAt(position) {} // 从链表特定位置移除一个元素
isEmpty() {} // 判断链表是否为空
size() {} // 返回链表包含的元素个数
toString() {} // 返回整个链表的字符串
}
- 2、defaultEquals和Node
export function defaultEquals(a, b) {
return a === b
}
export class Node {
constructor(element) {
this.element = element;
this.next = undefined;
}
}
三、实现链表的每一个方法
- 1、push尾部添加元素
push(element) {
const node = new Node(element);
let current;
// 头部为空
if (this.head == null) {
this.head = node;
// 头部不为空
} else {
current = this.head; // 当前元素
while(current.next != null) { // 获取最后一项
current = current.next;
}
// 将next赋值为新元素,建立链接
current.next = node;
}
this.count ++;
}
- 2、insert任意处添加元素
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
if (index === 0) { // 在第一个位置添加
const current = this.head;
node.next = current;
this.head = node;
} else {
const previous = this.getElementAt(index - 1);
const current = previous.next;
node.next = current;
previous.next = node;
}
this.count ++;
return true;
}
return false;
}
- 3、getElementAt查找元素位置
getElementAt(index) {
if (index >= 0 && index < this.count) {
let node = this.head;
for (let i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
return undefined;
}
- 4、removeAt从指定位置移除元素
// 从链表中移除元素,并返回移除项
removeAt(index) {
// 检查越界值
if (index >= 0 && index < this.count) {
let current = this.head;
// 移除第一项
if (index === 0) {
this.head = current.next;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
- 5、indexOf
// 查找元素位置
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.count && current != null; i++) {
if (this.equalsFn(element, current.element)) {
return i;
}
current = current.next;
}
return -1;
}
- 6、remove删除指定元素
// 从链表中移除元素
remove(element) {
const index = this.getElementAt(element);
return this.removeAt(index);
}
- 7、isEmpty判断链表是否为空
isEmpty() {
return this.size() === 0;
}
- 8、toString 将链表转化为字符串
toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current != null; i ++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
- 9、size返回链表长度
size() {
return this.count;
}
const list = new LinkedList();
list.push(12);
list.push(11);
list.push(13);
list.push(14);
list.insert(3, 3);
list.removeAt(2);
console.log(list);
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!