链表的基本概念

链表的基本概念

链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表 带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到 *** 作跑步减肥。

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行， 两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

链表中数据元素的构成

每个元素本身由两部分组成：

本身的信息，称为“数据域”；

指向直接后继的指针，称为“指针域”。

头结点、头指针和首元结点

头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

链表中插入头结点，根据插入位置的不同，分为3种：

1. 插入到链表的首部，也就是头结点和首元结点中间；
2. 插入到链表中间的某个位置；
3. 插入到链表最末端；
4. 提示：在做插入 *** 作时，首先要找到插入位置的上一个结点，图4中，也就是找到结点 1，相应的结点 2 可通过结点 1 的 next 指针表示，这样，先进行步骤 1，后进行步骤 2，实现过程中不需要添加其他辅助指针。
    

线性表的链式存储相比于顺序存储，有两大优势：

1. 链式存储的数据元素在物理结构没有限制，当内存空间中没有足够大的连续的内存空间供顺序表使用时，可能使用链表能解决问题。（链表每次申请的都是单个数据元素的存储空间，可以利用上一些内存碎片）
2. 链表中结点之间采用指针进行链接，当对链表中的数据元素实行插入或者删除 *** 作时，只需要改变指针的指向，无需像顺序表那样移动插入或删除位置的后续元素，简单快捷。

链表和顺序表相比，不足之处在于，当做遍历 *** 作时，由于链表中结点的物理位置不相邻，使得计算机查找起来相比较顺序表，速度要慢。