链表详解
一。链表的概念
链表与顺序表都是线性表中的一种,链表和顺序表在逻辑上都是连续的,但是链表是一种物理存储结构上非连续的存储结构,链表就像火车是由一个一个节点通过引用链接实现的:

链表的分类:有头链表和无头链表
- 有头链表:即头结点不存储实际数据,其指针指向第一个存储数据的节点;
- 无头链表:即没有头节点的链表,第一个节点直接存储数据,链表的头指针直接指向的就是第一个实际存储数据的节点;

二。链表的结构特点
我们知道链表是由一系列节点组成的,每个节点又分为两个部分:数据域和指针域;那么我们来看一下几个链表结构。
2.1 单向链表和双向链表
单向链表:
- 节点结构:
- 数据域:用来存放数据元素
- 指针域:用来存放下一个节点的地址
- 特点:单链表的节点只能通过指针指向下一个节点。形成一个单向的链状结构只能从前往后的顺序的访问链表,无法从当前节点访问到前一个节点

双向链表:
- 节点结构:
- 数据域:与单链表一样,用来存放数据元素
- 指针域:拥有两个指针,一个指向前驱节点,一个指向后继节点
- 特点:双链表可以从当前节点向前或者向后遍历链表,增加了操作的灵活性在删除节点时,双链表比单链表更加方便,可以直接通过前驱结点找到前一个节点

2.2 循环链表和非循环链表
循环链表:
- 定义:循环链表是一种特殊的链表结构,在单向循环链表中,最后一个节点的指针域指向的不是 null,而是该链表的头结点,从而形成一个环在双向链表中,不仅最后一个节点的后继指针指向头结点,头结点的前驱节点也指向最后一个节点,形成双向的循环结构








