数据结构之链表

链表(ListNode)

• 定义：链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现

• 链表的基本思维：利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互练习，串联，这就形成了链表。

• 特点：
  1.链表存储，顺序访问，
  2.结点可以在运行时动态生成，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域
  3.查询相对于数组困难，增加和删除容易。

• 优点
  1.链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素
  2.添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

• 缺点
  1.因为含有大量的指针域，占用空间较大
  2.查找元素需要遍历链表来查找，非常耗时

适用场景

• 数据量较小，需要频繁增加，删除操作的场景

常见的链表

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表
如图：

image.png

单链表

1.结构

image.png
2. 初始化

LinkedList listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL){                     //判断是否开辟空间失败，这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
}

3. 创建单链表
在初始化之后，就可以着手开始创建单链表了，单链表的创建分为头插入法和尾插入法两种，两者并无本质上的不同，都是利用指针指向下一个结点元素的方式进行逐个创建，只不过使用头插入法最终得到的结果是逆序的。

• 头插入法
  该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
  头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。

//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
  
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;     //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;

• 尾插入法
  该方法是将新结点逐个插入到当前链表的表尾上，为此必须增加一个尾指针 r, 使其始终指向当前链表的尾结点，否则就无法正确的表达链表

//单链表的建立2，尾插法建立单链表
  
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}

1. 遍历单链表（打印，修改）
进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可。

//遍历输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}

对于元素修改操作，以下是代码实现

//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

2. 插入操作
   链表的增加结点操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。

//单链表的插入，在链表的第i个位置插入x的元素
  
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}

3. 删除操作
删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。

//单链表的删除，在链表中删除值为x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}

双链表

1.结构

image.png

• DATA表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）；
• pre代表的是前驱指针，它永远指向当前结点的前一个结点，注意，如果当前结点是头结点，则pre指针为空；
• next代表的是后继指针，它永远指向当前结点的下一个结点，注意，如果当前结点是尾结点，则next指针为空
  2.操作
  双链表的创建
  对于创建双向链表，我们需要先创建头结点再逐步的进行添加，请注意，双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的。
  对于逐步添加数据，我们采取的做法是，开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。
  将过程逐步拆解为 创建头结点----创建一个新的结点----将头结点和新结点相互链接----再度创建新结点……
  双向链表的插入操作
  对于每一次的双向链表的插入操作，我们首先需要创建一个独立的结点并通过malloc操作开辟相应的空间，其次我们选中这个新创建的独立节点，将其的pre指针指向所需插入位置的前一个结点，同时，其所需插入的前一个结点的next指针修改指向为该新的结点，同理，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身，这样的一个操作我们称之为双向链表的插入操作。
  双向链表的删除操作
  删除操作的过程是：选择需要删除的结点，选中这个结点的前一个结点，将前一个结点的next指针指向自己的下一个结点，同时，选中该节点的下一个结点，将下一个结点的pre指针修改指向为自己的上一个结点，这样产生的效果就是在进行遍历的时候直接将这一个结点给跳过了。
  在这样的指针修改操作之后，我们释放删除结点，归还空间给内存，这样的操作我们称之为双链表的删除操作。
  双向链表的遍历
  如同单链表的遍历一样，利用next指针逐步向后进行索引即可，注意判断这里，我们既可以用while(list)的操作直接判断是否链表为空，也可以使用while(list->next)的操作判断该链表是否为空，其下一节点为空和本结点是否为空的判断条件是一样的效果，当然了，善用双向链表的pre指针进行有效的遍历也是值得去尝试的。
  C语言代码

#include<stdio.h>
#include<stdlib.h>
typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line;
//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)
 
//遍历双链表,同时打印元素数据
void printLine(line *head){
    line *list = head;
    int pos=1;
    while(list){
        printf("第%d个数据是:%d\n",pos++,list->data);
        list=list->next;
    }
}
 
//创建双链表
line* initLine(line * head){
    int number,pos=1,input_data;
    printf("请输入创建结点的大小\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //输入非法直接结束
    //////头结点创建///////
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("输入第%d个数据\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
 
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("输入第%d个数据\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
        
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}
 
//插入数据
line * insertLine(line * head,int data,int add){
    //三个参数分别为：进行此操作的双链表，插入的数据，插入的位置
    //新建数据域为data的结点
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;
    //插入到链表头，要特殊考虑
    if (add==1) {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一个结点
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判断条件为真，说明插入位置为链表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->pre=body;
        }else{
            body->next->pre=temp;
            temp->next=body->next;
            body->next=temp;
            temp->pre=body;
        }
    }
    return head;
}
 
//删除元素
line * deleteLine(line * head,int data){
    //输入的参数分别为进行此操作的双链表，需要删除的数据
    line * list=head;
    //遍历链表
    while (list) {
        //判断是否与此元素相等
        //删除该点方法为将该结点前一结点的next指向该节点后一结点
        //同时将该结点的后一结点的pre指向该节点的前一结点
        if (list->data==data) {
            list->pre->next=list->next;
            list->next->pre=list->pre;
            free(list);
            printf("--删除成功--\n");
            return head;
        }
        list=list->next;
    }
    printf("Error:没有找到该元素，没有产生删除\n");
    return head;
}
 
int main(){
    line *head=NULL;
    printf("创建双链表操作\n"); 
    head=initLine(head);
    printLine(head);
//////////create line////////////
    printf("插入操作\n"); 
    head=insertLine(head,40,2);     //为了简化直接写参数了
    printLine(head);
//////////insert Line////////////
    printf("删除操作\n"); 
    head=deleteLine(head,2);       //为了简化直接写参数了
    printLine(head);
//////////delete Line////////////  
    return 0;
}

循环单链表

1.结构

image.png

• next表示指针，它永远指向自身的下一个结点，对于只有一个结点的存在，这个next指针则永远指向自身，对于一个链表的尾部结点，next永远指向开头。
  循环单链表初始化
  循环链表的创建操作
  我们可以通过逐步的插入操作，创建一个新的节点，将原有链表尾结点的next指针修改指向到新的结点，新的结点的next指针再重新指向头部结点，然后逐步进行这样的插入操作，最终完成整个单项循环链表的创建。
  循环单链表的删除操作
  循环单链表的删除操作可以参考单链表的删除操作，其都是找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点即可，但需要注意的是尾节点和头结点的特判，尤其是尾结点，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空，其重点可以记录为【当前的前一节点.next=自身结点.next】这样的操作可以省去头尾结点的特判：
  3.循环单链表的遍历
  循环链表需要进行结点的特判，找到尾节点的位置，由于尾节点的next指针是指向头结点的，所以不能使用链表本身是否为空（NULL）的方法进行简单的循环判断，我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。
• 进阶概念——双向循环链表
  循环链表还有一个进阶的概念练习，同双向链表与单链表的关系一样，循环单链表也有一个孪生兄弟——双向循环链表，其设计思路与单链表和双向链表的设计思路一样，就是在原有的双向链表的基础上，将尾部结点和头部结点进行互相连接，这个链表的设计不难，就交给读者自主进行设计。

 #include<stdio.h>
#include<stdlib.h>
typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据，next指针为指向下一个结点
 
//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败，退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}
 
//创建--插入数据
int create_list(list *head){
    int data;   //插入的数据类型
    printf("请输入要插入的元素：");
    scanf("%d",&data);
 
    list *node=initlist();
    node->data=data;
    //初始化一个新的结点，准备进行链接
 
    if(head!=NULL){
        list *p=head;
        //找到最后一个数据
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("头结点已无元素\n");
        return 0;
    }
 
}
 
//插入元素
list *insert_list(list *head,int pos,int data){
    //三个参数分别是链表，位置，参数
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<=pos;i++){
            t=t->next;
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}
 
//删除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("链表为空！\n");
        return 0;
    }
    //建立零时结点存储头结点信息（目的为了找到退出点）
    //如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    list *temp = head;          
    list *ptr = head->next;
 
    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);
 
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { //循环结束的条件换成ptr->next == head
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}
 
 
//遍历元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍历头节点到，最后一个数据
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行 ( o=^•ェ•)o　┏━┓
        //把最后一个节点赋新的节点过去
        return 1;
    } else {
        printf("头结点为空!\n");
        return 0;
    }
}
 
int main(){
    //////////初始化头结点//////////////
    list *head=initlist();
    head->next=head;
    ////////通过插入元素完善链表/////////
    for(int i=0;i<5;i++){   //只是演示使用，不具体提供输入
        create_list(head);
    }
    display(head);
    ////////////插入元素////////////////
    head=insert_list(head,1,10);
    display(head);
    ////////////删除元素////////////////
    delete_list(head);
    display(head);
    return 0;
}

python链表实战

待实践后更新