链表:
javaScript中通过对象来表示节点,通过节点属性的调用来实现链表
//单个节点
function Node(el) {
this.el = el;
this.next = null;
}
function List() { //创建链表,并初始化头节点
this.head = new Node("head");
this.find = find;
this.findPre = findPre;
this.insert = insert;
this._delete = _delete;
this.display = display;
}
//查找节点,从头节点开始查找
function find(el) {
var currentNode = this.head;
// console.log(currentNode);
while (currentNode.el != el&¤tNode!==null) {
currentNode = currentNode.next;
}
return currentNode;
}
//查找前驱节点
function findPre(el) {
var currentNode = this.head;
// console.log(currentNode);
while (currentNode.next.el != el && currentNode.next.next!== null) { //当下一个节点的下一个节点为空时,终止循环
currentNode = currentNode.next;
}
return currentNode;
}
//插入节点
//参数:插入节点,要插入在哪个节点
function insert(el,item) {
var newNode = new Node(el);
var currentNode = this.find(item);
if (currentNode) {
newNode.next = currentNode.next;
currentNode.next = newNode;
}
}
//删除节点,从指定节点前驱节点进行删除
function _delete (item){
var preNode = this.findPre(item);
preNode.next = preNode.next.next;
preNode.next = null; //释放删除节点的内存
}
//遍历,从头节点开始遍历
function display() {
let p = this.head;
while (p.next!==null) {
console.log(p.next.el);
p = p.next;
}
}
let list = new List();
list.insert('jeff', 'head');
list.insert('tom', 'jeff');
list.insert('jim', 'tom');
list.display();
list._delete('jims');
list.display();