数据结构与算法（js描述）-- 单链表
单链表
什么是单链表？
单链表是线性表中的链式存储结构，顾名思义，就是在内存中申请一小块地址空间的结点，该结点存放数据和指针，然后通过指针将这些结点连接成一条链，我们称之为单链表。
优点：便于插入和删除，插入和删除的时间复杂度均为O(1) 缺点：不便于查找，查找时只能遍历单链表，不能随机存取，而且由于存储指针导致内存密度<1
结点结构
// 定义node结点
class LNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
单链表结构及其操作
// 定义单链表结构
class LinkList {
constructor(){
this.data = null;
this.next = null;
}
// 初始化单链表
InitList_L() {
this.next = null;
}
// 获取单链表的长度
GetListLength() {
let cur = this;
let count = 0;
while (cur.next !== null) {
++count;
cur = cur.next;
}
return count;
}
// 建立带表头结点的单链表L(头插法)
CreateList_L (arr) {
for(let i = 0; i < arr.length; i++) {
let p = new LNode(arr[i]);
p.next = this.next;
this.next = p;
}
return this;
}
// 在不带头结点的单链表中第pos个位置之前插入元素elem
ListInsert_L (pos,elem) {
let count = 0;
let pre = this;
// 遍历查找第pos-1个结点
while (pre.next !== null && count < (pos - 1)) {
++count;
pre = pre.next;
}
if(pre === null || count > (pos - 1)) return ERROR;
// 创建新结点
const p = new LNode(elem);
p.next = pre.next;
pre.next = p;
return OK;
}
// 在不带头结点的单链表中，删除第pos个元素
ListDelete_L (pos) {
let pre = this;
let count = 0;
while (pre !== null && count < (pos - 1)) {
++count;
pre = pre.next;
}
if(pre === null || count > (pos - 1)) return ERROR;
pre.next = p.next;
return OK;
}
// 归并单链表La，Lb
MergeList_L (La,Lb) {
// 已知单链表La和Lb的元素按值非递减排列
let pa = La.next;
let pb = Lb.next;
let Lc = new LinkList();
let pc = Lc.next;
while (pa !== null && pb !== null) {
if(pa.data <= pb.data) {
pc.next = pa;
pc = pa;
pa = pa.next;
} else {
pc.next = pb;
pc = pb;
pb = pb.next;
}
}
pc.next = pa !== null ? pa : pb;
return Lc;
}
}
简单测试
let testArr = [JAMES,kOBE,Durant,Paul];
// 创建单链表
const testList = new LinkList();
testList.CreateList_L(testArr);
// 遍历单链表
let p = testList;
while (p.next !== null) {
p = p.next;
console.log(p.data);
}
console.log(JSON.stringify(testList));
