前言
最近被小伙伴问到链表是什么, 链表作为一种常见的数据结构, 但是很多前端 coder 对此并不了解, 写下这篇文章, 介绍下链表的 JS 实现, 不了解链表的同学也可以做个参考
单向链表
和数组区别, 地址离散. 它在内存地址中可以离散的分配, 由于它是离散的分配, 所以他可以省去很多的麻烦, 不像数组由于预留空间不足经常需要拷贝, 分配新的内存地址
总体上还是线性的数据, 属于链式的排列
程序表示
. 表示一个节点 node ...JS function ListNode(key){ // 节点就单纯是一个数据结构, 不需要其他方法 this.key = key; // 传入的 key this.next = null; // 初始化时, 下一个节点指向 null }
- 表示单向链表
- ```JS
- class LinkedList {
- // 使用 class, 可以添加其他方法
- constructor(){
- this.head = null; // 初始化时, 头指针指向 null
- }
- }
向空链表中插入元素
创建一个空链表, HEAD 指针指向 NULL
const list = new LinkedList()
创建一个包含数据 1 的节点
const node = new ListNode(1)
将 HEAD 指针指向节点
list.head = node;
当前链表结构
- LinkedList {
- head: ListNode {
- key: 1,
- next: null
- }
- }
再插入一个元素 2
再创建一个包含数据 2 的节点
const node2 = new ListNode(2)
将节点 2 的 next 指针指向节点 1
node2.next = node;
调整 HEAD 指针指向节点 2
list.head = node2;
当前链表结构
- LinkedList {
- head: ListNode {
- key: 2,
- next: ListNode {
- key: 1,
- next: null
- }
- }
- }
插入的完整程序 (时间复杂度 O(1))
当头指针不为 null 时, 新插入的节点的 next 指针首先指向头指针指向的节点, 然后将头指针指向插入的节点
- class LinkedList {
- constructor(){
- this.head = null;
- }
- insert(node){
- if(this.head !== null){
- node.next = this.head
- }
- this.head = node;
- }
- }
在链表中查找节点(时间复杂度 O(n))
- class LinkedList {
- ...
- find(node){
- let p = this.head; // 创建一个遍历指针
- while(p && p !== node){
- // 当 p 为 null 或者 p 为 node 时, 停止遍历
- p = p.next;
- }
- return p; // 如果 node 在链表中, p = node, 否则返回 null
- }
- }
已知节点 2, 删除节点 2
找到节点 2 之前的节点 prev 这是一个 O(n)的操作
prev.next = node2.next;
双向链表图示
双向链表(Double Linked-List)
追加(append/push) - O(1)
索引 访问 / 修改 (A[idx] = ...) - O(n)
插入 (insert) - O(1)
删除 (delete/remove) - O(1)
合并 (merge/concat) - O(1)
从 API 上看, 链表比数组 在索引上变慢了, 但是在插入, 删除, 合并上都变快了
双向链表程序
表示一个链表节点
- function ListNode(key){
- this.key = key;
- this.prev = null;
- this.next= null;
- }
表示双向链表
- class DoubleLinkedList {
- constructor(){
- this.head = null;
- }
- }
双向链表删除元素 2 (时间复杂度 O(1))
节点 2 的前一个节点 (节点 1) 的 next 指针指向节点 2 的下一个节点(节点 3)
node2.prev.next = node2.next
节点 2 的下一个节点 (节点 2) 的 prev 指针指向节点 2 的上一个节点(节点 1)
node2.next.prev = node2.prev;
删除节点 2 的指针, 减少引用计数
- delete node2.next;
- delete node2.prev
双向链表的插入 - O(1)
- insert(node) {
- if(!(node instanceof ListNode)){
- node = new ListNode(node);
- }
- if (this.tail === null) {
- this.tail = node;
- }
- if (this.head !== null) {
- this.head.prev = node;
- node.next = this.head;
- }
- this.head = node;
- }
双向链表的合并 - O(m+n)
为了让合并操作可以在 O(1)完成, 除了头指针 head 外, 还需要维护一个尾指针 tail.
- merge(list) {
- this.tail.next = list.head;
- list.head.prev = this.tail;
- this.tail = list.tail;
- }
打印双向链表
- print() {
- let str = '';
- let p = this.head
- while (p !== null) {
- str += p.key + '<->';
- p = p.next;
- }
- console.log(str += 'NULL');
- }
完整代码
- class DoubleLinkedList {
- constructor() {
- this.head = null;
- this.tail = null;
- }
- print() {
- let str = '';
- let p = this.head
- while (p !== null) {
- str += p.key + '<->';
- p = p.next;
- }
- console.log(str += 'NULL');
- }
- insert(node) {
- if(!(node instanceof ListNode)){
- node = new ListNode(node);
- }
- if (this.tail === null) {
- this.tail = node;
- }
- if (this.head !== null) {
- this.head.prev = node;
- node.next = this.head;
- }
- this.head = node;
- }
- merge(list) {
- this.tail.next = list.head;
- list.head.prev = this.tail;
- this.tail = list.tail;
- }
- }
- class ListNode {
- constructor(key) {
- this.prev = null
- this.next = null
- this.key = key
- }
- }
- const list = new DoubleLinkedList()
- list.print()
- // 输出: NULL
- for (let i = 0; i <5; i++) {
- list.insert(String.fromCharCode('A'.charCodeAt(0) + i))
- }
- list.print()
- // 输出: E<->D<->C<->B<->A<->NULL
- list.insert('X')
- list.print()
- // 输出: X<->E<->D<->C<->B<->A<->NULL
- const list2 = new DoubleLinkedList()
- list2.insert('Q')
- list2.insert('P')
- list2.insert('O')
- list2.print()
- // 输出 O<->P<->Q<->NULL
- list2.merge(list)
- list2.print()
- // 输出 O<->P<->Q<->X<->E<->D<->C<->B<->A<->NULL
扩展方法
在链表的使用中, 经常要用到一些方法, 让我们来实现它吧
翻转单向链表
- class List {
- ...
- reverse(p = this.head){
- if(p.next){
- reverse(p.next);
- p.next.next = p;
- p.next = null
- }else{
- this.head = p;
- }
- }
- }
写一个函数 center(list)找到一个链表的中间节点. 如果链表有基数个节点, 那么返回中心节点. 如果链表有偶数个节点, 返回中间偏左的节点.
- // 解法一: 空间复杂度高 O(n) 时间复杂度 O(n)
- const center = (list)=>{
- let p = list.head
- const arr = []
- while(p){
- arr.push(p)
- p = p.next;
- }
- return arr.length % 2 ? arr[~~(arr.length/2)] : arr[arr.length/2-1]
- }
- // 解法二 时间复杂度 O(n)
- const center = (list)=>{
- let p = list.head
- if(p==null) return null
- let count = 0
- while(p){
- count++;
- p = p.next;
- }
- count = count % 2 ? ~~(count/2) : count/2-1
- p = list.head;
- while(count){
- count--
- p = p.next;
- }
- return p
- }
- // 解法三
- function center(list) {
- let fast = list.head, // 快指针, 每次移动两个
- slow = list.head // 慢指针, 每次移动一个
- while(fast) {
- fast = fast.next
- fast && (fast = fast.next)
- fast && (fast = fast.next)
- fast && (slow = slow.next)
- }
- return slow
- }
- const list = new DoubleLinkedList()
- console.log(center(list) )// null
- list.insert(4)
- list.insert(3)
- list.insert(2)
- list.insert(1)
- // list = 1-2-3-4
- const node = center(list) // node.key = 2
- console.log(node)
- list.insert(5)
- // list = 5-1-2-3-4
- const node2 = center(list) // node.key = 2
- console.log(node2)
结语
个人能力有限, 如有错误, 请指出.
如果能给您的代码之路增加点帮助, 点个赞吧
来源: https://juejin.im/post/5bf99f5e5188256d9832bb6d