链表的应用和实现

在软件开发中链表和数组非常常见,它们都是线性存储,区别只是存储方式的不同。数组是连续存储,链表是离散存储(非连续)。链表是根据节点的前后关系进行存储的,同时由于它是离散存储,对内存空间利用更好。

链表分为:单链表、双向链表、循环链表,下面我主要是以单链表为示例说明,单链表基本结构如下:

    头结点:A           首节点:B                                  尾节点:C
       👇               👇                                       👇
[data=NULL|next]——>[data|next]——>[data|next]——>[data|next]——>[data|next]——> NULL

由上结构可以知道,链表的每个节点都由两个属性构成,data负责存储数据,next负责指向下一个节点。当然,双向链表和循环链表都是以上面的结构进行扩展的。

单链表的头结点和尾结点比较特殊,头结点用来记录链表的头地址,是链表遍历的起点,尾结点的后继指针不指向任何结点,而是指向一个空地址NULL。这里首节点才时第一个有效节点。

时间复杂度: 单链表的插入、删除操作时间复杂度为O(1),随机查找时间复杂度为O(n)。相对于数组,链表的插入和删除更加简便。

尽管在前端开发中,数组的使用可能大于链表,但由于链表的优点,就我所知道,目前React框架中就有应用,React项目中React Fiber由单链表构成,参考:react16.3的fiber架构

C语言单链表实现

创建结构体Node数据类型,链表中的每个节点都将是下面的数据结构:

// 默认data为整型
typeof struct Node{
    int data; // 数据域
    struct Node * next; // 指针域
}Node, *PNode;

在上面的讲解中未说到结构体,简单点结构体就是一种数据类型。(*表示指针,指针就是内存地址,struct Node * next就是创建一个Node类型的结构体指针变量next,指针变量即存储内存地址的变量)。

链表创建函数如下:

// 创建链表
PNode createList() {
    // 长度
    int len;
    // 存放用户输入的节点值
    int val;
    
    // 不存放有效数据的头结点,分配动态内存
    PNode pHead = (PNode)malloc(sizeof(Node));
    // 容错
    if(NULL == pHead) {
        printf("分配失败,程序终止!\n");
        exit(-1);
    }
    
    // 创建一个临时节点
    PNode pTail = pHead;
    pTail->next = NULL;
    
    printf("请输入链表的长度: len=");
    scanf("%d", &len);
    
    for (int i = 0; i<len; ++i) {
        printf("请输入第%d个节点的值: ", i+1);
        scanf("%d", &val);
        // 分配动态内存
        PNode pNew = (PNode)malloc(sizeof(Node));
        if(NULL == pNew) {
            printf("分配失败,程序终止!\n");
            exit(-1);
        }
        
        // 赋值/替换
        pNew->data = val;
        pTail->next = pNew;
        pNew->next = NULL;
        pTail = pNew;
    }
    return pHead;
}

// 遍历  
int traverseList(PNode pHead) {
    printf("打印链表的z值:\n");
    PNode next = pHead->next;
    while(next != NULL) {
        printf("%d \n", next->data);
        next = next->next;
    }
    printf("\n");
    return 0;
}

// 移除
// pHead 链表头节点
// i 移除的下标,由1开始
bool removeList(PNode pHead, int position, int *pVal) {
    PNode p = pHead;
    int i = 0;
    
    // p->next != NULL,移除的前提下,保证要移除的那个只存在;
    // 在存在的前提下,p会指向要移除的前一个节点;
    while (p->next != NULL && i< position - 1) {
        p = p->next;
        ++i;
    }
    
    // i > position - 1,防止负数
    if(i > position - 1 || p->next == NULL) {
        return false;
    }
    
    PNode q = p->next;
    *pVal = p->data;
    
    p->next = p->next->next;
    free(q);
    q = NULL;
    return true;
}

// 插入
// pHead 链表头节点
// i 插入的下标,由1开始
bool insertList(PNode pHead, int position, int val){
    PNode p = pHead;
    int i = 0;
    
    // p != NULL,插入的前提下,保证要插入位置的前y一个元素存在;
    // 在存在的前提下,p会指向要插入的前的节点;
    while (p->next != NULL && i< position - 1) {
        p = p->next;
        ++i;
    }
    // // i > position - 1,防止负数
    if(i > position - 1 || p == NULL) {
        return false;
    }
    
    PNode pNew = (PNode)malloc(sizeof(Node));
    if(NULL == pNew) {
        printf("分配失败,程序终止!\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->next = p->next;
    p->next = pNew;
    return true;
}

通过createList函数创建单链表,这个函数的核心:创建一个临时的指针变量pTail,进行节点的替换。traverseList函数打印链表的值,removeList函数负责移除节点,insertList函数负责插入节点。

main函数中创建链表:

int main() {
    // 头节点
    PNode pHead = NULL; // 等价于struct Node * pHead = NULL
    int value;
    
    pHead = createList();
    removeList(pHead, 8, &value);
    insertList(pHead, 2, 123123);
    traverseList(pHead);
}

代码示例:C语言创建单链表

参考:

郝斌老师数据结构视频

ps: 微信公众号:Yopai,有兴趣的可以关注,每周不定期更新。不断分享,不断进步

上次更新: 7/25/2020, 9:20:49 AM

评 论: