乐趣区

关于javascript:前端算法系列之二数据结构链表双向链表闭环链表有序链表

jiezi

前言

上一次咱们讲到了数据结构：栈和队列，并对他们的使用做了一些介绍和案例实际；咱们也讲到了怎么简略的实现一个四则运算、怎么去判断标签是否闭合齐全等等，anyway，明天接着和大家介绍一些数据结构：
上一篇：前端算法系列之一：工夫复杂度、空间复杂度以及数据结构栈、队列的实现

链表

链表是一种怎么样的构造呢？链表就是一种能够把数据串联起来的构造，每个元素会有指向下一个元素的指针（开端的没有一般链表），就像事实世界中的火车一样一节一节的串联起来；链表依据本身的指针指向又能够分为：单向链表、双向链表、循环链表；

链表首先会有一个表头，表头作为起始的指针，而后每一个元素咱们称作为节点 (node); 每个节点有一个指向下一个节点的指针 (next)，直到链表的开端指针会指向 undefined；

链表的实现

1、节点

节点的创立和定义；每个节点会有一个保留本人数据的属性 (element)，而后有一个指针 (next)

export class Node {constructor(element, next = null) {
        this.element = element;
        this.next = next;
    }
}

2、链表的 api

getElementAt(position): 获取某个地位的元素

append(element): 向链表开端中增加元素

removeAt(idx): 移除某个元素

insert(element, position = 0, dir = ‘before’): 向指定地位增加元素

insertAfter(element, position): 向指定的地位前面增加元素

size(): 链表的长度

remove(): 删除链表末端元素

removeAll(): 删除整个链表

isEmpty(): 查看链表是否为空 

import {defaultEquals} from "../util.js";
import {Node} from './Node.js'

export default class LinkedList {constructor(equalsFn = defaultEquals) {
        this.count = 0;
        this.head = null;
        this.equalsFn = equalsFn;
    }
    getElementAt(position) {if(position >= 0 && position <= this.count) {
            let node = this.head;
            for (let i = 0; i < position && !!node; i++) {node = node.next;}
            return node;
        }
        return undefined;
    }

    insertAfter(element, position) {return this.insert(element, position, 'after');
    }
    size() {return this.count;}
    remove() {return this.removeAt(this.size() - 1);
    }
    removeAll() {
        this.count = 0;
        this.head = null;
    }
    isEmpty() {return this.size() === 0;
    }
    getHead() {return this.head;}
}

3、链表开端增加一个元素 append;

    append(element) {const node = new Node(element);
        let current = this.head;
        if(current == null) {this.head = node;} else {
            current = this.head;
            while (current.next !=  null) {current = current.next;}
            current.next = node
        }
        this.count++;
        return element;
    }

4、插入一个元素 

    insert(element, position = 0, dir = 'before') {if (element === undefined) {throw Error('短少须要插入的元素');
             return;
        }
        if (position >= this.count) {return this.append(element);
        }
        const node = new Node(element);
        const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position);
        if (!targetNode) {
            let prev = this.head;
            this.head = node;
            node.next = prev;
        } else {
            let next;
            next = targetNode.next
            targetNode.next = node;
            node.next = next;
        }
        this.count++;
        return element;
    }

5、删除一个元素 

removeAt(idx) {if (idx >= 0 && idx < this.count) {
            let current = this.head;
            if (idx === 0) {
                this.head = current.next;
                current.next = null;
            } else {let prev = this.getElementAt(idx - 1);
                current = prev.next;
                prev.next = current.next;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

6、双向链表

单向链表元素指向都是一个方向的，也只能被单向递归搜寻，而双向链表不仅仅有指向下一个元素的指针同时具备指向上一个元素的指针；

import LinkedList from "./LinkedList";
import {defaultEquals} from "../util";
import {DoubleNode} from "./DoubleNode";

export default class DoubleLinkedList extends LinkedList{constructor(equalIsFn = defaultEquals){super(equalIsFn);
        this.tail = null;// 队列尾部
    }
    getElementAt(position) {if(position >= 0 && position <= this.count) {if (position > this.count/2) {
                let cur = this.tail;
                for (let i = this.count - 1; i > position; i--){cur = cur.prev;}
                return cur;
            } else {return super.getElementAt(position)
            }
        }
        return undefined;
    }
    removeAll() {super.removeAll();
        this.tail = null;
    }
    removeAt(position) {if (position >= 0 && position < this.count) {let cur = this.getElementAt(position);
            if(position === 0) {
                this.head = cur.next;
                cur.next = null;
                this.prev = null;
            } else if (position === this.count - 1) {
                this.tail = cur.prev;
                this.tail.next = null;
                cur.prev = null;
            } else {
                let prev = cur.prev;
                let next = cur.next;
                prev.next = next;
                next.prev = prev;
                cur.prev = null;
                cur.next = null;
            }
            this.count--;
            return cur.element;
        }
        return undefined;
    }
}

队列开端插入元素 (append)

双向链表插入元素和单向比拟相似，不同的是双向不仅要链接他的上级还得关联他的前一级；

    append(element) {const node = new DoubleNode(element);
        if (!this.tail) {
            this.head = node;
            this.tail = node;
        } else {
            let cur = this.tail;
            cur.next = node;
            node.prev = cur;
            this.tail = node;
        }
        this.count++;
        return element;
    }

两头某个地位插入元素 

insert(element, position = 0, dir = 'before'){if (element === undefined) {throw Error('短少须要插入的元素');
            return;
        }
        if (position >= this.count) {return this.append(element);
        }
        const node = new DoubleNode(element);
        let cur;
        const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position);
        if (!targetNode) {
            cur = this.head;
            node.next = cur;
            cur.prev = node;
            this.head = node;
        } else {
            let next;
            next = targetNode.next
            targetNode.next = node;
            node.prev = targetNode;
            node.next = next;
            next.prev = node;
        }
        this.count++;
        return element;
    }

移除某个元素也是上述雷同，批改节点的前后指针就能够了，这里不再赘述，详情看源码

https://github.com/JasonCloud/DataStructuresAndAlgorithms

闭环链表

闭环链表也称环，是一个闭合的构造，尾部会指向头部

有序链表

有序链表就是在 append 元素的时候进行排序退出从而失去一个有程序的链表，比拟函数能够依据实例化的时候传入比拟函数 equalIsFn；

退出移动版