一、链表简介
1、链表概念
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,节点可以在运行时动态生成,节点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
2、基础特点
内存存储
逻辑结构
特点描述
物理存储上是无序且不连续的;链表是由多个节点以链式结构组成;逻辑层面上看形成一个有序的链路结构;链表结构解决数组存储需要预先知道元素个数的缺陷,可以充分利用内存空间,实现灵活的内存动态管理。
二、单向链表
1、基础描述
单向链表是链表的一种,其特点是链表的链接方向是单向的,链表的遍历要从头部开始顺序读取;结点构成,head指针指向第一个成为表头结点,终止于最后一个指向NULL的指针。
2、基础操作
添加数据
初始化head节点,作为链表的头;修改当前末尾节点的next指针;新添加的节点房子在链表末尾;删除数据
遍历找到要删除的节点,把删除节点前个节点的指针指向该删除节点的下个节点;
三、双向链表
1、概念描述
双向链表也叫双链表,是链表的一种,链表的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,从双向链表中的任意一个结点开始,都可以很快速地访问它的前驱结点和后继结点,链表结构的使用多数都是构造双向循环链表。
2、基础操作
添加数据
遍历找到链表的最后一个节点;修改当前末尾节点的next指针;新添加的节点房子在链表末尾;添加最新尾节点的prev指针;删除数据
双向链表,基于要删除节点操作即可;操作上图中要删除的Node2节点;Node2.prev.next = Node2.next;Node2.next.prev = Node2.prev;通过上述流程的操作,就把链表中一个节点删除,剩下节点再度连接成链式结构。
四、环形链表
在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点,这样就形成了环形链表:
环形链表链表的一种结构,特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。