单链表与双链表的代码实现

单链表

链表的概念

• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
• 链表比数组的优势在于，它可以提供高效的重排数据的能力。这种灵活性的代价是不能快速访问表中的任意数据项，
• 访问链表中数据项的唯一方式是沿着链表，一个一个节点的访问，直到找到这个数据项。、

节点的表示

//节点
typedef struct node{
    int data;
    struct node* next;
}node_t;

链表的表示

//链表
typedef struct list{
    node_t* head;//记录链表头节点的地址
    node_t* tail;//记录链表尾节点的地址
}list_t;

链表的操作

链表的初始化

//链表初始化
//list_t list  list.head list.tail
//list_init(&list);
void list_init(list_t* l){
   //头节点
   l->head = malloc(sizeof(node_t));
   //尾节点
   l->tail = malloc(sizeof(node_t));

   //头尾节点存入数据0
   l->head->data = 0;
   l->tail->data = 0;
   //头尾节点相连
   //头节点中的next指针　指向　尾节点
   //尾节点中的next指针　指向　NULL
   l->head->next = l->tail;
   l->tail->next = NULL;
}

链表的释放

//链表的释放
void list_deinit(list_t* l){
    //将头节点地址存入pnode指针
    node_t* pnode = l->head;
    while(pnode){
         //暂存下一个节点的地址
         node_t* tmp = pnode->next;
         //释放当前节点
         free(pnode);
         //pnode指向下一个节点
         pnode = tmp;
    }
    //头尾指针置空
    l->head = NULL;
    l->tail = NULL;   

}

头部插入

//头部插入
void list_add_head(list_t* l,int data){
    
//创建新节点
    node_t* new = malloc(sizeof(node_t));
    new->data = data;
    new->next = NULL;
    //将新节点插入指定位置
    //让新节点的next指针　指向　第一个有效节点
    new->next = l->head->next;
    //让头结点的next指针　指向　新节点
    l->head->next = new;
}

尾部插入

//尾部插入
void list_add_tail(list_t* l,int data){
    //创建新节点
    node_t* new = malloc(sizeof(node_t));
    new->data = data;
    new->next = NULL;
    //循环确定插入位置
    for(node_t* p = l->head;p != l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        //当mid指针指向尾节点，则first指针指向最后一个有效节点
        //新节点应插入在first和mid指针之间
        if(mid == l->tail){
            //让first指针指向的节点的next指针 指向 新节点
            first->next = new;
            //让新节点的next指针 指向 尾节点
            new->next = mid;
            break;
        }

    }
}

顺序插入

//顺序插入
 void list_add(list_t* l,int data){
    node_t* new = malloc(sizeof(node_t));
    new->data = data;
    new->next = NULL;
    //找位置插入
    for(node_t* p = l->head;p != l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        //当mid指针指向的节点第一次比新节点大
        //新节点应插入在first和mid指针之间
        //如果mid指针指向了尾节点,则说明新节点最大
        if(mid->data > new->data || mid == l->tail){
           //让first指针指向的节点的next指针 指向新节点
            first->next = new;
           //让新节点的next指针 指向 mid指针指向的节点
            new->next = mid;
            break;
        }
    }
 }

删除节点

//删除节点
void list_del(list_t* l,int data){
    //找到要删除的节点
    for(node_t* p = l->head;p != l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        node_t* last = mid->next;
        if(mid->data == data){
            //连接前后两个节点
            first->next = last;
            free(mid);
            mid = NULL;
            break;
        }
    }
}

遍历链表

//遍历链表
void list_travel(list_t* l){
    for(node_t* p = l->head;p != l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        node_t* last = mid->next;
        if(mid != l->tail){
            printf("%d ",mid->data);
        }
    }
    printf("\n");
}

在main.c文件调用上述链表的操作

//链表测试
#include<stdio.h>
#include"list.h"  //上述链表操作以及节点和链表的表示均写入头文件

int main(void){
    //链表
    list_t list;
    //初始化链表
    list_init(&list);
    //顺序插入
    list_add(&list,60);
    list_add(&list,40);
    list_add(&list,50);
    //头部插入
    list_add_head(&list,30);
    list_add_head(&list,20);
    //尾部插入
    list_add_tail(&list,70);
    list_add_tail(&list,80);
    //遍历
    list_travel(&list);
    //删除节点
    list_del(&list,60);
    //遍历
    list_travel(&list);
    //释放
    list_deinit(&list);
    return 0;
}

双链表

双链表的概念

• 单链表中，每个节点中都包含指向下一个节点的指针，这也就意味着，我们在使用链表时，只能从头到尾的去找节点。
• 为了克服单向性的这一缺点，我们在设计链表时，可以在每个节点中再设置一个指向前面节点的指针。这样每个节点中都包含两个指针，一个指向直接后继，一个指向直接前驱。这就是双向链表。

节点的表示

//节点
typedef struct node{
    int data;//数据
    struct node* next;//记录后一个节点的地址
    struct node* prev;//记录前一个节点的地址
}node_t;

双链表的表示

//链表
typedef struct list{
    node_t head;//头节点
    node_t tail;//尾节点
}list_t;

  ！！！   

       注意这里我们与定义单链表时的区别，这里我们定义的是变量，而在单链表中我们定义的是头尾指针，两种方法都可实现，这里我们用不同于单链表的方法来定义双向链表，因此在具体实现中也有些许区别，注意辨别，例如   l->head.data = 0;   而在单链表中我们用的是  l->head->data = 0;

双向链表的操作

链表的初始化

//list_t list;
//list_init(&list);
//初始化
void list_init(list_t* l){
    //头尾节点存入0
    l->head.data = 0;
    l->tail.data = 0;
    //处理头节点里的指针
    l->head.next = &l->tail;
    l->head.prev = NULL;
    //处理尾节点里的指针
    l->tail.next = NULL;
    l->tail.prev = &l->head;
}

链表的释放

//链表的释放
void list_deinit(list_t* l){
    while(l->head.next != &l->tail){
        node_t* first = &l->head;
        node_t* mid = first->next;
        node_t* last = mid->next;
        //连接节点
        //前面节点的next指针 指向 后面的节点
        first->next = last;
        //后面节点的prev指针 指向 前面的节点
        last->prev = first;
        //释放mid指针指向的节点
        free(mid);
        mid = NULL;
    }    
}

头部插入

//头部插入
void list_add_head(list_t* l,int data){
    //创建新节点
    node_t* pnode = malloc(sizeof(node_t));
    pnode->data = data;
    pnode->next = NULL;
    pnode->prev = NULL;
    //插入新节点
    node_t* first = &l->head;
    node_t* mid = first->next;

    //让first指向的节点里的next指针 指向 新节点
    first->next = pnode;
    //让pnode指向的新节点里的next指针 指向 mid指向的节点
    pnode->next = mid;
    //让mid指向的节点里的prev指针 指向 新节点
    mid->prev = pnode;
    //让pnode指向的新节点里的prev指针 指向 first指向的节点
    pnode->prev = first;
}

尾部插入

//尾部插入
void list_add_tail(list_t* l,int data){
    //创建新节点
    node_t* pnode = malloc(sizeof(node_t));
    pnode->data = data;
    pnode->next = NULL;
    pnode->prev = NULL;
    //插入新节点
    node_t* last = &l->tail;
    node_t* mid = last->prev;
    
    //让mid指向的节点里的next指针 指向 新节点
    mid->next = pnode; 
    //让pnode指向的节点里的next指针 指向 last指针指向的节点
    pnode->next = last;
    //让last指向的节点里的prev指针 指向 新节点
    last->prev = pnode;
    //让pnode指向的节点里的prev指针 指向  mid指针指向的节点
    pnode->prev = mid; 
}

顺序插入

//顺序插入
void list_add(list_t* l,int data){
    //创建新节点
    node_t* pnode = malloc(sizeof(node_t));
    pnode->data = data;
    pnode->next = NULL;
    pnode->prev = NULL;
    //找位置插入
    for(node_t* p = &l->head; p != &l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        if(mid->data > pnode->data || mid == NULL){
            //让first指向的节点里的next指针 指向 新节点
            first->next = pnode;
            //让pnode指向的节点里next指针 指向 mid指向的节点
            pnode->next = mid;
            //让mid指向的节点里的prev指针 指向 新节点
            mid->prev = pnode;
            //让pnode指向的节点里的prev指针 指向 first指向的节点
            pnode->prev = first;
            break;
        }
    }
}

删除节点

//删除节点
void list_del(list_t* l,int data){
    for(node_t* p = &l->head;p != &l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        node_t* last = mid->next;
        if(mid->data == data){
            // 让前后结点相连
            //让前面节点的后指针 指向 后节点
            first->next = last;
            //让后面节点的前指针 指向 前节点
            last->prev = first;
            // 释放中间节点
            free(mid);
            mid = NULL;
            break;
        }
    }
}

遍历链表

//遍历链表
void list_travel(list_t* l){
    for(node_t* p = &l->head;p != &l->tail;p = p->next){
        node_t* first = p;
        node_t* mid = first->next;
        if(mid != &l->tail){
            printf("%d ",mid->data);
        }
    }
    printf("\n");
}

在main.c文件调用上述栈的操作

#include<stdio.h>
#include"list.h"  //上述双向链表的操作以及节点和链表的表示均写入头文件

int main(void){
    //双链表
    list_t list;
    //初始化
    list_init(&list);
    //头部插入
    list_add_head(&list,30);
    list_add_head(&list,20);
    //尾部插入
    list_add_tail(&list,80);
    list_add_tail(&list,90);
    //顺序插入
    list_add(&list,10);
    list_add(&list,70);
    list_add(&list,40);
    list_add(&list,60);
    list_add(&list,50);
    //遍历链表
    list_travel(&list);
    //删除节点
    list_del(&list,30);
    list_del(&list,40);
    //遍历链表
    list_travel(&list);
    //释放
    list_deinit(&list);
    return 0;
}