头部和尾部堵塞方法
HashMap在JDK1.8为什么改用使用尾插法
因为 1.7头插法扩容时,头插法会使链表发生反转,多线程环境下会产生环;
A 线程在插入节点 B,B 线程也在插入,遇到容量不够开始扩容,重新 hash,放置元素,采用头插法,后遍历到的 B 节点放入了头部,这样形成了环。
1、假设容器大小为2,数组0 的链表上初始有个 A节点。A线程和B线程同时插入B节点。
2、B线程cup占用、头指针指向A节点后 cup被A线程占用。
3、A线程插入节点B时,刚好hash 到数组0,则该链表 为 B —> A。
4、B线程 插入节点B时,发现内存不够,进行resize扩容操作,恰巧节点rehash后也是在同一个位置上。该方法实现的机制就是将每个链表转化到新链表,并且链表中的位置发生反转(链表转置)。现在为 A —> B。
5、B实现插入节点B操作后就形成了环。
以上参考自:https://blog.****.net/weixin_42373997/article/details/112085344?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_baidulandingword-0&spm=1001.2101.3001.4242、https://blog.****.net/****_1107/article/details/108236495
以下转载自:https://blog.****.net/qq_40938077/article/details/80216563
方法1:头插法
基本思路:
定义一个链表类型的指针l,指针l指向的是链表的首地址,而不是链表的第一个数,指针l指向的下一个链表类型才是链表的第一个数,每次往链表中加数都加到链表中的第1个位置(即指针l指向的位置)。
代码:
最好自己看代码在纸上模拟一下过程
#include<bits/stdc++.h> using namespace std typedef struct Node { int value; struct Node *next; }node,*linkedlist; linkedlist linkedlistcreath()//返回的是该链表的地址 { node *l=(node*)malloc(sizeof(node)); l->next=NULL; int number; while (scanf("%d",&number)!=EOF) { node *p=(node*)malloc(sizeof(node));//新建一个node结构并为其申请空间 p->value=number;//给新建的node结构赋值 p->next=l->next;//赋值p所指的节点(就是l所指的节点,即链表的第2个节点) l->next=p;//将l所指的节点更新为p点 } return l;//返回头节点地址 }
方法2:尾插法
基本思路:
还是先定义一个链表类型的指针l,指针l指向的是链表的首地址,而不是链表的第一个数,指针l指向的下一个链表类型才是链表的第一个数,然后定义一个r指针,保证r指针始终指向链表的最后一个位置上的节点,然后让新加的节点加入到r指针指向的节点的后面。
代码如下:
最好自己看代码在纸上模拟一下过程
#include<bits/stdc++.h> using namespace std; typedef struct Node { int value; struct Node *next; } node,*linkedlist; linkedlist linkedlistcreatt()//返回的是该链表的地址 { node *l=(node*)malloc(sizeof(node)); l->next=NULL; node *r;//r指向的始终是该链表的最后一个node结构 r=l;//这个地方是地址之间的赋值,所以对r操作就相当于对l操作,即对链表最后一个node结构操作 int number; while (scanf("%d",&number)!=EOF) { node *p=(node*)malloc(sizeof(node));//新建一个node结构并为其申请空间 p->value=number;//给新建的node结构赋值 r->next=p;//将p插入到链表的最后一个node结构的后面 p->next=NULL;//此时p已经是链表的最后一个了,给p的next赋值 r=p;//让r等于链表的最后一个node结构,即p节点 } return l;//返回头节点的地址 }
转载:https://blog.****.net/qq_40938077/article/details/80216563
推荐阅读
-
头部添加法与尾部添加法 - 首先来聊聊头部添加法:这种方法实现起来比较简单,核心思想是在创建新节点后,将其下一个元素链接到头部(header)
-
详解单链表的头部插入和尾部添加方法
-
如何在单链表中实现头部添加和尾部添加的操作
-
Java 链表的头部插入和尾部插入
-
使用头部插值和尾部插值方法创建、删除和遍历单个链表
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
头部插入和尾部插入摘要(活动影像版)
-
单个链接表 - 单个链接表的定义和基本操作(头部插入、尾部插入以建立表格、查找、插入、删除等)
-
数据结构]单链表解释 + 完整代码(插入、删除、尾部插入、头部插入、按值和按位查找、前向插入和后向插入),包含和不包含头部节点的两种实现方式
-
分析线性表(链表)头部插入法和尾部插入法的区别和优缺点--尾部插入法: