数据结构:JavaScript实现链表

冷不防 2022-08-20 04:23 191阅读 0赞

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

数组元素靠他们的位置进行引用，链表元素则是靠互相之间的关系进行引用。

## 一.一个基本的链表 ##

一下是一个基于对象的链表的代码以及解释

//Node类包含两个属性，element用来保存节点上的数据，next用来保存指向下一个节点的链接
    function Node(element){
    	this.element = element;
    	this.next = null;
    }
    //LList类提供了对链表进行操作的方法
    function LList(){
    	//head节点的next属性被初始化为null，当有新元素插入时，next会指向新的元素，所以这里我们没有修改next的值
    	this.head = new Node("head");
    	this.find = find;
    	this.insert = insert;
    	this.findPrevious = findPrevious;
    	this.remove = remove;
    	this.display = display;
    }
    
    //想要插入节点，就首先要找到在哪个节点后面进行插入的操作，这里我们写一个find()函数来实现这一功能
    function find(item){
    	var currNode = this.head;
    	while(currNode.element != item){
    		currNode = currNode.next;
    	}
    	return currNode;
    }
    //找到之后就可以进行插入操作了，首先，将新节点的next属性设置为找到的节点的next属性对应的值，然后设置找到的节点的next属性指向新节点
    function insert(newElement, item){
    	var newNode = new Node(newElement);
    	var currNode = this.find(item);
    	newNode.next = currNode.next;
    	currNode.next = newNode;
    }
    //写一个函数来打印链表中的元素
    function display(){
    	var currNode = this.head;
    	while(currNode.next != null){
    		console.log(currNode.next.element);
    		currNode = currNode.next;
    	}
    }
    
    //同样的，当我们想要删除一个节点时，需要先找到想要删除元素的前一个节点，然后修改该节点的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点
    //这里我们写了一个findPrevious函数来做这件事
    function findPrevious(item){
    	var currNode = this.head;
    	while((currNode.next != null) && (currNode.next.element != item)){
    		currNode = currNode.next;
    	}
    	return currNode;
    }
    //下面开始写remove函数
    function remove(item){
    	var prevNode = this.findPrevious(item);
    	if(prevNode != null){
    		//让前一个节点直接指向待删除节点的后一个节点
    		prevNode.next = prevNode.next.next;
    	}
    }

测试一下

//测试一下！
    var colors = new LList();
    colors.insert("white", "head");
    colors.insert("red", "white");
    colors.insert("yellow", "red");
    colors.display();
    console.log("增加节点后，链表变为：")
    colors.insert("black", "white");
    colors.display();
    colors.remove("red");
    console.log("删除节点后，链表变为：");
    colors.display();

运行结果如下

![Center][]

## 二.双向链表 ##

双向链表在基础的链表中增加了一个前驱属性

代码如下

//首要的区别在于，Node类中增加了一个previous属性
    function Node(element){
    	this.element = element;
    	this.next = null;
    	this.previous = null;
    }
    function LList(){
    	this.head = new Node("head");
    	this.find = find;
    	this.insert = insert;
    	this.display = display;
    	this.remove = remove;
    	this.findLast = findLast;
    	this.dispReverse = dispReverse;
    }
    function find(item){
    	var currNode = this.head;
    	while(currNode.element != item){
    		currNode = currNode.next;
    	}
    	return currNode;
    }
    function insert(newElement, item){
    	var newNode = new Node(newElement);
    	var current = this.find(item);
    	newNode.next = current.next;
    	newNode.previous = current;
    	if(current.next != null){
    		current.next.previous = newNode;
    	}
    	current.next = newNode;
    }
    function remove(item){
    	var currNode = this.find(item);
    	if(currNode.next != null){
        	currNode.next.previous = currNode.previous;
    	}
    	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;
    }
    //反序显示列表中的元素
    function dispReverse(){
    	var currNode = this.findLast();
    	while(currNode.previous != null){
    		console.log(currNode.element);
    		currNode = currNode.previous;
    	}
    }
    function display(){
    	var currNode = this.head;
    	while(currNode.next != null){
    		console.log(currNode.next.element);
    		currNode = currNode.next;
    	}
    }

测试一下

//测试一下!
    var colors = new LList();
    colors.insert("white", "head");
    colors.insert("red", "white");
    colors.insert("yellow", "red");
    colors.display();
    console.log("增加节点后，链表变为：");
    colors.insert("black", "white");
    colors.display();
    colors.remove("yellow");
    console.log("删除节点后，链表变为：");
    colors.display();
    console.log("反向显示链表：");
    colors.dispReverse();

![Center 1][]

## 三.循环链表 ##

循环链表和单向链表类似，区别在于，在在创建循环链表时，让其头结点的next属性指向他本身，这样，链表的尾节点指向头结点，形成了一个循环链表。

创建循环链表，只需要修改LList类的构造函数并且对display函数稍加修改即可

//Node类包含两个属性，element用来保存节点上的数据，next用来保存指向下一个节点的链接
    function Node(element){
    	this.element = element;
    	this.next = null;
    }
    //LList类提供了对链表进行操作的方法
    function LList(){
    	this.head = new Node("head");
    	//修改此处，变为循环链表
    	this.head.next = this.head;
    	this.find = find;
    	this.insert = insert;
    	this.findPrevious = findPrevious;
    	this.remove = remove;
    	this.display = display;
    }
    
    //想要插入节点，就首先要找到在哪个节点后面进行插入的操作，这里我们写一个find()函数来实现这一功能
    function find(item){
    	var currNode = this.head;
    	while(currNode.element != item){
    		currNode = currNode.next;
    	}
    	return currNode;
    }
    //找到之后就可以进行插入操作了，首先，将新节点的next属性设置为找到的节点的next属性对应的值，然后设置找到的节点的next属性指向新节点
    function insert(newElement, item){
    	var newNode = new Node(newElement);
    	var currNode = this.find(item);
    	newNode.next = currNode.next;
    	currNode.next = newNode;
    }
    //原来的方式会出现死循环，我们把display函数稍作修改
    function display(){
    	var currNode = this.head;
    	while((currNode.next != null) && (currNode.next.element != "head")){
    		console.log(currNode.next.element);
    		currNode = currNode.next;
    	}
    }
    
    //同样的，当我们想要删除一个节点时，需要先找到想要删除元素的前一个节点，然后修改该节点的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点
    //这里我们写了一个findPrevious函数来做这件事
    function findPrevious(item){
    	var currNode = this.head;
    	while((currNode.next != null) && (currNode.next.element != item)){
    		currNode = currNode.next;
    	}
    	return currNode;
    }
    //下面开始写remove函数
    function remove(item){
    	var prevNode = this.findPrevious(item);
    	if(prevNode != null){
    		//让前一个节点直接指向待删除节点的后一个节点
    		prevNode.next = prevNode.next.next;
    	}
    }
    
    //测试一下！
    var colors = new LList();
    colors.insert("white", "head");
    colors.insert("red", "white");
    colors.insert("yellow", "red");
    colors.display();
    console.log("增加节点后，链表变为：")
    colors.insert("black", "white");
    colors.display();
    colors.remove("yellow");
    console.log("删除节点后，链表变为：");
    colors.display();

运行结果

![Center 2][]

[Center]: /images/20220731/30a06ae09e0b4678adf4b2c7ec290192.png
[Center 1]: /images/20220731/6f7488071ed54453b4b8d31a4bebecbd.png
[Center 2]: /images/20220731/f07fa4a26ff24b6db8a83a068326c9ab.png