javascript实现链表基本操作

一、定义

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一
个节点的引用叫做链。

二、操作

插入： 链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前
驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。
删除： 从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了。

三、模拟

我们用 object 来模拟一下链表

单链表

• 定义节点结构

// 定义每一个节点的结构
function Node(el) {
    this.el = el;
    this.next = null; // 后继节点
}

• 然后我们写个创建链表的方法

function List(){
    this.head = new Node('head');
}

• 插入节点
  • 插入节点之前我们要先找到节点，找到之后我们改变模拟指针的指向就能够实现元素的插入

// 找到插入位置，不存在返回null
function find(item){
    var currNode = this.head;
    while(currNode && currNode.el != item){
        currNode = currNode.next
    }
    return currNode
}
// 插入操作
function insert(newEl, item){
    var newNode = new Node(newEl);
    var currNode = this.find(item);
    // 找到要插入的前一个节点，如果存在，改变指针指向
    if(currNode){
        newNode.next = currNode.next; // 改变next指向
        // newNode.previous = currNode; // 改变previous指向
        currNode.next = newNode;
    }
}

• 模拟一个删除节点的方法
  • 删除节点不同于插入节点，我们不是要找到删除的节点的位置，而是要找到要删除的节点的前一个位置

// 找到所需删除节点的前一个位置
function findPrev(item){
    var prevNode = this.head;
    while(prevNode && prevNode.next.el !== item){
        prevNode = prevNode.next
    }
    return prevNode;
}
// 改变指针指向，移除节点
function remove(el){
    var prevNode = this.findPrev(el);
    var reNode;
    if(prevNode){
        reNode = prevNode.next;
        prevNode.next = prevNode.next.next;
    }
    return reNode;
}

• 再写一个展示当前链表结构的方法

// 展示链表
function display() {
    var currNode = this.head;
    var str = currNode.el + '->';
    while(!(currNode.next == null)){
        str += currNode.next.el + '->';
        currNode = currNode.next;
    }
    console.log(str.substring(0,str.length-2));
}

• 记得所有的方法都要在我们的链表上注册

// 链表
function List(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.findPrev = findPrev
    this.remove = remove;
    this.display = display;
}

• 测试一下当前写的方法是否有效

var list = new List();
list.insert('Mike', 'head');
list.insert('Sarah', 'Mike');
list.insert('Jhon', 'Sarah');
console.log('原链表结构：')
list.display();
list.remove('Sarah');
console.log('删除Sarah节点')
list.display();

• ！！！单链表反转
  • 小米一面的时候，面试官（好人）给了这么一道基础题，我却写不出来。现在用 js 来重现一下我的思路

// 寻找最后一个节点
function findLast(){
    var currNode = this.head;
    while(!(currNode.next === null)) {
        currNode = currNode.next;
    }
    return currNode;
}

// 单链表反转
function listReverse(){
    var firstEl = this.head.next.el;
    // 初始化数据
    var prevNode = this.head;
    var lastOne = this.findLast();
    var lastTwo = this.findPrev(lastOne.el);
    while(lastOne.el != firstEl){
        // 把原本倒数第二位的next和倒数第一位的next
        lastTwo.next = lastOne.next
        // 最后一位和插入位next指针改变
        lastOne.next = prevNode.next;
        prevNode.next = lastOne;
        // 刷新数据
        prevNode = lastOne;
        lastOne = this.findLast();
        lastTwo = this.findPrev(lastOne.el);
    }
}

• 测试

var list = new List();
list.insert('Mike', 'head');
list.insert('Sarah', 'Mike');
list.insert('Jhon', 'Sarah');
console.log('原链表结构：')
list.display();
list.listReverse();
console.log('反转列表输出：')
list.display();

双向链表

• 通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样删除节点就变容易了，但插入节点就要注意前驱指针的指向
• 新的节点结构

// 双向链表节点
function Node(el) {
    this.el = el;
    this.next = null; // 后继节点
    this.previous = null; // 前驱节点
}

• 新的插入节点的方法

// 插入操作
function insert(newEl, item){
    var newNode = new Node(newEl);
    var currNode = this.find(item);
    // 找到要插入的前一个节点，如果存在，改变指针指向
    if(currNode){
        newNode.next = currNode.next; // 改变next指向
        newNode.previous = currNode;    // 改变previous指向
        currNode.next = newNode;
    }
}

• 新的删除方法（不需要去找前一个节点）

function remove(item){
    var currNode = this.find(item);;
    if(!(currNode.next === null)) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous; // 改变前后指针方向
        currNode.next = null;
        currNode.previous = null; // 释放
    }
}

• 再写一个双链表反序输出的方法

// 找到最后一个元素
function findLast(){
    var currNode = this.head;
    while(!(currNode.next === null)) {
        currNode = currNode.next;
    }
    return currNode;
}
// 利用前驱节点直至head
function dispReverse() {
    var currNode = this.findLast();
    var str = currNode.el + '->';
    while(!(currNode.previous == null)){
        currNode = currNode.previous;
        str += currNode.el + '->';
    }
    console.log(str.substring(0, str.length-2));
}

• 注册方法

function List(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.findLast = findLast;
    this.dispReverse = dispReverse;
    this.display = display;
}

• 测试一下所有方法

var list = new List();
list.insert('Mike', 'head');
list.insert('Sarah', 'Mike');
list.insert('Jhon', 'Sarah');
console.log('原链表结构：');
list.display();
console.log('反序输出')
list.dbReverse();
console.log('反转列表输出：');
list.dbReverse();
list.display();
console.log('删除节点Sarah：')
list.remove('Sarah');
list.display();

循环列表

• 循环链表即最后一个节点指向 head 的链表结构，可以在初始化的时候把 head 的 next 指向自身就行了，这里就不再做演示了。

这样就很粗浅的复习了一下链表的知识 ，做个记录