链表（学习记录）

链表是什么

链表和数组相似，都是有序的列表，都是线性结构。
不同的是，数组在内存中是一段连续的内存空间，由此遍历数组是可以通过下标直接定位元素的，而链表是离散的内存，可能散播在内存的各个角落，所以链表之间需要通过一个关联把前后节点连接起来，就像用线串珠子一样，需要把珠子一个一个的串起来；
在链表中一个元素称为结点，结点中包括数据域(珠子)和指针域（线）；

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

数据域存着这个结点的数据值，而指针域则代表着下一个结点的引用，这样就知道下一个结点是谁啦！

创建链表

创建链表需要借助一个构造函数

function ListNode(val){
    this.val = val;   // 数据域
    this.next = null; // 指针域
}

let node = new ListNode(1);
node.next = new ListNode(2);

通过ListNode去创建结点，入参val为数据域,next为指针域；

想要访问链表中的任意一个数据，都需要从起始结点开始，逐个访问next到目标结点为止。为了保证起始结点可访问性，我们一般会创建一个头结点指向起始结点;

链表添加、删除

链表的添加和删除主要是对指针域next的操作。

添加

尾部添加

在尾部添加结点相对简单，只需要吧尾部结点的next指向要添加的结点就行；

let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);

// 将node2添加在node1后面
node1.next = node2;
// 将node3添加在node2后面
node2.next = node3;

console.log(node1);  //  { val: 1, next: { val: 2, next: { val: 3, next: null } }}

任意两节点中添加

在node1和node2中间插入node3；


let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);

node1.next = node2;  
console.log(node1)  // {val: 1, next: { val: 2, next: null}

// 中间插入node3
node3.next = node1.next;
node1.next = node3;
console.log(node1) //  { val: 1, next: { val: 3, next: { val: 2, next: null } }}

删除


let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);

// 将node2添加在node1后面
node1.next = node2;
// 将node3添加在node2后面
node2.next = node3;
console.log(node1); // { val: 1, next: { val: 2, next: { val: 3, next: null } }}

// 删除node2
node1.next = node2.next;
console.log(node1); // { val: 1, next: { val: 3, next: null } }