JS专题系列之手摸手彻底了解链表操作

前言

1、什么是链表？

官方解释:

链表是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现,常见的链表有: 单向链表、双向链表、循环链表、反向链表

通俗解释：

链表其实就是一个俄罗斯套娃,一层套着一层，拿掉第一层可以找到第二层,....依次类推

0.png

2、数组特点

数组是顺序存储结构

数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间，比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了

插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动，比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上

随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据

3、链表特点

在内存中可以存在任何地方，不要求连续

每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据

链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充

查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起

4、总结：

数组：

1、随机访问性强

2、查找速度快

链表：

1、插入删除速度快

2、内存利用率高

3、拓展很灵活

一、单向链表

1.png

特点:

用一组任意的内存空间去存储数据元素（这里的内存空间可以是连续的，也可以是不连续的）

每个节点(node)都由数据本身和一个指向后续节点的指针组成

整个链表的存取必须从头指针开始，头指针指向第一个节点

最后一个节点的指针指向空（NULL）

链表中的主要操作:

创建节点

插入节点

查找节点

删除节点

1、创建节点

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

2、尾部插入节点

尾部插入节点我们只需要考虑2点

链表中head是否存在如果不存在代表插入的节点是第一个

如果存在则则找最后一个节点，将最后一个节点的next指向插入的节点

// 尾部插入   this.tail的作用就是用来保存最后一个节点
append(data) {
    let listNode = new ListNode(data);
    if (this.head) {
        this.tail.next = listNode;
        this.tail = listNode;
    } else {
        this.head = listNode;
        this.tail = listNode;
    }
    this.length++;
    return true;
}

3、获取节点

此方法很重要，因为删除和添加都需要用到此方法.另外链表的缺陷也在此方法中体现了出来

如果index等于0则直接返回head

如果index不等于0则需要通过while循环找到对应的节点

getNode(index) {
    if (index < 0 || index > this.length) {
        return false;
    } else {
        if (index === 0) {
            return this.head;
        } else {
            let current_index = 0;
            let current_node = this.head;
            while (current_index < index) {
                current_index += 1;
                current_node = current_node.next;
            }
            return current_node;
        }
    }
}

4、插入节点

如果index的值等于this.length的值则代表需要插入到最后，直接调用尾部插入即可

如果index等于0则需要将head节点赋值给插入节点的next，插入节点赋值给head

如果index不等于0则需要获取到插入位置的prevNode和nextNode,然后将插入节点的next等于nextNode，prevNode的next等于插入节点

2.png

insert(index, data) {
    if (index < 0 || index > this.length) {
        return fase;
    } else if (index === this.length) {
        this.append(data);
    } else {
        let listNode = new ListNode(data);
        if (index === 0) {
            listNode.next = this.head;
            this.head = listNode;
        } else {
            const nextNode = this.getNode(index);
            const prevNode = this.getNode(index - 1);
            listNode.next = nextNode;
            prevNode.next = listNode;
        }

        this.length += 1;
        return true;
    }
}

5、删除节点

如果index等于0则将head值改为head.next

如果index不等于0则需要获取到删除节点的prevNode和nextNode，将nextNode赋值给prevNode的next

3.png

remove(index) {
    if (index < 0 || index > this.length) {
        return false;
    } else if (index === 0) {
        this.head = this.head.next;
        this.length -= 1;
    } else {
        const nextNode = this.getNode(index).next;
        const prevNode = this.getNode(index - 1);
        prevNode.next = nextNode;
        this.length -= 1;
    }
}

6、获取节点数据

同理获取节点

get(index) {
    if (index < 0 || index > this.length) {
        return false;
    } else {
        if (index === 0) {
            return this.head.data;
        } else {
            let current_index = 0;
            let current_node = this.head;
            while (current_index < index) {
                current_index += 1;
                current_node = current_node.next;
            }
            return current_node.data;
        }
    }
}

7、完整版代码

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

  class List {
    constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
    }
    /*
        尾部插入
    */
    append(data) {
      let listNode = new ListNode(data);
      if (this.head) {
        this.tail.next = listNode;
        this.tail = listNode;
      } else {
        this.head = listNode;
        this.tail = listNode;
      }
      this.length++;
      return true;
    }

    /*
        获取节点
    */
    getNode(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else {
        if (index === 0) {
          return this.head;
        } else {
          let current_index = 0;
          let current_node = this.head;
          while (current_index < index) {
            current_index += 1;
            current_node = current_node.next;
          }
          return current_node;
        }
      }
    }
    /*
        插入
    */
    insert(index, data) {
      if (index < 0 || index > this.length) {
        return fase;
      } else if (index === this.length) {
        this.append(data);
      } else {
        let listNode = new ListNode(data);
        if (index === 0) {
          listNode.next = this.head;
          this.head = listNode;
        } else {
          const nextNode = this.getNode(index);
          const prevNode = this.getNode(index - 1);
          listNode.next = nextNode;
          prevInsertNode.next = listNode;
        }

        this.length += 1;
        return true;
      }
    }

    /*
        移除
    */
    remove(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else if (index === 0) {
        this.head = this.head.next;
        this.length -= 1;
      } else {
        const nextNode = this.getNode(index).next;
        const prevNode = this.getNode(index - 1);
        prevNode.next = nextNode;
        this.length -= 1;
      }
    }

    /*
        获取节点数据
    */
    get(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else {
        if (index === 0) {
          return this.head.data;
        } else {
          let current_index = 0;
          let current_node = this.head;
          while (current_index < index) {
            current_index += 1;
            current_node = current_node.next;
          }
          return current_node.data;
        }
      }
    }
  }

二、双向链表

双向链表其实就是多了一个指向上一个节点的指针，不管删除还是添加时刻记得改变prev的指向即可.其他逻辑和单向链表一致

1、完整代码

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

  class List {
    constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
    }
    /*
        尾部插入
    */
    append(data) {
      let listNode = new ListNode(data);
      if (this.head) {
        this.tail.next = listNode;
        listNode.prev = this.tail;
        this.tail = listNode;
      } else {
        this.head = listNode;
        this.tail = listNode;
      }
      this.length++;
      return true;
    }

    /*
        获取节点
    */
    getNode(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else {
        if (index === 0) {
          return this.head;
        } else {
          let current_index = 0;
          let current_node = this.head;
          while (current_index < index) {
            current_index += 1;
            current_node = current_node.next;
          }
          return current_node;
        }
      }
    }
    /*
        插入
    */
    insert(index, data) {
      if (index < 0 || index > this.length) {
        return fase;
      } else if (index === this.length) {
        this.append(data);
      } else {
        let listNode = new ListNode(data);
        if (index === 0) {
          listNode.next = this.head;
          this.head.prev = listNode;
          this.head = listNode;
        } else {
          const nextNode = this.getNode(index);
          const prevNode = this.getNode(index - 1);
          listNode.next = nextNode;
          listNode.prev = prevNode;
          nextNode.prev = listNode;
          prevNode.next = listNode;
        }

        this.length += 1;
        return true;
      }
    }

    /*
        移除
    */
    remove(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else if (index === 0) {
        this.head.next.prev = null;
        this.head = this.head.next;
        this.length -= 1;
      } else {
        const nextNode = this.getNode(index).next;
        const prevNode = this.getNode(index - 1);
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        this.length -= 1;
      }
    }

    /*
        获取节点数据
    */
    get(index) {
      if (index < 0 || index > this.length) {
        return false;
      } else {
        if (index === 0) {
          return this.head.data;
        } else {
          let current_index = 0;
          let current_node = this.head;
          while (current_index < index) {
            current_index += 1;
            current_node = current_node.next;
          }
          return current_node.data;
        }
      }
    }
  }

三、反转链表

什么是反转链表? 假设套娃的顺序是1<2<3<4,那么反转也就是4<3<2<1。实现反转的方法有2种

迭代法：就是需要定义三个节点指针，一个指向当前节点，一个指向前面一个节点，一个指向后面一个节点，反转就是说，当前节点的next指针指向前面一个节点

递归：递归方法就是你不会反转当前链表，让递归方法先帮你反转当前节点的下一个节点开始的单链表，把反转后的头节点返回。你再将当前头节点连接到返回头节点的尾部

4.png

一、迭代法

class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  let node1 = new Node(1);
  let node2 = new Node(2);
  let node3 = new Node(3);
  let node4 = new Node(4);
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = null;
// 核心
  function reverse(node) {
    if (!node) {
      return null;
    }
    let curr_node = node;
    let pre_node = null;
    while (curr_node) {
      // 获取下一个节点,用来更改current_node的值,遍历所有的节点
      let next_node = curr_node.next;
      // 将当前节点的next指向上一次的current_node,如果第一次遍历则指向null
      curr_node.next = pre_node;
      // 保存当前current_node的节点
      pre_node = curr_node;
      // 进行下一次遍历
      curr_node = next_node;
    }
    return pre_node;
  }


  let node = reverse(node1);
  console.log(node);

5.png

二、递归

function reverse_digui(node) {
    if (!node) {
      return null;
    }
    if (node.next == null) {
      return node;
    }
    let new_head = reverse_digui(node.next);
    node.next.next = node;
    node.next = null;
    return new_head;
  }

最后编辑于：2021.01.14 18:13:21

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,427评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,551评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,747评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,939评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,955评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,737评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,448评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,352评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,834评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,992评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,133评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,815评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,477评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,022评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,147评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,398评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,077评论 2赞 355

JS专题系列之手摸手彻底了解链表操作

前言

一、单向链表

1、创建节点

2、尾部插入节点

3、获取节点

4、插入节点

5、删除节点

6、获取节点数据

7、完整版代码

二、双向链表

1、完整代码

三、反转链表

一、迭代法

二、递归

推荐阅读更多精彩内容