链表的头节点和头指针.md

概述

今天在整理HashMap在多线程环境下的死循环问题时,注意到了一个细节,哈希表的形状分别可以是以下两种形式:

image image

当然二者都是对的,其中第二种形式也是我头脑里面想象的符合,继续向下探索,因为table数组中,每个下标所在位置都是可以存放一条链表的,链表可以有头节点,也可以没有,那么第一种HashMap的结构就是每条链表都带有一个头节点,第二张图没有头节点。
对上面结果做出修改,HashMap中的链表是没有头节点的,图一这样做完全是为了方便表示。

1.抛开上面的不谈,带头节点的链表和不带头节点的链表有何不同?

头指针:

把指向第一个节点的指针成为头指针

头节点:

在第一个节点前面附加一个节点,数据域可以不设任何信息,也可以设置一些特殊信息,例如链表的长度等

一个链表可以没有头节点,但是不能没有头指针,头指针作为数组的标识,当你想要访问这个链表时,就要通过头指针来获取链表所在位置,知道了头指针,那么链表中所有 的节点都可以被访问到

2.头节点不是必要的,那么为什么要进入头节点呢?

插入操作 假设头节点为head,插入元素为s

1.带有头节点进行插入操作时,不管要插入的位置是第一个节点,还是中间的任意位置,只需要使用一个变量p记录要插入节点的前一个位置,当节点s进行插入时,s.next = p.next p.next = s 即可完成

2.如果没有头节点,进行插入操作就要分两种情况操作,如果要插入的位置是第一个节点,那么s.next = head head = s ,如果要插入的位置是中间的任意位置,那么还是使用p指向要插入的前一个元素,s.next = p.next p.next = s ,由此可知,如果不使用头节点既要考虑两种插入情况,又在中途修改了头节点head,虽然也不是不对,但是有一种违背契约的感觉。

删除操作

1.如果使用头节点,也不存在删除位置的差异,要删除的节点为s,那么使用p来指向要删除节点前一个节点,不管p是指向了头节点还是普通节点,只需要p.next = s.next

2.如果没有头节点,删除第一个节点,head = head.next,删除其他节点同上,还是分情况考虑,而且修改了头指针


由此可以看出,第一张图中的数组链表中,是使用了头节点的,这样做完全是为了实现的简洁,并且这样制图更容易表达。