首页 > 其他分享 >链表-双向链表

链表-双向链表

时间：2024-06-07 23:33:32浏览次数：20  
标签：node current 元素 next 链表 tail 双向

之前实现的是单向链表, 即每个节点有一个元素值和一个指向下一个元素的指针, 是单向的. head ->a ->b ->c1.

现在来做一个双向的, 即对每个节点来说, 有两个指针, 一个链向下一个元素, 另一个链向上一个元素. head -> <- b -> <- c.

链表初始化

基本的操作套路和单链表是差不多的啦.

// 节点类
class Node {
  constructor(element, next = null, prev = null) {
    this.element = element
    this.next = next
    // 新增
    this.prev = prev 

  }
}


// 链表类
class doublyLinkedList {
  constructor() {
    this.count = 0           // 链表大小
    this.head = undefined    // 指向头节点元素
    this.tail = undefined    // 指向尾节点元素
  }
}

公共方法

链表的长度, 查询头, 尾元素, 打印链表, 根据元素值查索引, 根据索引查询值等链表公用方法.

// 链表长度
size() {
    return this.count
}

getHead() {
    return this.head
}

getTail() {
    return this.tail
}

// 将链表节点元素以字符串形式打印
toString() {
    if (this.head == null) return undefined
    
    let str = `${this.head.element}`
    let current = this.head.next
    for (let i = 1; i < this.count && current != null; i++) {
        str = `${str}, ${currrent.element}`
        current = current.next
    }
    return str
}	

// 查询元素的索引
indexOf(element) {
    let current = this.head
    for (let i = 0; i < index && current != null; i++) {
        if (current.element == element) return i
        current = current.next
    }
    // 没找到则返回 -1
    return -1
}


// 根据索引返回对应节点
getElementAt(index) {
    if (index < 0 || index > this.count) return undefined
    let node = this.head
    for (let i = 0; i < index && node != null; i++) {
        node = node.next
    }
    return node
}

从任意位置插入元素

  • 头部插入
    • 空链表, 让 head, tail 指针都指向目标元素 node
    • 非空链表, 让 node 变成首元素 (前插)
  • 尾部插入, 通过 tail 先定位到尾部元素, 然后追加 node, 要记得 prev 指向
  • 中间插入, 找出目标元素的前后元素进行断链, 插入, 再链接
// 从任意位置插入元素
insert(index, element) {
    // 越界检查
    if (index < 0 || index > this.count) return false
    const node = new Node(element)
    let current = this.head  // 让 current 默认指向头节点
    
    if (index == 0) {
        // 链首插入
        if (this.head == null) {
            // 空链表则让 head, tail 都指向 node 即可
            this.head = node
            this.tail = node
        } else {
            // 头结点有值时, 则让 node 前插
            node.next = current
            current.prev = node
            this.head = node
            
        } else if (inde == this.count) {
            // 尾部插入, 通过 tail 定位到尾部元素, 然后追加 node
            current = this.tail
            current.next = node
            node.prev = current
            this.tail = node
            
        } else {
            // 中间插入, 调整 previous, current 关系即可
            current = this.getElementAt(index)
            previous = current.prev
            
            previous.next = node
            node.prev = previous
            
            node.next = current
            current.prev = node
        }
    }
    // 记得要更新链表长度
    this.count++
    return true
}

关键就是要能在脑海里想象出这个节点, 链接的画面就很轻松写出来了.

从任意位置删除元素

  • 头节点删
    • 空链表, 返回 false
    • 链表有一个元素, 更新 head, tail
    • 链表多个元素, 将后面"补位"的元素的 prev 指向 null
  • 尾节点删, 通过 tail 定位到尾元素, 让尾元素的 prev 指向 原来的倒2元素, next 则指向 null
  • 从中间删, 对 previous, current, current.next 进行中间跳跃
// 从任意位置删除元素
removeAt(index) {
    // 越界检查, 空链表检查
    if (index < 0 || index > this.count) return false
    if (this.count == 0) return undefined

	let current = this.head  // 老规矩, 让 current 默认指向头节点
	if (index == 0) {
  		// 删除头节点, 则让 this.head -> this.head.next 即可
        this.head = current.next
        // 如果链表只有一个元素, 则让 tail -> null
        if (this.count == 1) {
            this.tail = null
        } else {
            // 链表有多个元素, 后面补位的 prev 则指向 null
            current.next.prev = null
        }

    } else if (index == this.count - 1) {
        // 删除尾节点, 定位到尾节点, 让原来到倒2元素变成尾节点即可
        current = this.tail
        this.tail = current.prev
        current.prev.next = null 
        
    } else {
        // 删除中间节点, 让 previous 越过 current 指向 current.next 即可
        current = this.getElementAt(index)
		const previous = current.prev
		
		previous.next = current.next
		current.next.prev = previous
		
    }
	// 还是要记得更新链表长度
	this.count--
	return current.element
    
}

// 顺带根据 indexOf(element) 实现 remove(element) 方法
remove(element) {
    const index = indexOf(element)
    return this.removeAt(index)
}

感觉这个删除节点好像比增加节点要简单一些呢.

完整实现

// 节点类
class Node {
  constructor(element) {
    this.element = element
    this.next = null
    // 新增
    this.prev = null 

  }
}

// 链表类
class doublyLinkedList {
  constructor() {
    this.count = 0           // 链表大小
    this.head = undefined    // 指向头节点元素
    this.tail = undefined    // 指向尾节点元素
  }

  size() {
    return this.count
  }

  getHead() {
    return this.head.element
  }

  getTail() {
    return this.tail.element
  }

  // 将元素的值用字符串形式打印出来
  toString() {
    if (this.head == null) return undefined

    let str = `${this.head.element}`
    let current = this.head.next
    // 遍历节点将元素连接起来
    for (let i = 1; i < this.count && current != null; i++) {
      str = `${str}, ${current.element}`
      current = current.next
    }
    return str 
  }

  // 根据索引, 查询并返回节点
  getElementAt(index) {
    if (index < 0 || index > this.count) return undefined
    let node = this.head 
    for (let i = 0; i < index && node != null; i++) {
      node = node.next 
    }
    return node 
  }

  // 在任意位置插入元素
  insert(index, element) {
    // 越界检查
    if (index < 0 || index > this.count) return false 
    // 实例化节点对象, 根据位置 (头, 尾, 中间) 分情况处理
    // current 指针在多处会用到, 用来指向目标位置的元素
    const node = new Node(element)
    let current = this.head  
    
    if (index == 0) {
      // 头结点插入, 如果当前是空链表, head, tail 都指向改节点即可
      if (this.head == null) {
        this.head = node
        this.tail = node 
      } else {
        // 头结点插入, 如果当前头结点有值, 则进行前插元素
        node.next = current
        current.prev = node 
        this.head = node 
      }
    } else if (index == this.count) {
      // 尾部插入, 直接通过 tail 定位到尾部元素往后追加 node 即可
      current = this.tail
      current.next = node 
      node.prev = current
      this.tail = node 
    } else {
      // 中间插入则需要用 getElementAt(index) 定位目标前后的元素断链哦
      current = this.getElementAt(index)
      const previous = current.prev
      
      previous.next = node 
      node.prev = previous

      node.next = current
      current.prev = node 
      
    }
    // 不管从哪插, 一定要更新长度
    this.count++
    return true 
  }

  // 从任意位置移除元素
  removeAt(index) {
    // 越界检查, 链表为空检查
    if (index < 0 || index > this.count) return undefined
    if (this.count == 0) return undefined

    let current = this.head
    if (index == 0) {
      // 场景1: 被删的是头节点, 则让 this.head -> current.next 即可
      this.head = current.next
      // 如果只有一个元素, 则要更新 tail 也指向 null 
      if (this.count == 1) {
        this.tail = undefined
      } else {
        // 原来位置为1 的元素已被干掉, 后面补位的元素的 prev 则指向为 null
        current.next.prev = undefined
      }
    } else if (index == this.count -1) {
      // 场景2: 被删的是尾部节点, 直接让 current 通过 tail 找到尾元素操作
      // 让尾元素的 prev 指向原来的倒数第二元素, next 则指向 null 
      current = this.tail 
      this.tail = current.prev  
      current.prev.next = null     
    } else {
      // 场景3: 被删的是中间节点, 则对 previous, current, current.next 中间跳跃
      current = this.getElementAt(index)
      const previous = current.prev 

      previous.next = current.next 
      current.next.prev = previous
      
    }
    // 记得删除元素要更新链表长度哦
    this.count--
    return current.element
  }

  // 查找元素位置
  indexOf(element) {
    let current = this.head 
    for (let i = 0; i < this.count && current != null; i++) {
      if (current.element == element) return i
      // 移动指针
      current = current.next 
    }
    return -1
  }

  // 删除元素
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }
}



// test 
const list = new doublyLinkedList()

list.insert(0, 888)
list.insert(0, 666)
list.insert(0, 111)
list.insert(0, 'first')
console.log('链表元素是:',  list.toString());
console.log('链表长度是: ', list.size())
console.log('tail: ', list.getTail());

console.log('从位置1处添加 999:',  list.insert(1, 999));
console.log('链表元素是:',  list.toString());
console.log('链表长度是: ', list.size());
console.log('tail: ', list.getTail());

console.log('从尾部处添加 nb:',  list.insert(list.size(), 'nb'));
console.log('链表元素是:',  list.toString());
console.log('链表长度是: ', list.size());
console.log('tail: ', list.getTail());

console.log('从头部处添加 nb1:',  list.insert(0, 'nb1'));
console.log('链表元素是:',  list.toString());
console.log('tail: ', list.getTail());

// 删除相关
console.log('从头部删除元素: ', list.removeAt(0));
console.log('链表元素是:',  list.toString());
console.log('tail: ', list.getTail());

console.log('从尾部删除元素: ', list.removeAt(list.size() - 1));
console.log('链表元素是:',  list.toString());
console.log('tail: ', list.getTail());

console.log('从位置 1 处删除元素: ', list.removeAt(1));
console.log('链表元素是:',  list.toString());
console.log('tail: ', list.getTail());

// 查询元素 666 的位置
console.log('查询元素 666 的位置: ', list.indexOf(666));     // 2
console.log('查询元素 hhh 的位置: ', list.indexOf('hhh'));  // -1

// 删除元素
console.log('删除元素 666 : ', list.remove(666));     
console.log('链表元素是:',  list.toString());

console.log('删除元素 hhh : ', list.remove('hhh'));  
console.log('链表元素是:',  list.toString());

测试结果如下:

PS F:\algorithms> node .\double_linked_list.js

链表元素是: first, 111, 666, 888
链表长度是:  4
tail:  888
从位置1处添加 999: true
链表元素是: first, 999, 111, 666, 888
链表长度是:  5
tail:  888
从尾部处添加 nb: true
链表元素是: first, 999, 111, 666, 888, nb     
链表长度是:  6
tail:  nb
从头部处添加 nb1: true
链表元素是: nb1, first, 999, 111, 666, 888, nb
tail:  nb
从头部删除元素:  nb1
链表元素是: first, 999, 111, 666, 888, nb     
tail:  nb
从尾部删除元素:  nb
链表元素是: first, 999, 111, 666, 888
tail:  888
从位置 1 处删除元素:  999
链表元素是: first, 111, 666, 888
tail:  888
查询元素 666 的位置:  2
查询元素 hhh 的位置:  -1
删除元素 666 :  666
链表元素是: first, 111, 888
删除元素 hhh :  undefined
链表元素是: first, 111, 888

至此, 双向链表的基本实现也就搞定啦.

标签：node,current,元素,next,链表,tail,双向
From： https://www.cnblogs.com/chenjieyouge/p/18238041

相关文章

  • day3链表
    题目：https://leetcode.cn/problems/remove-linked-list-elements/submissions/537974263/题目解析：https://programmercarl.com/0203.移除链表元素.html这道题用了dummyHead，会简单非常多，但是需要注意的是，如果不用dummyHead的话，去除head为啥使用while而不是if呢？个人理解是，可......
  • 代码随想录第3天 | 链表 203.移除链表元素，707.设计链表，206.反转链表
    题目：203.移除链表元素思路：主要是头节点的删除问题，一种是直接在原链表上后移头节点设置虚拟头结点，指向原链表的头结点，在设置一个cur指针指向当前节点，虚拟头节点初始化后就不移动了，使用cur进行移动不要忘记释放删除节点的内存，自行设置的虚拟头节点也要释放时间复杂度:O(n)空......
  • 代码随想录训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表
    python定义链表val：数据域，节点存储的元素。next：指针域，指向下一个节点的指针，最后一个节点指向None表示空指针。点击查看代码classListNode:def__init__(self,val,next=None):self.val=valself.next=next203.移除链表元素题目：给你一个链表的......
  • 二叉链表---二叉树的简单实现
    实验内容将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。代码实现#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineElemTypeinttypedefstructBtree{ ElemTypeelem; structBtree*lchild,*rchild......
  • 141. 环形链表
    /***Definitionforsingly-linkedlist.*typeListNodestruct{*Valint*Next*ListNode*}*/funchasCycle(head*ListNode)bool{listMap:=map[*ListNode]struct{}{}forhead!=nil{if_,ok:=listMap[head];ok{......
  • 21. 合并两个有序链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}//创建链表funccreateList(nums[]int)*ListNode{ head:=&ListNode{} tail:=head fori:=0;i<len(nums);i++{ node:=&ListNode{Val:nums[i]} t......
  • 206. 反转链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}funcreverseList(head*ListNode)*ListNode{ varpre*ListNode//前驱节点指针 cur:=head//当前节点指针 forcur!=nil{ next:=cur.Next//临时存储next指针 cur.N......
  • leetcode19删除链表的倒数第 N 个结点
    本文主要讲解删除链表倒数第n个节点的要点与细节c++与java代码如下，末尾本题之前可以尝试leetcode203移除链表元素具体要点：1.首先，单看移除链表节点，核心操作是:cur->next=cur->next->next 即，当前节点cur的下一个节点指向原本的下下个节点小细节：操作时，我们需要得到要......
  • leetcode160相交链表
    本文主要讲解相交链表的要点与细节c++及java代码如下，末尾1.两个链表相交的条件是，两个节点的指针相同，而不是元素值相同，即if(a==b)returna; 2.·既然要找到相交的点，那么相交之后，两个链表就完全一样了（后续长度和数值），那么我们就要不断同步更新headA和headB的临时指针，直到......
  • 【C++进阶】深入STL之list：高效双向链表的使用技巧
    ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99