title

date

链表

简单说几句

在前端开发中，经常接触到的线性结构有数组、字符串，还有ES6中的Set和Map。这其中最常用的，应该就数数组了。我们今天要说到的链表也是数据元素的线性集合，跟数组和字符串不同的是，链表元素的线性顺序不是由他们在内存中的物理位置给出的，而是由他一个又一个的节点的指向串起来的序列表现出来的。这样设计的目的是为了解决数组等数据结构需要预先知道数据大小的缺点，开发js的同学可能不太了解，因为js中的数组是支持动态扩容的，(感兴趣的朋友移步这篇好文『v8引擎下的“数组”底层实现』)

链表在插入的时候很快，可以达到O(1)的复杂度，但他的访问时间是线性的，更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。今天就来说说这个链表，以及它在js中的实现。

今天的主角——链表

链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的基本数据以节点来表示，每个节点由元素+指针构成，元素是存储数据的存储单元，指针就是连接每个节点的地址数据。来源百度

链表中又分为单链表、双链表和循环链表等，其中最简单的要数单链表了

单链表

单链表的的节点只有两个域，一个是信息域，一个是指针域。信息域会保存当前节点的数据信息，而指针域保存着指向下个节点的地址，最末尾的节点的指针域指向null。介绍到这里的时候，链表这个名字的由来就一清二楚了。每个节点保存数据的同时，还指向下个节点，然后下个节点继续保存数据的同时指向它的下个节点，一个个节点就这么链接起来，形成了一个链条。

单链表在js中的实现

单链表由最开始的head一直指向null。中的链条节点，data存放数据，next存放下个节点的地址数据。所以单个的节点，实现起来就很简单了

class Node{
  constructor(element){
    // 信息域
    this.element = element;
    // 指针域
    this.next = null;
  }
}

同时这个链表数据还要实现增删改查的功能。

class SignleLinkLit{
  constructor(){
    // 初始的头部节点
    this.head = null
    // 初始长度
    this.length = 0;
  }

  // 获取链表
  getList() {
    return this.head;
  }
  // 链表长度
  size() {
    return this.length;
  }
  // 链表是否为空
  isEmpty() {
    return this.length === 0;
  }
  // 追加
  append(element) {}
  // 搜寻
  search(list, element) {}
  // 插入
  insert(position, element) {}
  // 移除
  remove(element) {}
}

getList、size和isEmpty这三个方法自不必说了，我们着重说说另外四个操作链表数据的方法。

追加节点

由于链表的的特性，追加节点只需遍历到尾部节点，并将其指针域指向待追加的节点就可以了

// 追加节点
append(element){
  // 先定义当前节点
  const node = new Node(element);
  // 用来辅助找到链尾的变量
  let temp = this.head;

  if(!this.head){ // 如果当前head为空，就直接放置element
    this.head = node;
  }else{
    // INFO: 当节点的next为null时，即可确定找到链尾
    while(temp.next){ // 循环遍历以找到链尾
      temp = temp.next;
    }
    temp.next = node;
  }
  this.length++;
}

搜寻节点

从头到尾遍历单链条，判断节点是否等于查找的值，相等则返回true，不想等就返回false。

search(element){
  if(!this.head) return false;

  let temp = this.head;
  while(temp){
    if(temp.element === element) return true;

    temp = temp.next
  }
  return false;
}

插入节点

步数(position)为 0 的时候，直接将节点的next指向head，再将节点赋值给this.head。position 不为 0，就遍历到 position 前一个节点插入。

insert(position, element){
  if(position < 0 || position > this.length) return null;

  const node = new Node(element);
  if(position === 0){
    node.next = this.head;
    this.head = node;
  }else{
    let temp = this.head,
        index = 0;
    while(index < position){
      temp = temp.next;
      index++;
    }
    // 插入操作，将待插入节点的next指向当前节点的next
    node.next = temp.next;
    // 然后将当前节点的next指向待插入的节点
    temp.next = node;
  }
  // 长度加一
  this.length++;
}

删除节点

同样是遍历单链表，找到待删的节点，将其删之。需要注意的是，当待删除的节点是head时，需要单独“重定向”head的指向。

remove(element){
  if(!this.head) return;
  if(this.head.element === element){
    this.head = this.head.next;
    this.length--;
    return;
  }
  let curr = this.head,
    prev = this.head;
  while(curr){
    if(curr.element !== element){
      prev = curr;
      curr = curr.next;
    }else{
      prev.next = curr.next;
      this.length--;
      break;
    }
  }
}

双链表

前面的单链表只有一个从头链到尾的方向，而这个双链表则是有两个方向，支持从尾链到头

所以这里双链表里面的单个节点元素跟上面的单链表节点元素就有所不同了：

class Node {
  constructor(element) {
    this.element = element;
    // 前驱指针
    this.prev = null;
    // 后继指针
    this.next = null;
  }
}

双链表的大概样子：

class DoublyLinkedList{
  constructor(){
    // 初始头部节点
    this.head = null;
    // 初始尾部节点
    this.tail = null;
    // 链表的长度
    this.length = 0;
  }

  // 操作
  size(){
    return this.length;
  }
  // 获取链表
  getList(isInverted = false){
    return isInverted ? this.tail : this.head;
  }
  // 清空链表
  clear(){
    this.head = this.tail = null;
    this.length = 0;
  }
  // 链表是否为空
  isEmpty(){
    return this.length === 0;
  }
  // 插入节点
  insert(position, element);
  // 删除链表节点
  removeAt(position){}
  // 寻找链表节点
  search(element){}
}

插入节点

这里需要画个图来辅助下理解了。首先初始化一个待插入的节点，遍历到链表的position的前一个位置节点，在该节点位置插入待插入的节点，处理好周围三个节点的前后指针。

insert(position, element){
  if(position < 0 || position > this.length) return null;

  const node = new Node(element);

  if(!this.head){
    this.head = this.tail = node;
  }else if(position === 0){ // 插入节点是0的话，就需要调整head指向
    node.next = this.head;
    this.head.prev = node;
    // head指向新的头节点
    this.head = node;
  }else if(position === this.length){ // 是尾部
    this.tail.next = node;
    node.prev = this.tail;
    // tail重定向
    this.tail = node;
  }else {

    let temp = this.head,
      index = 0;

    while(index < position){
      temp = temp.next;
      index++;
    }
    temp.prev.next = node;
    node.prev = temp.prev;
    temp.prev = node;
    node.next = temp;
  }
  this.length++;
}

删除节点

这里跟单链表类似，先遍历链表，找到需要删除的节点后，将周围的节点的prev和next重定向。

removeAt(position){
  if(!this.length || position < 0 || position > this.length - 1) return null;

  let temp = this.head, index = 0;

  if(this.length === 1){ // 如果仅有一个节点
    this.clear();
  }else if(position === 0){
    this.head.next.prev = null;
    this.head = this.head.next;
  }else if(position === this.length - 1){
    this.tail.prev.next = null;
    this.tail = this.tail.prev;
  }else{
    while(index < position){
      temp = temp.next;
      index ++;
    }
    temp.prev.next = temp.next;
    temp.next.prev = temp.prev;
  }
  this.length--;
  return temp.element;
}

搜索节点

跟单链表类似，从头至尾遍历链表，找到元素返回true，否则返回false。

search(element){
  let temp = this.head;
  while(temp){
    if(temp.element === element) return true;
    temp = temp.next;
  }
  return false;
}

做道小题

leetcode21.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

// Definition for singly-linked list.
// 节点
class ListNode {
  constructor(val){
    this.val = val;
    this.next = null;
  }
}

我最开始的方法

var mergeTwoLists = function(l1, l2) {
  let res = new List();
  while (l1 !== null && l2 !== null) {
    if (l1.element < l2.element) {
      res.append(l1.element);
      l1 = l1.next;
    } else {
      res.append(l2.element);
      l2 = l2.next;
    }
  }
  let temp = !l1 ? l2 : l1;
  while (temp) {
    res.append(temp.element);
    temp = temp.next;
  }
  return res;
};

还有更优雅的使用递归的方式

var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l2.next, l1);
    return l2;
  }
}

关注本人公众号

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

数据结构——链表.md

数据结构——链表.md

链表

简单说几句

今天的主角——链表

单链表

单链表在js中的实现

双链表

做道小题

Files

数据结构——链表.md

Latest commit

History

数据结构——链表.md

File metadata and controls

链表

简单说几句

今天的主角——链表

单链表

单链表在js中的实现

双链表

做道小题