数据结构学习--链表

链表是物理存储单元上非连续的、非顺序的存储结构，不同于栈和队列。链表由一系列节点组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

下面为链表的结构示意图

1.1、节点

节点包含了两部分，一部分是存储数据的元素区域，一部分是指向下一个节点的指针区域，上图中绿色部分表示数据区域，蓝色部分表示指针区域，它们共同构成一个节点。

定义一个节点：

let Node = function(data) {
    this.data = data // 数据
    this.next = null // 指针
}
// 创建新的节点
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
node1.next = node2;
node2.next = node3
复制代码

1.2、首尾节点

链表中的第一个节点是首节点，最后一个节点是尾节点。

1.3、有头链表和无头链表

1. 无头链表是指第一个节点既有数据域，又有指针域，第一个节点既是首节点又是头节点。

2. 有头链表是指第一个节点只有指针域，而没有数据域。通常有头链表的数据域可以存放当前的链表的一些信息。

在链表定义中展示的就是无头链表，一个有头链表的结构图如下：

2、链表的实现

2.1、定义链表类

function LinkList() {
    let Node = function(data) {
        this.data = data
        this.next = null
    }
    let length = 0   // 链表长度 
    let head = null  // 头节点
    let tail = null  // 尾节点
}
复制代码

2.2、链表的方法

• append， 添加一个新的元素
• insert，在指定位置插入一个元素
• remove，删除指定位置的节点
• get，返回指定索引位置的元素
• print，打印整个链表

2.2.1、append

• 每次append，都要先创建一个node节点，如果列表为空，则让head和tail指向这个新创建的节点
• 如果列表不为空，则tail.next = node， 并让tail指向node

this.append = (data) => {
    // 创建一个新的节点
    let new_node = new Node(data)
    
    // 判断是否为空链表
    if(head === null) {
        head = new_node
        tail = head
    } else {
        tail.next = new_node // 尾节点指向新创建的节点
        tail = new_node      // 让尾节点等于新创建的节点
    }
    length ++
}
复制代码

2.2.2、insert

append只能在链表的末尾添加元素，而insert可以在指定位置插入一个元素，新增数据的方式更加灵活，insert方法需要传入参数index，指明要插入的索引位置。该方法的关键是找到索引为index-1的节点，只有找到这个节点，才能将新的节点插入到链表中

this.insert = (index. data) => {
        if(index<0 || index > length) return // index无效值
        if(index === length) { // 当index等于length调用append方法
            return this.append(data)
        } else {
            let new_node = new Node(data)
            if(index === 0) { // 
                new_node.next = head
                head = new_node
            } else {
                let insert_index = 1
                let curr_node = head
                while(insert_index < index) {
                    insert_index ++
                    curr_node = curr_node.next
                }
                let next_node = curr_node.next // 记录当前节点下一个节点
                curr_node.next = new_node      // 当前节点下一个节点设为新节点
                new_node.next = next_node      // 看上面的图会更能明白
            }
        }
        length ++
}
复制代码

2.2.3、remove

删除指定位置的节点，需要传入参数index,和insert方法一样，先考虑索引的范围是否合法，然后考虑索引在边界时的操作，关键点是找到索引为index-1的这个节点，这个节点的next指向了要删除的节点。

this.remove = (index) => {
    if(index<0 || index>length) return
    if(index === 0) {
        let del_node = head
        head = head.next
        del_node.next = null
    } else {
        let del_index = 0
        let pre_node = null // 要删除节点的前一个节点
        let curr_node = head // 要删除的节点
        while(del_index<index) { // 依此循环找到
            del_index++
            pre_node = curr_node
            curr_node = curr_node.next
        }
        let del_node = curr_node
        pre_node.next = curr_node.next // 要删除节点的前一个节点的下一个节点等于要删除节点的下一个节点
        del_node.next = null // 要删除节点的下一个节点为空
        if(curr_node.next === null) { // 如果删除的是尾节点
            tail_node = pre_node
        }
    }
    length --
}
复制代码

2.2.4、最终代码

其他方法比较容易理解

function LinkList() {
  let Node = function (data) {
    this.data = data
    this.next = null
  }
  let length = 0
  let head = null
  let tail = null

  // 在尾部添加节点
  this.append = (data) => {
    // 创建新节点
    let new_node = new Node(data)
    if (head == null) {
      head = new_node
      tail = new_node
    } else {
      tail.next = new_node
      tail = new_node
    }
    length +=1
    return true
  }
  // 打印节点
  this.print = () => {
    let curr_node = head
    while (curr_node) {
      console.log(curr_node.data)
      curr_node = curr_node.next
    }
  }
  // 指定位置添加节点
  this.insert = (index, data) => {
    if (index > length || index < 0) {
      return
    } else if (index == length) {
      return this.append(data)
    } else {
      let new_node = new Node(data)
      if (index == 0) {
        new_node.next = head
        head = new_node
      } else {
        let insert_index = 1
        let curr_node = head
        while (insert_index < index) {
          insert_index ++
          curr_node = curr_node.next
        }
        let next_node = curr_node.next
        curr_node.next = new_node
        new_node.next = next_node
      }
    }
    length ++
    return true
  }
  // 删除指定位置节点
  this.remove = (index) =>{
    if (index<0||index>=length) {
      return false
    } else {
      let del_node = null
      if (index == 0) {
        del_node = head
        head = head.next
        del_node.next = null
      } else {
        let del_index = 0
        let pre_node = null
        let curr_node = head
        while (del_index<index) {
          del_index++
          pre_node = curr_node
          curr_node = curr_node.next
        }
        del_node = curr_node
        pre_node.next = curr_node.next
        if (curr_node.next == null) {
          tail = pre_node
        }
        del_node.next = null
      }
    }
    length --
    // return del_node.data
  }
  // 返回指定位置节点
  this.get = (index) => {
    if (index>=length || index<0) {
      return false
    }
    let node_index = 0
    let curr_node = head
    while (node_index<index) {
      node_index++
      curr_node = curr_node.next
    }
    return curr_node.data
  }
复制代码

3、链表应用

3.1、链表反转

迭代反转

思路

假设链表中间的某个点为 curr_node ，它的前一个节点是 pre_node ,后一个节点是 next_node ，现在把思路聚焦到这个 curr_node 节点上，只考虑在这一个点上进行翻转： curr_node.next = pre_node ;只需要这简单的一个步骤就可以完成对 curr_node 节点的翻转,对于头节点来说，它没有上一个节点，让 pre_node=null ,表示它的上一个节点是一个空节点。在遍历的过程中，每完成一个节点的翻转，都让 curr_node = next_node ,找到下一个需要翻转的节点。同时， pre_node 和 next_node 也跟随 curr_node 一起向后滑动。

function reveser(head) {
  if (!head) {
    return false
  }
  let pre_node = null
  let curr_node = head
  while (curr_node) { // 循环结束条件为当前节点为空
    let next_node = curr_node.next // 记录当前节点下一个节点
    curr_node.next = pre_node // 当前节点的下一个节点变为前一个节点
    pre_node = curr_node // 向下遍历
    curr_node = next_node
  }
  return pre_node
}
复制代码

递归反转

递归的核心之处在于 先执行的后执行 完，以及递归的出口

function reveser_digui(head) {
  if (!head) {
    return false
  }
  if (head.next == null) { // 出口
    return head
  }
  let new_head = reveser_digui(head.next) // 递归调用
  head.next.next = head // 下一个节点指向上一个节点
  head.next = null // 
  return new_head
}
复制代码

3.2、合并两个有序链表

已知有两个有序链表(链表元素从小到大)，请实现函数merge_link，将两个链表合并成一个有序链表，并返回新链表，原有的两个链表不要修改。

思路

合并两个有序链表，是归并 排序 在链表上的一种实践。对两个链表，各自设置一个游标节点指向头节点，对游标节点上的数值进行比较，数值小的那个拿出来放入到合并链表中，同时游标节点向后滑动，继续比较游标节点数值大小。

为了实现滑动，需要使用一个while循环，当其中一个游标节点为null时，循环终止，这时，可能另一个游标节点还没有到达尾节点，那么把这段还没有遍历结束的链表添加到合并列表上。

代码

function merge_link(head1,head2) {
    if(head1 === null && head2 === null) return
    if(head1 === null) {
        return head2
    } else if (head2 === null){
        return head1
    }
    let merge_head = null // 合并后的头节点
    let merge_tail = null // 合并后的尾节点
    let curr1 = head1 // 游标
    let curr2 = head2
    while(curr1&&curr2) {
        let min_node = null // 最小的节点
        if(curr1.data<curr2.data) { // 找到最小的节点
            min_node = curr1.data
            curr1 = curr1.next  // 向后滑动
        } else {
            min_node = curr2.data
            curr2 = curr2.next
        }
        // 想合并的链表添加节点
        if(merge_head === null) { // 链表为空
            merge_head = new Node(min_node)
            merge_tail = merge_head
        } else { // 不为空
            let new_node = new Node(min_node)
            merge_tail.next = new_node
            merge_tail = new_node
        }
        // 判断是否有剩余的部分
        let res_link = null
        if(curr_1){
            rest_link = curr_1;
        }
        if(curr_2){
            rest_link = curr_2;
        }
        while (res_link) { // 依此将剩余的加到合并链表
            let new_node = new Node(res_link.data)
            merge_tail.next = new_node
            merge_tail = new_node
            res_link = res_link.next
        }
    }
    return merge_head
}
复制代码

链表还有很多其他会被问道的问题比如：

1. 查找单链表中的倒数第K个节点（k > 0）：定义两个游标都指向head,先让其中一个走k步，然后两个一起走，当先走的走到尽头时此时后走的所在的位置就是倒数第k个。
2. 查找单链表的中间结点：定义两个节点k1、k2，k1一次走两步，k2一次走一步，当k2走到尽头时此时k1所在的位置中间节点。
3. 实现双向链表：多了一个前驱指针

4、最后

在学习了链表之后，发现链表比队列和栈更加困难，日后要多加复习和练习来巩固学到的内容。