单链表的介绍和内存布局 [数据结构][Java]

单链表的介绍和内存布局

链表: LinkedList

链表是以节点的方式来存储的

• 节点又称之为: 结点

每个节点包含data域,next域

• data域就是数据域
  • 数据域就是用来存储数据的
• next域就是指针域
  • 指针域就是用来指向下一个节点的

链表在内存中各个节点不一定是连续存储的

链表分为带头结点和不带头结点的链表,在实际开发中根据实际的需求确定需不需要头结点

头结点是什么?:

• 头结点又称之为头节点

在数结构中,在单链表的首元节点之前设置的一个节点我们称之为头节点,头节点的数据域可以不存储任何信息,也可以存储链表的长度等附加信息,头结点的指针域存储指向首元节点的指针

头节点的作用:

方便链表的操作,减少代码量,举个例子: 要知道在链表中插入,删除一个元素是通过更改待操作节点的上一个结点的指针域来实现的 —> 那么我们第一个结点以外的结点做这些操作时还是比较简单的,但是我们怎样对第一个存储数据的节点(也就是首元节点)做这些操作? — > 这个时候我们就要通过引入一个头结点来实现 ,那么有的人就会问了: 除了引入头节点之外还有没有其他的方法?

• 方法是有的,但是不如引入一个头节点来的方便,总之,引入头结点就可以方便的处理一些特殊情况,就可以减少代码量

首元节点: 是指链表中用来存储数据元素的结点中的第一个结点

• 而头结点是首元节点前的结点

一个链表可以没有头结点,但是不可能没有首元节点

头指针: 头指针是指向链表中第一个节点的指针

• 这里的第一个节点可能是头结点,也可能时候首元节点

单链表(带头结点)的逻辑结构示意图如下:

单链表(带头结点)的物理结构(存储结构)的示意图:

• 物理结构是其在内存中的真实结构

补充:

链表是一个真正的动态数据结构

• 我们的数组并不是一个动态的数据结构, 即使我们可以让一个数组具有动态扩容的功能, 那么这个功能也是我们后天补充上去的 , 比不是数组这个数据结构与生俱来的, 但是我们的链表就是不同的了, 我们向链表中添加元素的时候不用去判断我们的链表是否已满, 我们的链表结构是不会满的, 只有当我们的内存被占用完的时候我们的链表才会由于添加不了元素而出现堆溢出, 但是这个时候即使由于我们的内存溢出, 这个时候其实我们的链表还是没有满, 此时只是我们的内存空间不够大了
  • 在理想状态之下我们的链表结构是永远不会满的