数据结构02-链表(单/双/向普通及循环链表)

数据结构02-链表(单/双/向普通及循环链表)

链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一个用来指向下一个节点地址的指针(next指针)。

  1. 数组内存连续，需要预先知道数据大小的缺点；
  2. 链表结构内存不需要连续，可以充分利用计算机内存空间，实现灵活的内存动态管理。但失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大

链表在插入的时候可以达到O⑴的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。

1：单向链表

单向链表：指存放链表的结点中只有一个指针，指向它的下一个结点，而链表中最后一个结点的next指针为NULL。

头结点：链表中的第一个结点。只要知道了链表的头结点，就可以通过next指针，遍历整个链表。因此，一般在函数中，我们使用头结点来代表整个链表，将头结点传参给函数。

单向链表的存储结构：

typedef struct _node {
       int val;//值域，可以增加更多的值域，这里仅以int类型为代表
       struct _node *next;//指针域，指向下一个结点，最后一个结点指向NULL
} Node, *PNode;
单链表.png

1.1：创建

在创建链表过程中，将新分配的一个链表结点插入到已知的链表中，可以分为两种情况：从头部插入和从尾部插入。

image.png

1.1.1：头部插入创建

分析：


image.png
//从头部插入创建链表算法
node *create_linklist_head() {
       node *h = NULL;

       while(1) {
              node *p = (node*)malloc(sizeof(node));

              if(p==NULL) {
                     return h;
              }

              memset(p,0,sizeof(node));
              printf("Please input a data\n");
              scanf_s("%d",&(p->val));
              p->next = NULL;
              
              if(h==NULL) {//头结点指针为空，创建第一个结点              
                     h=p;
              } else {
                     p->next = h;
                     h=p;
              }

              if(p->value==0) {
                     break;
              }
       }

       return h;
}

1.1.2：尾部插入创建

分析：


image.png
//从尾部插入链表算法
node *create_linklist_tail() {
       node *h=NULL;

       while(1) {
              node *p = (node *)malloc(sizeof(node));

              if(p==NULL) {
                     return h;

              }

              memset(p,0,sizeof(node));
              printf("Please input a data\n");
              scanf_s("%d",&p->value);
              p->next = NULL;

              if(h==NULL) { //头结点指针为空，创建第一个结点 
                    h=p;
              } else {
                    node *q = h;//需要从头部遍历到尾部
                    
                    while(q->next) {
                        q=q->next;
                    }
                    
                    q->next = p;//q为尾部，q->next=p，将新建结点设置为尾部
                    p->next = NULL;
              }

              if(p->value==0) {//输入为零，则停止创建链表              
                     break;
              }
       }

       return h;
}

1.2：遍历

void traverse_list(node *h) {
       node *p = h;
       
       while(p) {
              printf("%d ",p->value);
              p=p->next;
       }

       printf("\n");
}

1.3：插入

将链表结点插入到某个指定的结点;

分析：


image.png
//在头结点之前插入某节点
bool insert_linklist_in_head_front(Node **h, int data) {
    Node *p = *h;
    
    if (p == NULL) {
        return false;
    }
    
    Node *node = (Node *)malloc(sizeof(Node));
    
    if (node == NULL) {
        return false;
    }
    
    memset(node, 0, sizeof(Node));
    node->val = data;
    node->next = p;
    *h = node;//改变h的值，需要传h的地址
    
    return true;
}

//在尾结点之后插入某节点
bool insert_linklist_in_tail_behead(Node *h, int data) {
    Node *p = h;
    
    if (p == NULL) {
        return false;
    }
    
    Node *node = (Node *)malloc(sizeof(Node));
    
    if (node == NULL) {
        return false;
    }
    
    memset(node, 0, sizeof(Node));
    node->val = data;
    node->next = NULL;//node之后要变为尾节点
    
    while (p->next) {
        printf("%d ", p->val);
        p = p->next;
    }
    
    p->next = node;
    
    return true;
}

//index_in_front(从0开始)
bool insert_linklist(Node **h, int index, int data) {//在链表h第index节点插入data
    Node *p = *h;

    if (!p) {
        return false;
    }
    
    Node *node = (Node *)malloc(sizeof(Node));
    
    if (node == NULL) {
        return false;
    }
    
    memset(node, 0, sizeof(Node));
    node->val = data;
    node->next = NULL;//node防止野指针
    
    if (index == 0) {
        node->next = p;
        *h = node;//改变h的值，需要传h的地址

        printf("0位置插入成功\n");
        return true;
    }
    
    int i = 0;
    Node *swap;
    
    while (i < index - 1) {
        p = p->next;
        ++i;
    }
    
    swap = p->next;//把下一个节点的地址，给用于交换的swap
    p->next = node;//把要插入的节点的地址，给上个节点的指针域
    node->next = swap;//把插入节点的下一个节点的地址，给插入节点的指针域
    
    return true;
}

int main(int argc, const char * argv[]) {
    printf("头部插入节点创建链表:  Please creat_linklist_head\n");
    Node *head1 = creat_linklist_head();//
    printf("遍历节点head1:  Please traverse_list\n");
    traverse_list(head1);
    
    //在尾结点之后插入某节点
    printf("插入某节点:  Please input a data\n");
    int k;
    scanf("%d", &k);
    printf("插入节点的位置index：\n");
    int index;
    scanf("%d", &index);
    bool binsert_linklist = insert_linklist(&head1, index, k);
    if (binsert_linklist) {
        printf("插入成功遍历节点head1:  Please traverse_list\n");
        traverse_list(head1);
    } else {
        printf("插入错误\n");
    }
}

1.3：删除

分析：


image.png
void del_list_node(node **h,int value) {
       if(h==NULL) {
              return;
       }

       node *p = *h;
       node *q = NULL;

       while(p) {
              if(p->value==value) {
                     if(p==h) {
                     //改变指针的值，需要在传参时传二级指针
                            *h=(*h)->next;
                            free(p);
                            p = NULL;
                            return;
                     } else {
                            q->next=p->next;
                            free(p);
                            p = NULL;
                     }
                            
                         return;
              }

              q=p;
              p = p->next;
       }
}

1.5：销毁

void destroy_list(node \*p) {
       node \*p =h;

       while(p) {
              node *q=p;//先用q保存这个待删除的结点
              p=p->next;//p指向下一个结点
              free(q);//现在可以删除q了
       }
}

1.6：单向循环链表

循环链表：最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

单向循环链表的遍历：判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非循环单链表判断链域值是否为NULL。

单向循环链表的4种不同的形式：


image.png

1.6.1：单向循环链表的创建

Node *create_list_loop() {
    Node *h = NULL;
    
    while(1) {
        Node *node = (Node *)malloc(sizeof(Node));
        
        if(node == NULL) {
            return h;
        }
        
        memset(node, 0, sizeof(Node));
        printf("Please input a data\n");
        scanf("%d",&(node->val));
        node->next = NULL;
        
        if(h == NULL) {//如果头结点指针为空，表明这是创建的第一个结点
            h = node;
            node->next = h;//单个节点的循环链表
        } else {
            Node *q = h;
            
            while(q->next != h) {//q->next如果等于h，那么q就是最后一个结点
                q = q->next;
            }
            
            q->next = node;
            node->next = h;//将p的next指针指向h，构成一个循环
        }
        
        if(node->val == 0) {
            break;
        }
    }
    
    return h;
}

1.6.2：单向循环链表的遍历

void traverse_loop_list(node *h) {
    if(h==NULL)
        return;
        
    node *p = h;
    
    do {
      printf("%d ",p->value);
      p = p->next;
    } while(p != h);
    
    printf("\n");

}

1.6.3：单向循环链表的销毁

void destroy_loop_list(node *h) {
    if(h==NULL)
        return;
        
    node *p = h->next;//防止头结点销毁,所以从第二个开始
    
    do {
        node *q = p;
        p = p->next;
        free(q);
    } while (p != h);

    free(h);
}

1.6.4：判断链表是否含有循环

//步长法判断链表是否含有循环
//思路是：定义2个指针遍历该链表，1个指针跑一步，1个指针跑两步；
//那么如果两个指针相遇，则表示有循环，否则无循环。
bool is_a_loop_list(node *h) {
       node *p = h;
       node *q = h->next;

       while(p&&q&&q!=p&&q->next) {
              p=p->next;
              q=q->next->next;
       }

       if(p==q) {//循环退出，p和q相等了，表示链表中存在循环
              return true;

       }

       return false;
}

2：双向链表

双向链表：结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

双向链表的存储结构定义如下：
typedef struct _dnode {
       int data;
       struct _dnode *pre;//前向指针，指向结点左边的结点
       struct _dnode *next;//后继指针，指向结点右边的结点
} dnode, *pdnode;
image.png

2.1：创建

创建双向链表，将一个新建的结点p，插入已知的双向链表中，有2种插入方法：

  1. 直接插入头部
  2. 直接插入尾部
image.png
//1. 从头部插入方法创建双向链表：
dnode *create_dobulelist_head() {
       dnode *h = NULL;

       while(1) {
              dnode *p = (dnode *)malloc(sizeof(dnode));

              if(p == NULL) {
                     return h;
              }

              memset(p, 0, sizeof(p));
              printf("Please input your data\n");
              scanf_s("%d",&p->value);
              p->next = p->pre = NULL;

              if(h==NULL){ //如果头结点指针为空，表明这是创建的第一个结点              
                     h = p;
              } else {
                     p->next = h;
                     h->pre = p;
                     h = p;
              }

              if(p->value==0) {
                     break;
              }
       }

       return h;
}

//2. 从尾部插入创建双向链表：
dnode *create_dobulelist_tail() {
       dnode *h = NULL;

       while(1) {
              dnode *p = (dnode *)malloc(sizeof(dnode));

              if(p==NULL){
                     return h;
              }

              memset(p,0,sizeof(p));
              printf("Please input your data\n");
              scanf_s("%d",&p->value);
              p->next = p->pre = NULL;

              if (h==NULL) {//如果头结点指针为空，表明这是创建的第一个结点              
                     h = p;
              } else {
                     dnode *q = h;

                     while(q->next) {//需要先从头结点开始遍历到尾结点
                            q=q->next;
                     }

                     q->next = p;
                     p->pre=q;
                     p->next = NULL;
              }

              if(p->value==0) {//创建循环退出
                     break;
              }
       }

       return h;
}

2.2：插入

如图：将一个结点p插入到双向链表q的后面下面演示顺序插入


image.png
dnode *create_sorted_dlist() {
    dnode *h = NULL;
    
    while(1) {
        dnode *p = (dnode *)malloc(sizeof(dnode));
        
        if(p == NULL) {
             return h;
        }
        
        memset(p, 0, sizeof(p));
        printf("Please input your data\n");
        scanf_s("%d", &(p->value));
        p->next = p->pre = NULL;
                  
        if(h==NULL){ //如果头结点指针为空，表明这是创建的第一个结点                   h = p;
        } else {
            dnode *q = h;
            dnode *r = NULL;
            
            while(q && q->val<p->val) {
                r = q;//用r记录下q的前一个结点
                q = q->next
            }
            
            //q非空，说明在链表中找到了一个节点，值比p->val大，此时p应插入到q的前面，r的后面
            if(q) {//q非空
                if (q == h) {
                    p->next = h;
                    h->pre = p;
                    h = p;
                } else {
                    r->next = p;//r->next->pre = p;
                    p->pre = r;//
                    p->next = q;//p->next = r->next;
                    q->pre = p;//r->next->pre = p;
                }
            } else {//q为空，r为尾节点
                r->next = p;
                p-pre = r;
            }
        
             p->next = h;
             h->pre = p;
             h = p;
        }
        
        if(p->value==0) {
             break;
        }
 
       if(p->value==0) {//创建循环退出
            break;
        }
    }

    return h;
}

2.3：遍历

void traverse_dlist_next(dnode *h) {
       dnode *p=h;

       while(p) {
              printf("%d ",p->value);
              p = p->next;
       }

       printf("\n");
}

2.4：销毁

void destroy_dlist(dnode *h) {
    dnode *p = h;
    
    while(p) {
          dnode *q = p;
          p = p->next;
          free(q);
    }
}

2.5：删除

双向链表中，将一个结点p从双向链表中删除方法：


image.png
int del_dlist_value(dnode **h, int value) {
    if (*h == NULL) {
        return 0;
    }
    
    node *p = *h;
    
    while(p) {
        
    
        if(p->value == value) {
            if(p == *h) {//头结点
                *h = (*h)->next;
                (*h)->pre = NULL;
            } else if (p->next == NULL) {
                p->pre->next = NULL;
            } else {
                p->pre->next = p->next;
                p->next->pre = p->pre;
            }
            
            free(p);
        }
        
        p = p->next; 
    }
}

2.6：双向循环链表

双向循环链表既是双向链表，又是循环链表。头结点的左链域指向最后一个结点，最后一个结点的右链域指向头结点。

image.png
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,743评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,296评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,285评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,485评论 1赞 283
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,581评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,821评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,960评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,719评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,186评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,516评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,650评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,329评论 4赞 330
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,936评论 3赞 313
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,757评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,991评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,370评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,527评论 2赞 349

推荐阅读更多精彩内容

  • 数据结构：链表
    本文内容：1、 什么是链表？2、 链表共分几类？3、 链表的 C 实现！ 总表：《数据结构？》 工程代码 Gith...
    半纸渊阅读 39,930评论 0赞 54
  • 二. 数据结构之线性结构
    本文内容取自于小甲鱼的数据结构与算法。//www.greatytc.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,876评论 0赞 7
  • 数据结构 第4讲 单链表
    本文来自本人著作《趣学数据结构》 链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么...
    rainchxy阅读 3,685评论 6赞 20
  • 数据结构第4-2讲双向链表
    链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？ 可以...
    rainchxy阅读 1,936评论 0赞 6
  • 8-14
    感恩同事一路的开车，一路风景，我们顺利到达目的地，为了了解原料的生产工艺及原料属性，联系厂家负责人，感恩山东好客的...
    毛先利阅读 183评论 0赞 0