链表是什么?
链表（Linked-List）是由一组不必相连的节点，按照一定的顺序链接在一起的抽象数据模型
增删查操作，相对于数组来说，速度快很多
有单链表，双链表，循环链表三种
下面，就来实现一个单链表
[ head | next ] --> [ data1 | next ] --> [ data2 | next ] --> null
先定义节点属性
function Node(val) {
this.val = val;
this.next = null;
}
function Lnode() {
this.head = new Node(null)
this.find = find
this.insert = insert
this.remove = remove
this.findPrev = findPrev
this.display = display
}
查找一个节点
function find(val) {
const current = this.head
while (current.val !== val) {
current = current.next
}
return current
}
插入一个节点
function insert(newEle, val) {
const newNode = new Node(newEle)
const currNode = this.find(val)
newNode.next = currNode.next
currNode.next = newNode
}
删除一个节点
function remove(val) {
const currNode = this.find(val)
const prevNode = this.findPrev(val)
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next
current.next = null
}
}
查找前一个节点
function findPrev(val) { // 一个链表里面有相同的元素，这个方法找到的永远是第一个这个元素的前一个节点
const currNode = this.head
while (headNode.next !== null && currNode.next.val !== val) {
headNode = headNode.next
}
return headNode
}
展示该链表上所有节点
function display() {
const headNode = this.head
while (headNode.next !== null) {
console.log(headNode.val)
headNode = headNode.next
}
}
