JavaScript实现链表、双向链表、循环链表

写在之前

• JavaScript在实现链表时，每一个结点都是一个对象，因为每一个对象都储存在堆内存的独立空间中，也就实现了链表的物理上不连续。

链表JS代码实现

在使用构造函数内部的方法时，要加上this。

function Node(element)  //生成新结点的构造函数
{
   
    this.val = element;  //数据域
    this.next = null;  //指向下一个结点
}

function Linkedlist() //链表的构造函数
{
   
    this.head = new Node("head");  //每一个链表都存在头结点
    this.find = function(target)  //找到数据域为target的结点
    {
   
        let curNode = this.head;  //从头结点开始遍历（单链表找目标结点只能从头结点开始遍历）
        while(curNode.val !== target && curNode.next !== null)
        {
   
            curNode = curNode.next;
        }
        return curNode;
    }
    this.insert = function(val,target)  //在数据域为target的结点之后插入数据域为val的结点
    {
   
        let newNode = new Node(val);  //生成一个数据域是val的新结点
        let prev = this.find(target);
        newNode.next = prev.next;
        prev.next = newNode;
    }
    this.findPrevNode = function(target)  //找到数据域为target结点的上一个结点
    {
   
        let curNode = this.head;  //从头结点开始遍历，找到目标结点的上一个结点
        while(curNode.next.val !== target && curNode.next !== null)
        {
   
            curNode = curNode.next;
        }
        return curNode;
    }
    this.remove = function(target)  //删除数据域为target的结点
    {
   
        let prev = this.findPrevNode(target);
        if(prev.next.next !== null)  //当待删除结点的下一个结点不是null
        {
   
            prev.next = prev.next.next;  //使待删除结点的前驱结点的指针指向待删除结点的后继结点
        }
        else{
   
        	prev.next = null;
        }
    }
    this.print = function()  //遍历链表
    {
   
        let curNode = this.head;
        while(curNode.next !== null)  //当curNode的下一个结点不是null
        {
   
            console.log(curNode.next.val);  //打印curNode的下一个结点的数据域
            curNode = curNode.next;  //使curNode指向下一个结点
        }
    }
}

双向链表JS实现

在使用构造函数内部的方法时，要加上this。

function Node(val)
{
   
    this.val = val;
    this.next = null;
    this.prev = null;
}

function List()
{
   
    this.head = new Node("head");
    this.find = function(target)
    {
   
        let curNode = this.head;
        while(curNode.next !== null && curNode.val !== target)
        {
   
            curNode = curNode.next;
        }
        return curNode;
    }
    this.insert = function(target,val)
    {
   
        let newNode = new Node(val);
        let curNode = this.find(target);  //坑点:在使用构造函数内部的方法时，要加上this
        if(curNode.next !== null)
        {
   
            newNode.next = curNode.next;
            curNode.next = newNode;
            newNode.next.prev = newNode;
            newNode.prev = curNode;
        }
        else{
   
            newNode.next = curNode.next;
            curNode.next = newNode;
            newNode.prev = curNode;
        }
    }
    this.findPrevNode = function(target)
    {
   
        let curNode = this.find(target);
        return curNode.prev;
    }
    this.remove = function(target)
    {
   
        let prevNode = this.findPrevNode(target);
        if(prevNode.next.next !== null)
        {
   
            prevNode.next = prevNode.next.next;
        }
        else{
   
            prevNode.next = null;
        }
    }
    this.print = function()
    {
   
        let curNode = this.head;
        while(curNode.next !== null)
        {
   
            console.log(curNode.next.val);
            curNode = curNode.next;
        }
    }
}

循环链表JS实现

function Node(val)
{
   
    this.val = val;
    this.next = null;
    this.prev = null;
}

function Cyclelist()
{
   
    this.head = new Node("head");
    this.find = function(target)
    {
   
        let curNode = this.head;
        while(curNode.next !== null && curNode.val !== target && curNode.next !== this.head)
        {
   
            curNode = curNode.next;
        }
        return curNode;
    }
    this.insert = function(target,val)
    {
   
        let newNode = new Node(val);
        let curNode = this.find(target);
        if(curNode.next === null)
        {
   
	       curNode.next = newNode;
	       newNode.prev = curNode;
	       newNode.next = this.head;
        }
        else
        {
   
        	newNode.next = curNode.next;
        	curNode.next = newNode;
        	newNode.prev = curNode;
        	newNode.next.prev = newNode;
        }
    }
    this.findPrevNode = function(target)
    {
   
        let curNode = this.find(target);
        let prevNode = curNode.prev;
        return prevNode;
    }
    this.remove = function(target)
    {
   
        let prevNode = this.findPrevNode(target);
        prevNode.next = prevNode.next.next;
        prevNode.next.prev = prevNode;
    }
    this.print = function()
    {
   
        let curNode = this.head;
        while(curNode.next !== this.head && curNode.next !== null)
        {
   
            console.log(curNode.val);
            curNode = curNode.next;
        }
        console.log(curNode.val);
    }
}