Appearance
链表
查看js的单向链表结构
js
// 单向链表节点类
Class Node() {
constructor(val) {
this.val = val;
this.next = null
}
}
// 单向链表类
Class ListNode() {
constructor() {
this.head = null;
this.tail = null;
}
}查看js的双向链表结构
js
Class Node() {
constructor(val) {
this.prev = null;
this.val = val;
this.next = null;
}
}
Class DoubleNode() {
constructor() {
this.head = null;
this.tail = null;
}
// 末尾添加元素
add(item) {
let node = new Node(item);
if (!head) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
}
// 在某个位置添加元素
addAt(index, item) {
let cur = this.head;
let node = new Node(item);
// 如果在头部插入
if(index === 0) {
node.next = cur;
cur.prev = node;
this.head = node;
} else {
// 从第一个元素开始加
let counter = 1;
while(cur) {
cur = cur.next;
if (index === counter) {
node.prev = cur.prev;
node.next = cur;
cur.prev.next = node;
cur.prev = node;
}
counter++;
}
}
}
// 删除一个元素
remove(item) {
let cur = this.head
while(cur) {
// 找到了目标节点
if(cur === item) {
// 只有一个元素
if (cur === this.head && cur === this.tail) {
this.head = null
this.tail = null
// 目标为链头
} else if (cur === this.head) {
this.head = this.head.next
this.head.prev = null
} else if (cur === this.tail) {
this.tail = this.tail.prev
this.tail.next = null
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
cur = cur.next
}
}
// 在某个位置中删除元素
removeAt(index) {
let cur = this.head
let counter = 1;
// 删除链头
if (index === 0) {
this.head = this.head.next
this.head.prev = null
} else {
while(cur) {
cur = cur.next
if(index === counter) {
// 如果在链尾
if(cur === this.tail) {
this.tail = this.tail.prev
this.tail.next = null
} else {
cur.prev.next = cur.next
cur.next.prev = cur.prev
break;
}
}
counter++
}
}
}
// 翻转链表
reverse() {
let cur = this.head
let prev = null
while(cur) {
let next = cur.next
// 交换指针
cur.next = prev
cur.prev = next
// 向后移动
prev = cur
cur = next
}
// 当前末尾是prev
this.tail = this.head
this.head = prev
}
// 交换两个链表元素的位置
swap(index1, index2) {
if (index1 > index2) return swap(index2, index1)
let cur = this.head
let counter = 0;
let firstNode
while (cur!== null) {
// 找到第一个
if(counter === index1) {
firstNode = cur
// 找到第二个
} else (counter === index2) {
let temp = firstNode.val
firstNode.val = cur.val
cur.val = temp
}
cur = cur.next
counter++
}
return true
}
// 判断是否为空
isEmpty() {
return this.length() < 1;
}
// 查询链表长度
length() {
let cur = this.head;
let counter = 0;
while(cur !== null) {
counter++;
cur = cur.next;
}
return counter;
}
// 遍历链表
traverse(fn) {
let cur = this.head
while(cur !== null) {
fn(cur)
cur = cur.next
}
return true
}
// 找到某个节点的索引
find(item) {
let cur = this.head
let counter = 0
while(cur !== null) {
if（cur.val === item) {
return counter
}
cur = cur.next
counter++
}
return false;
}
}