前端算法：数据结构、双向、闭环、有序链表

链表

链表是一种怎么样的结构呢？链表就是一种可以把数据串联起来的结构，每个元素会有指向下一个元素的指针（末尾的没有普通链表），就像现实世界中的火车一样一节一节的串联起来；链表根据自身的指针指向又可以分为：单向链表、双向链表、循环链表；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

链表首先会有一个表头，表头作为起始的指针，然后每一个元素我们称作为节点(node);每个节点有一个指向下一个节点的指针(next)，直到链表的末尾指针会指向undefined；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

链表的实现

1、节点

节点的创建和定义；每个节点会有一个保存自己数据的属性(element)，然后有一个指针(next)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

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

2、链表的api

getElementAt(position): 获取某个位置的元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

append(element): 向链表末尾中添加元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

removeAt(idx): 移除某个元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

insert(element, position = 0, dir = 'before'): 向指定位置添加元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

insertAfter(element, position): 向指定的位置后面添加元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

size(): 链表的长度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

remove(): 删除链表末端元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

removeAll(): 删除整个链表文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

isEmpty(): 检查链表是否为空文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

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;
    }

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

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;
    }

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

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;
    }

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

6、双向链表

单向链表元素指向都是一个方向的，也只能被单向递归搜索，而双向链表不仅仅有指向下一个元素的指针同时具有指向上一个元素的指针；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

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)

双向链表插入元素和单向比较类似，不同的是双向不仅要链接他的下级还得关联他的前一级；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

    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;
    }

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

中间某个位置插入元素

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://www.cainiaoxueyuan.com/suanfa/20929.html

移除某个元素也是上述相同，修改节点的前后指针就可以了，这里不再赘述，详情看源码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

https://github.com/JasonCloud/DataStructuresAndAlgorithms文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

闭环链表

闭环链表也称环，是一个闭合的结构，尾部会指向头部
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html

有序链表

有序链表就是在append元素的时候进行排序加入从而得到一个有顺序的链表，比较函数可以根据实例化的时候传入比较函数equalIsFn；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/20929.html