Day9:[资料结构] Linked-List - 链结串列

Linked List为抽象的资料结构，概念有点像三国的连环船，一艘船(节点)连结着下一艘船(节点)，每个节点除了拥有自己的值之外也记录自己的下一个节点是指向哪个节点，而Linked List又分为下列几种

Simple Linked List

单向的Linked List，最後一个节点next指向null

Circular Linked List

最後一个节点的next指向第一个，形成一个循环

Doubly Linked List

双向的Linked List，可以看到节点除了纪录next指向谁，也会记录是谁指向自己

Linked List v.s Array

Linked List为不连续的记忆体空间，因此在存放每个元素的同时 ，也会记录下一个元素存放的位置，但假设今天想要取得链结串列的最後一个元素时 ，就必须从第一个元素开始读取， 逐一读到最後一个，读取效率较为不理想，但是做插入和删除资料的时候非常快，时间复杂度只有O(1)。

Array为连续的记忆体空间，所以可以直接用索引(index)来取得需要的值 ，读取相当的快，不过假如要删除一个元素或新增一个元素都会影响到其他元素的排序，统一往後或是往前挪，因此时间复杂度为O(n)，n为阵列长度。

下图是操作两者所需的时间复杂度比较

那甚麽时候该用Linked List呢?

不需要快速的查询资料以及有频繁新增删除资料的需求

用js实作Linked List

创建一个linked list，初始节点的值为apple并且将next指向banana

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor(value) {
        //初始的节点命名为head
        this.head = new ListNode(value);
    }
    add(value) {
        const newNode = new ListNode(value);
        //head的next指向新的节点
        this.head.next = newNode;
        console.log("head", this.head);
    }
}

let linkedList = new LinkedList("apple");
linkedList.add("banana");

成功做出一个Linked List!