阅读 349

JS数据结构之单链表

前言

在我们平时的工作中,可能很少用到链表,但作为一个有追求的前端工程师还是有必要学习下常见的数据结构的。

代码实现

我们先来创建一个Node类

class Node {
    constructor(element) {
    	this.element = element;
    	this.next = undefined;
    }
}
复制代码

Node类表示一个链表中的结点,element表示结点,next指向他的下一个结点(null表示是最后一个结点)

接下来我们实现以下LinkedList类,我们先来看下LinkedList需要实现哪些常用方法:

我们先来实现LinkedList构造方法部分:

class LinkedList {
    constructor() {
    	this.head = null;
    	this.count = 0;
    }
}
复制代码

head为null表示默认情况下链表是一个空链表,count用来记录链表中结点的个数

push方法

class LinkedList {
    constructor() {
    	this.head = null;
    	this.count = 0;
    }
    push(element) {
        //向链表尾部添加一个新元素
        const node = new Node(element);
        let current;
        if (this.head == null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            this.count++
        }
    }
}
复制代码

pushn方法我们要考虑两种情况,第一种是链表中没有元素时和链表中有元素时,分两种情况进行处理。最后因为新添加了一个元素,所以count++

第一种情况:

链表中没有元素时我们让头结点(head)直接为node结点

第二种情况:

在有元素的情况下,我们要在尾部插入元素,那么肯定要先找到最后一个元素,然后让最后一个元素的next为新插入的元素就可以了。

一般我们都是用current表示当前元素,node表示新元素,previous表示当前元素的上一个元素。

removeAt

移除指定位置的元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
	let current = this.head;
	if (index === 0) {
	    this.head = current.next;
	} else {
    	let previous;
    	for (let i = 0; i < index; i++) {
            previous = current;
  	    current = current.next;
    	}
    	previous.next = current.next;
	}
	this.count--;
	return current.element;
    }
    return undefined;
}
复制代码

移除元素我们肯定要先做边界判断,确保index不能小于0也不能大于链表元素个数,然后再进行操作,

这里也分为两种情况:一种是index为0时和index为其他情况时

index为0则表示要删除第一个元素,那么我们其实可以直接让head为current.next,意思就是让head从当前元素的下一个元素开始,那也就是说把第一个元素丢弃掉了

其他情况:我们需要找到要删除元素的前一个元素和要删除的元素,我们让要删除元素的前一个元素的next指向当前元素的next,就可以把当前元素移除掉

最后返回删除掉的元素

getElementAt

返回指定索引的元素

对于索引我们每次都应该判断是否越界

getElementAt(index) {
    if (index >= 0 && index <= this.count) {
    	let node = this.head;
    	for (let i = 0; i < index && node != null; i++) {
    	    node = node.next;
    	}
    	return node;
    }
    return undefined;
}
复制代码

这个还是很简单的,我们只需要通过迭代把指定索引元素找到返回就可以了

insert

在指定位置插入元素

insert(element, index) {
if (index >= 0 && index <= this.count) {
	const node = new Node(element);
	if (index === 0) {
            const current = this.head;
            node.next = current;
            this.head = node;
	} else {
            let previous;
            for (let i = 0; i < index; i++) {
                previous = current;
            }
            const current = previous.next;
            node.next = current;
            previous.next = node;
	}
    	this.count++;
    	return true;
    }
    return false;
}
复制代码

indexOf

indexOf(element) {
	let current = this.head;
	for (let i = 0; i < this.count && current != null; i++) {
        if (element === current.element) {
            return i;
        }
        current = current.next;
    }
    return -1;
}
复制代码

remove

remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
}
复制代码

其余函数

size() {
    return this.count;
}
isEmpty() {
    return this.size() === 0;
}
getHead() {
    return this.head;
}
复制代码

toString

toString() {
    if (this.head == null) {
    	return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
    	objString = `${objString}->${current.element}`;
    	current = current.next;
    }
    return objString;
}
复制代码

首先,如果链表为空( head 为 null 或 undefined ),我们就返回一个空字符串。 如果链表不为空,我们就用链表第一个元素的值来初始化方法最后返回的字符串( objString )。

然后,我们迭代链表的所有其他元素,将元素值添加到字符串上。如果链表 只有一个元素, current != null 验证将失败,因为 current 变量的值为 undefined (或 null ), 算法不会向 objString 添加其他值。 最后,返回链表内容的字符串

总结

数据结构在理解的基础上再多练习就能事半功倍了

关注下面的标签,发现更多相似文章
评论