首页 > 其他分享 >链表-循环链表

链表-循环链表

时间：2024-06-08 19:22:21浏览次数：6  
标签：current head index next 链表 循环 element

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于

最后一个元素指向下一个元素的指针（tail.next）不是引用undefined，而是指向第一个元素（head).

  • 单链表: this.tail.next = this.head;
  • 双向链表: this.tail.next = this.head; this.head.prev = this.tail;

这里简化演示就单向链表的方式来操作即可;

链表初始化

// 节点类
class Node {
  constructor(element) {
    this.element = element; 
    this.next = undefined; 
  }
}


// 链表类
class CicularLinkedList {
  constructor() {
    this.count = 0; 
    this.head = null; 
  }

  size() {
    return this.count
  }

  toString() {
    if (this.head == null) return undefined
    let str = `${this.head.element}`
    let current = this.head.next 
    for (let i = 1; i < this.count; i++) {
      str = `${str}, ${current.element}`
      current = current.next 
    }
  }

  getElementAt(index) {
    if (index < 0 || index > this.count) return undefined
    let node = this.head; 
    for (let i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }

  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      if (current.element == element) return i;
      current = current.next; 
    }
    return -1;
  }
  
}

在任意位置插入元素

  • 头结点插入
    • 空链表, 自循环
    • 非空链表, 记得通过 getElement() 方法将 tail 元素指向 head
  • 中间或尾部插入, 调整 previous, current 即可
// 在任意位置插入元素
  insert(index, element) {
    if (index < 0 || index > this.count) return false
    const node = new Node(element)
    let current = this.head 

    if (index == 0) {
      // 空链表插入元素, 则自循环呗
      if (this.head == null) {
        this.head = node
        node.next = this.head 
      } else {
        // 记得要将最后一个元素的 next 指向头结点元素
        node.next = current
        this.head = node 

        const tail = this.getElementAt(this.size())
        tail.next = this.head 
      }
    } else {
      // 从中间或者尾部插入, 调整 previous, current  指针即可
      const previous = this.getElementAt(index - 1)
      current = previous.next 

      previous.next = node 
      node.next = current
    }
    // 记得更新链表长度
    this.count++
    return true
  }

和普通链表一样的, 唯一要考虑的就是要将尾节点的 next 连接到头节点

在任意位置删除元素

  • 删除头节点
    • 空链表, 返回 undefined
    • 链表仅一个元素, 让 head ->null 即可
    • 链表有多个元素, 让 head -> 原第二; tail -> 原第二 (现第一)
  • 中间或尾部删, 调整 previous , current 即可
  // 从任意位置删除元素
  removeAt(index) {
    // 越界和空链表检查
    if (index < 0 || index > this.count) return undefined
    if (this.head == null) return undefined

    let current = this.head 
    if (index == 0) {
      if (this.count == 1) {
        // 删除头节点, 且当只有一个元素时, 让 head -> null 即可
        this.head = undefined
      } else {
        // 删除头结点, 后面原来还有多个元素, head -> 原第二, tail -> 原第二(现第一 )
        current = this.head 
        this.head = this.head.next 

        const tail = this.getElementAt(this.count)
        tail.next = this.head.next 
      }
    } else {
      // 删除中间或者尾部元素, 不用常更新 tail
      const previous = this.getElementAt(index - 1)
      current = previous.next 

      previous.next = current.next 
    }
    // 记得更新链表长度
    this.count--
    return current.element
  }

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

}

循环链表-完整实现

// 节点类
class Node {
  constructor(element) {
    this.element = element
    this.next = undefined
  }
}


// 链表类
class CicularLinkedList {
  constructor() {
    this.count = 0
    this.head = null
  }

  size() {
    return this.count
  }

  toString() {
    if (this.head == null) return undefined
    let str = `${this.head.element}`
    let current = this.head.next 
    for (let i = 1; i < this.count; 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; i++) {
      node = node.next
    }
    return node
  }

  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      if (current.element == element) return i
      current = current.next
    }
    return -1
  }

  // 在任意位置插入元素
  insert(index, element) {
    if (index < 0 || index > this.count) return false
    const node = new Node(element)
    let current = this.head 

    if (index == 0) {
      // 空链表插入元素, 则自循环呗
      if (this.head == null) {
        this.head = node
        node.next = this.head 
      } else {
        // 记得要将最后一个元素的 next 指向头结点元素
        node.next = current
        this.head = node 

        const tail = this.getElementAt(this.size())
        tail.next = this.head 
      }
    } else {
      // 从中间或者尾部插入, 调整 previous, current  指针即可
      const previous = this.getElementAt(index - 1)
      current = previous.next 

      previous.next = node 
      node.next = current
    }
    // 记得更新链表长度
    this.count++
    return true
  }

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

    let current = this.head 
    if (index == 0) {
      if (this.count == 1) {
        // 删除头节点, 且当只有一个元素时, 让 head -> null 即可
        this.head = undefined
      } else {
        // 删除头结点, 后面原来还有多个元素, head -> 原第二, tail -> 原第二(现第一 )
        current = this.head 
        this.head = this.head.next 

        const tail = this.getElementAt(this.count)
        tail.next = this.head.next 
      }
    } else {
      // 删除中间或者尾部元素, 不用常更新 tail
      const previous = this.getElementAt(index - 1)
      current = previous.next 

      previous.next = current.next 
    }
    // 记得更新链表长度
    this.count--
    return current.element
  }

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

}


// test 
const list = new CicularLinkedList()

list.insert(0, '111')
console.log('链表是: ', list.toString());

list.insert(1, '222')
console.log('链表是: ', list.toString());

list.insert(2, '333')
console.log('链表是: ', list.toString());

list.insert(list.size(), '444')
console.log('链表是: ', list.toString());

list.insert(0, '555')
console.log('链表是: ', list.toString());
console.log('链表长度是: ', list.size());

console.log('尾元素的 next 是: ', list.getElementAt(list.size() - 1).next.element);

console.log('删除头部元素: ', list.removeAt(0));
console.log('链表是: ', list.toString());
console.log('链表长度是: ', list.size());

console.log('删除位置 1 的元素: ', list.removeAt(1));
console.log('链表是: ', list.toString());
console.log('链表长度是: ', list.size());

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

测试结果如下:

PS E:\Front_Mook\projects\shop-admin> node test.js
链表是:  111
链表是:  111, 222
链表是:  111, 222, 333
链表是:  111, 222, 333, 444
链表是:  555, 111, 222, 333, 444
链表长度是:  5
尾元素的 next 是:  555
删除头部元素:  555
链表是:  111, 222, 333, 444
链表长度是:  4
删除位置 1 的元素:  222
链表是:  111, 333, 444
链表长度是:  3
删除尾部部元素:  444
链表是:  111, 333
链表长度是:  2

至次, 循环链表也基本理解差不多了, 还是比较容易实现的, 通过形象化的想象出来.

标签：current,head,index,next,链表,循环,element
From： https://www.cnblogs.com/chenjieyouge/p/18238873

相关文章

  • 代码随想录算法训练营第四天 Leetcode 24 两两交换链表节点 Leetcode19 删除链表倒数
    链表问题首先要记住设置虚拟头节点Leetcode24两两交换链表节点题目链接思路：就是简单模拟两两交换 要注意链表节点的处理一定要获取到合适的位置比如：这一题中两个交换节点的前一个节点注意链表保存临时节点/***Definitionforsingly-linkedlist.*publicclas......
  • 浙江大学蒋明凯研究员《Nature》正刊最新成果！揭示生态系统磷循环响应大气二氧化碳浓度
    随着大气二氧化碳浓度的升高，陆地生态系统固存额外碳汇的能力取决于土壤养分的可利用性。前期的研究证据表明，在土壤低磷环境下，大气二氧化碳浓度的升高可以提升成熟森林的光合速率，但是没有产生额外生物量固碳。热带和亚热带森林的生产力普遍受到土壤磷元素可用性的限制，但是生态系......
  • 顺序表、链表、栈和队列总结
    目录顺序表链表栈队列总结补充顺序表实现链表实现栈实现队列实现  顺序表、链表、栈和队列都是线性数据结构，但它们在管理和访问数据方面有不同的特点和用途。以下是它们之间的主要区别：顺序表存储方式：在连续的内存空间中存储元素。访问方式：通过索引直接访......
  • 链表-双向链表
    之前实现的是单向链表,即每个节点有一个元素值和一个指向下一个元素的指针,是单向的.head->a->b->c1.现在来做一个双向的,即对每个节点来说,有两个指针,一个链向下一个元素,另一个链向上一个元素.head-><-b-><-c.链表初始化基本的操作套路和单链表是差不多的......
  • 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......
  • 循环
    一、for循环： 1.遍历字符串中的每个字符：示例：str="abcdferfd"foriinstr:#此处i为临时变量名，可以任意起名x,y.....print(i)#单独输出每一个字母*注：可在括号内i后加上,end=''，意为连续输入不换行（python中的print()等同于java中的printly()，......
  • ＜PLC＞＜工控＞使用汇川PLC控制SV630N伺服驱动的循环运动程序（附PLC程序）
    前言本系列是关于PLC相关的博文，包括PLC编程、PLC与上位机通讯、PLC与下位驱动、仪器仪表等通讯、PLC指令解析等相关内容。PLC品牌包括但不限于西门子、三菱等国外品牌，汇川、信捷等国内品牌。除了PLC为主要内容外，PLC相关元器件如触摸屏（HMI）、交换机等工控产品，如果有值得记......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99