多个元素组成的列表

元素存储不连续，用next指针连在一起

JavaScript中没有链表

可以使用Object模拟链表

数组 VS 链表

数组：增删非首位元素时需要移动元素

链表：增删非首位元素时，不需要移动元素，只需要更改next的指向即可

1. 定义

存储有序的元素集合

不是连续放置的

一个存储元素本身的节点 + 一个指向下一个元素的引用

2. 具体操作

创建

class Node {  //表示想要添加到链表中的项
    constructor(element, next) {
      this.element = element;
      this.next = next;  //指向链表中下一个元素的指针
    }
}

class LinkedList {
    constructor() {
    this.count = 0;
    this.head = undefined; //保存引用
    }
}

方法

//返回特定位置的元素
getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;  //通过循环，使得node指向index元素
      }
      return node;
    } 
    throw new Error("out range");
}

//返回元素在链表中的索引。如果链表中没有该元素则返回-1
indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.size() && current != null; i++) {
      if (current.element === element) {
        return i;
      }
      current = current.next;
    }
    return -1;
}

//向尾部添加一个新元素
push(element) {
    let node = new Node(element);
    if (this.head == null) {  //如果是空链表，直接加到头部
      this.head = node;
    } else {
        let current = this.head;
        while (current.next != null) { //获得最后一项
            current = current.next;
        } 
        //当current.next == undefined||null时，即到达链表尾部
        //**链表最后一个节点的下一个元素始终是undefined或null**
        current.next = node;  //将其next赋为新元素，建立链接
    }
    this.count++;
}
//也可以使用这个方法
// ……
// else {
//      **let current = this.getElementAt(this.count - 1);**  //找到node
//      **current.next = node;**
//     }
// ……

//向特定位置插入一个新元素
insert(element, index) {
    if (index >= 0 && index <= this.count) {  //在范围内
        let node = new Node(element);
        if (index === 0) {  //在头部直接加
            const current = this.head;
            node.next = current;
            this.head = node;
        } else {
            const pre = this.getElementAt(index - 1);  //获得前一个节点的位置
            node.next = pre.next; //新创建的节点赋值为pre.next
            pre.next = node;  //将pre.next指向新创建的节点
        }
        this.count++;  //长度+1
        return true;
    }
    throw new Error("out range");
}

//从特定位置移除一个元素
removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) { //移除第一项
            this.head = current.next; //也可以使用head=head.next
        } else {
            for (let i = 0; i < index; i++) {  //从移除的位置开始，其后元素往前移一位
                let pre = current;
                current = current.next;
            }
            //pre为要移除元素的前一位，next指针指向移除元素的下一位，即实现了移除元素
            pre.next = current.next; 
        }
        this.count--;
        return current.element;
    }
    return undefined; //如果index不在范围内，返回undefined
}

//移除一个元素
remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
}

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

size() {
	return this.count;
}

getHead() {
	return this.head;
}

clear() {
    this.head = undefined;
    this.count = 0;
}

//把LinkedList对象转换成一个字符串
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;
}

3. 双向链表

链接是双向的：一个链向下一个元素，另一个链向前一个元素

优势：在单向链表中，如果迭代时错过了要找的元素，就需要回到起点重新开始迭代

双向链表要同时控制 next 和 prev 这两个指针

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

function defaultEquals(a, b) {
    return a === b;
}

class LinkedList {
    constructor(equalsFn = defaultEquals) {
    this.count = 0;
    this.head = undefined;
    this.equalsFn = equalsFn;
    }
}

class DoublyNode extends Node {
    constructor(element,next,prev) {
        super(element,next);
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList {
    constructor(equalasFn = defaultEquals) {
        super(equalasFn);
        this.tail = undefined;
    }
}

insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new DoublyNode(element);
        let current = this.head;
        if (index === 0) {
            if(this.head == null) { //空链表，直接让this.head和this.tail指向node即可
                this.head = node;
                this.tail = node;
            } else {
                node.next = this.head;
                current.prev = node; 
                this.head = node;
            }
        }else if (index === this.count) { //插入到末尾
            current = this.tail;
            current.next = node;
            node.prev = current;
            this.tail = node;
        } eles {
            const previous = this.getElementAt(index - 1); //查找插入点前一个位置
            current = previous.next;
            node.next = current;
            previous.next = node;
            current.prev = node;
            node.prev = previous;
        }
        this.count++;
        return true;
    }
    return false;
}

removeAt(index) {
    if (index >= 0 && index < this.count) { //在范围内
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
            if (this.count === 1) {
                this.tail = undefined;
            } else {
                this.head.prev = undefined;
            }
        } else if (index === this.count - 1) { //删除最后一个元素
            current = this.tail;
            this.tail = current.prev;
            this.tail.next = undefined;
        } else {
            current = this.getElementAt(index);
            const previous = current.prev;
            previous.next = current.next;
            current.next.prev = previous;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

4. 循环链表

具有链表单项引用+双向链表双向引用

最后一个元素指向下一个元素的指针（tail.next）指向第一个元素（head）

双向循环链表：有指向head元素的tail.next和指向tail元素的head.prev

class CircularLinkedList extends LinkedList {
    constructor(equalsFN = defaultEquals) {
        super(equalsFn);
    }
}

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的next指针指向头部
                current = this.getElementAt(this.size()); //最后一个元素
                this.head = 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;
}

removeAt(index) {
    if(index >= 0 && index < this.count) {
        let current = this.head;
        if(index === 0) { //移除第一个元素
            if(this.size() === 1) {
                this.head = undefined; //只有一个元素，直接让头部为undefined
            } else {
                const removed = this.head;
                current = this.getElementAt(this.size()); //最后一个元素
                this.head = this.head.next;  //头部元素变成下一个元素
                current.next = this.head;  //最后一个元素next指针指向头部
                current = removed;  //获得移除的元素，后面return移除元素的值
            }
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

5. 有序链表

保持元素有序的链表结构

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};
function defaultCompare(a,b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn);
        this.compareFn = compareFn;
    }
}

insert(element, index = 0) {
    if(this.isEmpty()) {
        return super.insert(element,0);
    }
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(elemenet,pos);
}

getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    for(; i < this.size() && current; i++) {
        const comp = this.compareFn(element,current.element);
        if(comp === Compare.LESS_THAN) {
            return i;
        }
        current = current.next;
    }
    return i;
}

6. 创建StackLinkedList 类

class StackLinkedList {
    constructor() {
    	this.items = new DoublyLinkedList(); // {1}
    }
    push(element) {
        this.items.push(element); // {2}
    }
    pop() {
        if (this.isEmpty()) {
            return undefined;
    }
    return this.items.removeAt(this.size() - 1); // {3}
    }
}

7. LeetCode题

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1) {
        const tmp = p1.next;
        p1.next = p2; //指向前一个指针
        p2 = p1; 
        p1 = tmp; 
    }
    return p2; //p1已经跑不见了
};

大致的思路：

翻转节点，将n+1的next指向n

具体操作：

创建一对快慢指针，p1指向头部，p2指向null（慢于p1）

当p1存在时，将p1.next用tmp存起来，p1.next指向前一个指针，p2、p1向右走，直到所有节点都翻转过来

var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0)
    let p1 = l1
    let p2 = l2
    let p3 = l3
    let carry = 0  //存放上一个val的个位数
    while(p1 || p2) {
        const v1 = p1 ? p1.val:0
        const v2 = p2 ? p2.val:0
        const val = v1 + v2 + carry  //加起来
        carry = Math.floor(val / 10)  //取出十位数
        p3.next = new ListNode(val % 10)  //把个位数加上去
        //p1 p2向右走
        if(p1) p1 = p1.next  
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    if(carry) {
        p3.next = new ListNode(carry)  //把carry也放进去
    }
    return l3.next
};

var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next) {
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else {
            p = p.next;
        }
    }
    return head;
    
};

var hasCycle = function(head) {
    let slow = head;
    let fast = head;
    while(slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            return true;
        }
    }
    return false;
};

快慢指针： 快慢指针遇上，表明有环

8. 应用

参考文章：《前端与链表》