江苏龙网

  1. 主页 > 生活百科 > >

关于链表的理解

链表

一：链表是什么 
1、链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成 。
 
2、结点包括两个部分：（1）存储数据元素的数据域（内存空间），（2）存储指向下一个结点地址的指针域 。
 
3、相对于线性表顺序结构，操作复杂 。
 
4.链表分为 （1）单链表 （2）双链表 （3）单向循环链表 （4）双向循环链表
 
二：链表的作用
 
1、实现数据元素的存储按一定顺序储存，允许在任意位置插入和删除结点 。
 
2、包括单向结点，双向结点，循环接点
 
三：链表与数组的区别
说到链表那肯定要聊一下数组，为什么会出现链表呢？
 
（1）数组：使用一块连续的内存空间地址去存放数据，但
 
例如：
int  a[5]={1,2,3,4,5} 。突然我想继续加两个数据进去，但是已经定义好的数组不能往后加，只能通过定义新的数组
 
int b[7]={1,2,3,4,5,6,7};      ***********这样就相当不方便比较浪费内存资源,对数据的增删不好操作 。
 
（2）链表：使用多个不连续的内存空间去存储数据，可以 节省内存资源（只有需要存储数据时，才去划分新的空间），对数据的增删比较方便 。
 
四、链表的优缺
优点:
(1)插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可 。(2)没有空间限制,存储元素无上限,只与内存空间大小有关 。(3)动态分配内存空间，不用事先开辟内存
 
缺点：
(1)占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多) (2) 查找速度比较慢，因为在查找时，只能顺序查找，需要循环链表
 
五、关于头指针，头节点，首元节点的那些事
头指针：指向链表第一个节点的指针（不一定是头节点，因为……链表要是没有头节点呢？），没有实际开辟空间 （即没有用malloc等动态分配内存） 而且必须存在，因为头指针不存在，就不便于对链表进行操作 。
 
头节点：不是必须存在（若存在则为链表的第一个节点）其主要作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行（还是挺有用的） 。其数据域可以不储存任何数据，若储存则通常是链表的长度啥的 。
 
首元节点：第一个数据域中储存有效数据的节点 若头节点不存在 则其为链表的第一个节点，是一定要存在的（除非是空表）
 
有关链表的一些操作
1.单链表 
节点结构默认为：
 
struct ListNode
{
int val;
struct ListNode *next;
}
 
①单链表的创建
//创建链表 
struct ListNode* createList()
{
    struct ListNode*p=NULL,*tail=NULL,*head=NULL;//p为待开辟的节点指针,tail为指向链表尾部的指针,head为指向链表头部的指针 。
                                  //笔者喜欢在创建链表时 创建head tail 两个指针 虽然不一定都用得到
    int num;                        //将指针置空是个好习惯 
    scanf("%d",&num);
    //尾插法  顺序插法 
    while(num!=-1)//假设以num/val值为-1作为链表的结束标志  或者你用定长条件也行 
    {
       p=(struct ListNode*)malloc(sizeof(struct ListNode));//注意此处用sizeof计算大小时在ListNode前要加struct关键字
       p->val=num;
       p->next=NULL;
       if(head==NULL)//第一次循环时将头指针head指向p 
       {
           head=p;    
       } 
       else
       {
          tail->next=p;    
       } 
       tail=p;//此句放else里面也行  笔者更喜欢在第一次循环时就将tail与p与head产生关联 


推荐阅读


上一篇：一文精通递归算法

下一篇：Kubernetes集群