数据结构与算法—链表

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

链表与数组的对比：

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。在数组中，我们可以直接访问任何元位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

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

/**
 * @class LinkedList
 * @classdesc 链表
 * size(): 返回链表包含的元素个数
 * isEmpty(): 判断链表中是否包含元素
 * toString(): 返回表示整个链表的字符串
 * getElementAt(position): 返回链表中特定位置的元素
 * push(element): 向链表尾部添加一个新元素
 * insert(element, position): 向链表的特定位置插入一个新元素
 * removeAt(position): 从链表的特定位置移除一个元素
 * indexOf(element): 返回元素在链表中的索引
 * remove(): 从链表中移除一个元素
 */

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

    size() {
        return this.count
    }

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

    toString() {
        if (this.head == null) {
            return ''
        }

        let objString = `${this.head.element}`;
        let current = this.head.next
        for (let i = 1; i < this.size(); i++) {
            objString = `${objString},${current.element}`
            current = current.next
        }

        return objString
    }

    getElementAt(position) {
        if (position >= 0 && position <= this.count) {
            let node = this.head
            for (let i = 0; i < position; i++) {
                node = node.next
            }
            return node
        }
        return undefined
    }

    push(element) {
        const node = new Node(element)
        let current
        if (this.head == null) { // 判断是否为空链表
            this.head = node
        } else {
            current = this.head
            while (currnet.next != null) { // 获得最后一项
                current = current.next
            }
            // 将 next 赋为新元素，建立链接
            current.next = node
        }
        this.count++
    }

    insert(element, position) {
        if (position >= 0 && position <= this.count) {
            const node = new Node(element)
            if (position === 0) {
                const current = this.head
                node.next = current
                this.head = node
            } else {
                const current = this.getElementAt(position - 1)
                node.next = current.next
                current.next = node
            }
            this.count++
            return true
        } else {
            return false
        }
    }

    removeAt(position) {
        if (position >= 0 && position < this.count) {
            let currnet = this.head
            if (position == 0) {
                this.head = currnet.next
            } else {
                const previous = this.getElementAt(position - 1)
                currnet = previous.next
                previous.next = currnet.next
            }

            this.count--
            return currnet.element
        } else {
            return false
        }
    }

    indexOf(element) {
        let current = this.head
        let index = 0
        while (current) {
            if (current.element === element) {
                return index
            }
            current = current.next
            index++
        }

        return -1
    }

    remove(element) {
        const index = this.indexOf(element)
        return this.removeAt(index)
    }
}

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

注意：下列代码实现过程中，迭代均为从表头到表尾，可自行实现从表尾到表头的迭代方式，以此进行优化查询。

class DoublyNode {
    constructor(element) {
        this.element = element;
        this.prev = undefined
        this.next = undefined
    }
}


class DoublyLinkedList {
    constructor() {
        this.count = 0
        this.head = undefined
        this.tail = undefined
    }

    isEmpty() {
        return this.count === 0
    }

    size() {
        return this.count
    }

    // 获取链表第一个元素
    getHead() {
        return this.head
    }

    // 获取链表最后一个元素
    getTail() {
        return this.tail
    }

    // append 向链表尾部添加一个新元素
    append(element) {
        const node = new DoublyNode(element)
        if (!this.head) {
            this.head = node
            this.tail = node
        } else {
            node.prev = this.tail
            this.tail.next = node
            this.tail = node
        }
        this.count++
    }

    // toString 返回表示整个链表的字符串（正向遍历)
    toString() {
        return this.backwardString()
    }

    // forwardString 返回表示整个链表的字符串（从尾到头）
    forwardString() {
        let current = this.tail
        let resultString = ''
        while (current) {
            resultString += current.element + ''
            current = current.prev
        }

        return resultString
    }

    // backwardString 返回表示整个链表的字符串（从头到尾的顺序）
    backwardString() {
        let current = this.head
        let resultString = ''
        while (current) {
            resultString += current.element + ' '
            current = current.next
        }
        return resultString
    }

    // 返回元素在链表中的索引
    indeOf(element) {
        let index = 0
        let currnet = this.head
        while (currnet) {
            if (currnet.element === element) {
                return index
            }
            currnet = currnet.next
            index++
        }
        return -1
    }

    // 返回链表中特定位置的元素 
    getElementAt(position) {
        if (position >= 0 && position < this.count) {
            let current = this.head
            let i = 0
            while (i < position) {
                current = current.next
                i++
            }
            return current
        }
        return false
    }

    // insert(element,index) 在链表任意位置插入新元素
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new DoublyNode(element)
            let current = this.head
            if (index === 0) { // 判断是否在链表头部插入
                if (this.head) { // 判断是否是空链表
                    node.next = current
                    current.prev = node
                    this.head = node
                } else {
                    this.head = node
                    this.tail = node
                }
            } else if (index === this.count) { // 判断是否是在链表尾部插入
                current = this.tail
                current.next = node
                node.prev = current
                this.tail = node
            } else { // 在链表中间插入元素
                let i = 0
                while (i++ < index) { // 找到当前链表中 index 位置的元素
                    current = current.next
                }
                node.next = current
                node.prev = current.prev
                current.prev.next = node
                current.prev = node
            }
            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 {
                let i = 0
                while (i++ < index) {
                    current = current.next
                }
                current.prev.next = current.next
                current.next.prev = current.prev
            }
            this.count--
            return true
        }
        return false

    }

    // 从链表中移除一个元素
    remove(element) {
        const index = this.getElementAt(element)
        return this.removeAt(index)
    }
}

const list = new DoublyLinkedList()
console.log(list.append('aa'));
console.log(list.append('bb'));
console.log(list.append('cc'));
console.log(list.append('ee'));
console.log(list.append('ff'));
console.log(list.insert('dd', 1));
console.log(list.getElementAt(0));
console.log(list.getElementAt(1));
console.log(list.getElementAt(2));
console.log(list.toString());
console.log(list.removeAt(2));
console.log(list.toString());

循环链表（暂不详细实现）

循环列表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是 undefined，而是指向第一个元素（head）。

有序链表（暂不详细实现）

有序链表是指保持元素有序的链表结。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。

使用链表来实现一个栈（创建 StackLinkedList 类）

class StackLinkedList {
	constructor(){
		this.items = new DoublyLinkedList();
	}
	
	push(element) {
		this.items.append(element)
	}

	pop() {
		if(this.isEmpty()){
			return undefined
		} else {
			this.items.removeAt(this.size() - 1)
		}
	}
	
	peek() {
		if(this.isEmpty()) {
			return undfined
		} else {
			return this.items.getElementAt(this.size() - 1).element;
		}
	}
	
	isEmpty() {
		return this.items.isEmpty()
	}
	
	size() {
		return this.items.size() 
	}

	clear() {
		this.items.clear()
	}

	toString() {
		return this.items.toString()
	}
}