[数据结构与算法]JavaScript数据结构——链表LinkedList

笔者表达能力不太行，不会描述更多硬知识，但会解释每一步代码的操作逻辑，更多的是做个记录方便在外面看, 持续更新…

4.1 —— 简述

• 链表存储有序的元素集合，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成.
• 相对于数组，链表的添加或移除元素的操作不需要移动其他元素
• 链表需要指针，想要访问链表中的一个元素，需要从头节点（起点）开始迭代链表查找
  【第三点很重要，刷力扣时传的头节点】

4.2 —— 实现

4.3：链表节点

链表里的元素都是存储在节点中的，形象的说，一个节点就是一个容器，里面存放了数据，和一个对外的链子，链子连着下一个容器

class Node {
    constructor(value) {
        this.value = value; //接受传进来的元素
        this.next = null; //指向下一个元素的指针,默认指向null
    }
}

4.4：单向链表

链表的第一个节点称为头节点，用head标记头节点，count记录节点的数量

class LinkedList {
	constructor() {
        this.head = null; //头节点，默认为null
        this.count = 0; // 记录节点的数量
    };
}

4.4.1：size 方法

返回链表包含的元素个数,返回count值

size() {
	return this.count;
}

4.4.2：isEmpty 方法

判断链表是否为空, 链表为空返回true，不为空返回false

isEmpty() {
	return this.size() === 0;
}

4.4.3：indexOf 方法

查找特定的元素的位置，首先判断链表是否有节点，如果为空返回-1；
创建一个指针current, 默认指向头节点，判断当前节点的元素是否为传入的element，不是则指向当前节点的下一个节点，以此类推，找到了返回目标元素在链表中的位置，不存在返回-1；

indexOf(element) {
	//越界判断，如果头节点为空则返回-1，
	if (this.head) {
		//创建一个current指针，指向head
    	let current = this.head; 
        for (let i=0; i<this.count; i++) {
        	//这里current指向的是node节点，需要.value拿到元素;
            if (element === current.value) {
                return i;
            };
            //没有找到，向下移动current指针
            current = current.next;
        }
    }
    return -1;
}

4.4.4：push方法

添加元素到链表尾部：
首先将要添加的元素element放在node容器中，判断头节点是否为空，为空则直接将element作为头节点插入，因为node节点的next指向null，所以最后一个节点的指针不需要操作，默认指向null；
如果不为空，从头节点开始往下找，直到找到next指向null的节点，那必定是最后一个节点，然后将最后节点的next指针指向要插入的node节点即可。

push(element) {
    //将element存入node节点中
    const node = new Node(element);
    //越界判断
    if (!this.head) {
        this.head = node;
    } else {
        //遍历调用
        let current = this.head;
        //current.next == null 则找到了最后一个节点
        while (current.next) {
            current = current.next;
        }
        //将最后一个几点连接要插入的节点
        current.next = node;
    }
    //插入成功，节点数量加1
    this.count++;
}

4.4.5：getElement 方法

该方法接收一个索引index，返回链表中index对应的node节点, node不存在返回null

1. 首先越界判断，判断index是否符合条件，index应该大于0，且小于节点数量；
2. 创建一个指针node指向头节点，从头节点依次往下传递指针，直到找到index对应的节点,返回该节点供调用者接收

getElementAt(index) {
    if (index >= 0 && index <= this.count) {
        let node = this.head;
        for (let i=0; i<index; i++) {
            node = node.next; //依次向下传递
        }
        //返回node节点
        return node;
        //返回元素 return node.value;
    }
    //始终返回一个null，告诉调用者index错误,没有找到对应的节点
    return null;
}

4.4.6：insert方法

向链表中任意位置插入元素：insert方法接收两个参数: 要插入的值element和要插入的位置index;

1. 首先判断index是否符合条件，如果index不合理则直接返回false表示插入失败;
2. 第一种情况，index === 0 在头部插入节点，标记当前节点（头节点）将要插入的节点的指针指向标记的节点（头节点）再将要插入的节点作为头节点插入;
3. 第二种情况，index ！== 0 在头部意外的任意地方插入, 首先找到目标位置index的前一个节点index - 1标记为previous，目标位置的节点标记为current，然后将要插入的节点node指向目标位置的节点（插入后目标current的位置会往右挪一位），最后将previous的指针指向要插入的节点node
   【例：现在有两个人A连着B；现在要插入C，首先将C连接B， 由于A还是连接着B所以指针不会丢失，再将A连接C，这时A不再与B连接，A -> C -> B 】

insert(element, index) {
    if (index >= 0 && index <= this.count) {
    	//将element存入node节点中
        const node = new Node(element);
        //插在头部
        if (index == 0) {
        	//标记头节点
            const current = this.head;
            //node节点连接标记的头节点
            node.next = current;
            //node节点作为头节点插入
            this.head = node;
        } else {
        	//标记目标位置的前一个节点
            const previous = this.getElementAt(index -1);
            //标记目标位置的节点
            const current = previous.next;
            //要插入的节点node连接目标位置的节点
            node.next = current;
            //前一个节点连接node
            previous.next = node;
        };
        //操作成功，节点数量加1，返回true
        this.count++;
        return true;
    }
    return false;
}

4.4.7：removeAt 方法

该方法接收一个索引index，移除index对应的节点的元素
【如果节点直接没有指针连接，则会自动被js垃圾回收机制回收，说白了，就是自动删除】

1. 首先判断index是否符合条件，如果index不合理则直接返回false表示插入失败;
2. 创建一个指针current， 默认指向头节点 （从头节点开始）
3. 第一种情况，index === 0 移除头节点，直接将头节点指向current的下一个节点（头节点的下一个节点）
4. 第二种情况，index ！== 0 移除头节点外的任意节点, 首先找到当前位置index对应的节点current 以及前一个节点previous （index - 1），再将previous的指针指向current指向的节点，
   【例：现在有三个人依次连接A -> B -> C ；删除B后，A -> C；即 A相当于previous ，B相当于current ，C相当于current.next 】

removeAt(index) {
    if (index >= 0 && index < this.count) {
       let current = this.head;
       //三种情况考虑：移除第一项，最后一项，中间任意一项
       if (index == 0) {
           this.head = current.next;
       } else {
           // let previous;
           // //遍历index，找到index的位置
           // for (let i=0; i<index; i++) {
           //     previous = current;
           //     current = current.next;
           // }
           //调用getElementAt方法
           const previous = this.getElementAt(index 1); //找到前一个
           current = previous.next;
           //空过当前节点，当前节点没有连接会被回收
           previous.next = current.next;
       }
       //节点数量减-
       this.count--;
       //操作成功返回被删除节点的值
       return current.value;
    }
    return -1;
}

4.4.8：remove 方法

该方法接收一个值element，移除链表中的element
使用现成的方法，

1. 首先调用indexOf方法找到element在链表中的位置，
2. 然后根据返回的索引index调用removeAt方法删除对应的元素，接收removeAt返回的值，
3. 最后判断返回的值，操作成功返回elelment对应的索引值，操作失败返回-1；

remove(element) {
    //这里不需要越界判断，在两个方法里已经判断过了
    //获取element对应的位置，接收indexOf方法返回的索引值index
    const index = this.indexOf(element);
    //根据index删除对应的元素，接收removeAt方法返回的元素
    const value = this.removeAt(index);
    //如果删除成功则返回index， 删除失败返回-1；
    return value == -1 ? -1 : index;
}

4.5 双向链表

4.5.1 双向链表的节点

相对于单向链表的节点，双向链表的节点需要两个指针，分别指向头部和尾部的节点

class DoublyNode {
    constructor(value, next, prev) {
        this.value = value; //存储元素
        this.next = next; //指向后一个节点
        this.prev = prev; //指向前一个节点
    }
}

4.5.2 创建双向链表

这里使用es6中的继承，除了插入和删除操作，其他方法与单向链表一样，可以复用，双向链表的构造函数多了一个tail属性，它总是指向链表的最后一个节点

class DoublyLinkedList extends LinkedList {
	constructor() {
        this.head = null; //头节点，默认为null
        this.count = 0; // 记录节点的数量
        this.tail = null; // 指向最后一个元素
    }
}

4.5.3 双向链表的insert方法

双向链表麻烦在于处理两个指针，操作不当容易指针容易丢失，在纸上画图会清晰一点，直接上注释

insert(element, index) {
	//越界判断
    if (index >= 0 && index <= thiscount) {
    	//创建node储存element
        const node = new DoublyNod(element);
        //标记当前元素
        let current = this.head;
        //插入链表首部
        if (index == 0) {
        	//判断链表中是否有节点
            if (!this.head) {
            	//没有，直接将node作为头节点插入
                this.head = node;
                //尾指针也指向node（只有一个元素）
                this.tail = node;
            } else {
            	//不为空 将node指向头节点
                node.next = this.head;
                //current的前指针prev指向node(current默认标记head)
                current.prev = node;
                //node作为头节点插入链表中
                this.head = node;
            }
        }
        // 插入链表尾部
        else if (index == this.count) {
        	//将current移到链表尾部
            current = this.tail; //tail总是指向链表最后一个节点
            //将链表最后一个节点指向node
            current.next = node;
            //node的前节点指向标记的最后一个节点
            node.prev = current;
            //tail指向node
            this.tail = node;
        }
        //插入中间
        else {
            //找到目标的前驱节点previous 和目标位置对应的节点current 
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            //让node指向current
            node.next = current;
            //前驱节点previous指向node，（previous原来与current连接）
            previous.next = node;
            //current的前节点指向node，（current前节点原来与previous连接)
            current.prev = node;
            //最后node的前节点与前驱节点连接
            node.prev = previous;
            //这里最好画图，画图后一目了然
        };
        this.count++;
        return true;
    }
    return false;
}

4.5.4 双向链表的removeAt方法

removeAt(index) {
	//越界判断
	if (index >= 0 & index < this.count) {
		//标记current
        let current = this.head;
        //删除第一项
        if (index == 0) {
        	//移动head指针，指向下一个
            this.head = current.next;
            //如果删除后链表为空,更新尾指针
            if (this.count == 1) {
                this.tail = null;
            }
            //不为空
            else {
            	//将head的前节点指向null, 它的前一个节点没有链接会被回收
                this.head.prev = null;
            }
        }
        //删除最后一项: 找到倒数第二个节点
        else if (index == this.count -1) {
            current = this.tail;
            this.tail = current.prev; //将tail指针移到倒数第二个节点
            this.tail.next = null; //再将tail标记位置的节点的指针指向null,current节点没有链接将被回收
        }
        //删除中间
        else {
        	//找到当前位置的节点与前一个节点
            current = this.getElementA(index);
            const previous = current.prev;
            //将前驱节点的指针指向当前节点的下一个节点（断开与当前节点的前节点prev的链接）
            previous.next = current.next;
            //将当前位置的下一个节点的前节点指向前驱节点(断开与当前节点的后节点next的链接)
            current.next.prev = previous;
        }
        this.count--;
        return current.value;
    }
    return null;
}

4.6 循环链表

循环链表的结构与双向链表结构一样也是有两个节点，直接继承，不同的是，循环链表的尾指针指向head头节点，不再指向null

class CircularLinkedList extends LinkedList {}

原理跟双向链表差不多，画一画就清晰了

4.6.1 循环链表的 insert 方法

insert(element, index) {
    if (index > 0 && index <= this.count) {
        const node = new Node(element);
        let current = this.head;
        if (index == 0) {
            if (this.head == null) {
                this.head = node;
                node.next = this.head;
            } else {
                node.next = current; /node节点指针指向头节点
                //获取最后一个节点，指向节点
                current = this.getElementAt(this.size();
                this.head = node; //node作为头节点
                current.next = this.head; //最后一个节点的针指向头节点
            }
        }
        else {
            const previous = this.getElementAt(index - 1);
            node.next = previous.next;
            previous.next = node;
        }
        this.count++;
        return true;
    }
    return false;
}

4.6.2 循环链表的 removeAt方法

removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index == 0) {
            if (this.size() == 1) {
                this.head = null;
            } else {
                const removed = this.head; //要移除的元素
                current = this.getElementAt(this.size(); //找到最后一个元素
                this.head = this.head.next; //改变头节点的指指向
                current.next = this.head; // 尾节点的指针指头节点
                current = removed; //移除的节点
            }
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.count--;
        return current.value;
    }
    return null;
}

下一章，将会写一些js的操作方法，做个归类