奉贤建设机械网站制作网络营销推广的要点及注意事项

当前位置： 首页 > news >正文

奉贤建设机械网站制作,网络营销推广的要点及注意事项,一小时学做网站,百度搜索风云排行榜文章目录一#xff1a;链表的类型单链表双链表循环链表二#xff1a;链表的存储方式三#xff1a;链表的定义删除节点添加节点四#xff1a;实战练习1.设计链表2. 移除链表元素最后说一句一#xff1a;链表的类型 单链表 什么是链表#xff0c;链表是一种通过指针串联在… 文章目录一链表的类型单链表双链表循环链表二链表的存储方式三链表的定义删除节点添加节点四实战练习1.设计链表2. 移除链表元素最后说一句一链表的类型 单链表 什么是链表链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。 链表的入口节点称为链表的头结点也就是head。 如图所示
双链表 单链表中的指针域只能指向节点的下一个节点。 双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。 双链表 既可以向前查询也可以向后查询。 如图所示
循环链表 循环链表顾名思义就是链表首尾相连。 循环链表可以用来解决约瑟夫环问题。 二链表的存储方式 了解完链表的类型再来说一说链表在内存中的存储方式。 数组是在内存中是连续分布的但是链表在内存中可不是连续分布的。 链表是通过指针域的指针链接在内存中各个节点。 所以链表中的节点在内存中不是连续分布的 而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。 如图所示 这个链表起始节点为2 终止节点为7 各个节点分布在内存的不同地址空间上通过指针串联在一起。 三链表的定义 public class ListNode {// 结点的值int val;// 下一个结点ListNode next;// 节点的构造函数(无参)public ListNode() {}// 节点的构造函数(有一个参数)public ListNode(int val) {this.val val;}// 节点的构造函数(有两个参数)public ListNode(int val, ListNode next) {this.val val;this.next next;} }删除节点 删除D节点如图所示 只要将C节点的next指针 指向E节点就可以了。 添加节点 如图所示 可以看出链表的增添和删除都是O(1)操作也不会影响到其他节点。 但是要注意要是删除第五个节点需要从头节点查找到第四个节点通过next指针进行删除操作查找的时间复杂度是O(n)。 四实战练习 1.设计链表 力扣链接 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性val 和 next。val 是当前节点的值next 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。 在链表类中实现这些功能 get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。 addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。 addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。 addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。 deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。 示例 MyLinkedList linkedList new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1- 2- 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1- 3 linkedList.get(1); //返回3 //单链表 class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.valval;} } class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size 0;head new ListNode(0);}//获取第index个节点的数值注意index是从0开始的第0个节点就是头结点public int get(int index) {//如果index非法返回-1if (index 0 || index size) {return -1;}ListNode currentNode head;//包含一个虚拟头节点所以查找第 index1 个节点for (int i 0; i index; i) {currentNode currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点等价于在(末尾1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度则返回空public void addAtIndex(int index, int val) {if (index size) {return;}if (index 0) {index 0;}size;//找到要插入节点的前驱ListNode pred head;for (int i 0; i index; i) {pred pred.next;}ListNode toAdd new ListNode(val);toAdd.next pred.next;pred.next toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index 0 || index size) {return;}size–;if (index 0) {head head.next;return;}ListNode pred head;for (int i 0; i index ; i) {pred pred.next;}pred.next pred.next.next;} }2. 移除链表元素 力扣链接 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [], val 1 输出[] 也可以用迭代的方法删除链表中所有节点值等于特定值的节点。 用temp表示当前节点。如果temp的下一个节点不为空且下一个节点的节点值等于给定的val则需要删除下一个节点。删除下一个节点可以通过以下做法实现: temp.nect temp.neat.next 如果temp的下一个节点的节点值不等于给定的val则保留下一个节点将temp移动到下一个节点即可。 当temp的下一个节点为空时链表遍历结束此时所有节点值等于val的节点都被删除。 具体实现方面由于链表的头节点head有可能需要被删除因此创建哑节点dummgHead令dummgHead.next head初始化 temp dummyHead然后遍历链表进行删除操作。最终返回dummyHead.next 即为删除操作后的头节点。 class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode temp dummyHead;while (temp.next ! null) {if (temp.next.val val) {temp.next temp.next.next;} else {temp temp.next;}}return dummyHead.next;} }最后说一句 感谢大家的阅读文章通过网络资源与自己的学习过程整理出来希望能帮助到大家。 才疏学浅难免会有纰漏如果你发现了错误的地方可以提出来我会对其加以修改。