[数据结构与算法][数据结构] 二.单链表及其C语言实现

单链表也是线性表的一种物理结构(储存结构)

它的特点是逻辑上相邻的元素物理位置上并不一定相邻, 所以单链表不需要一块连续的内存, 可以更好地利用内存

它利用指针去指向下一个节点, 因此它的缺点是不能随机访问, 只能由前一个节点找到后一个节点,
而且指针也会占用额外的内存

算法时间复杂度:

• 找到某个索引的节点: O(n), (不能随机访问,只能从头开始找)
• 在头部/尾部插入节点: O(1)

• 在中间某位置插入节点: O(n) (因为需要找到节点的位置)
• 删除头部/尾部节点(如果有尾指针): O(1)

• 删除中间某位置的节点: O(n) (也是因为需要找到节点位置)

C语言实现:

/**
 * @file linked_list.c
 * @author xiaoxiao (you@domain.com)
 * @brief 单链表
 * @version 0.1
 * @date 2022-03-01
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    struct Node * next;
    int data;
}Node;

typedef Node* PNode;

/**
 * @brief 初始化表头(无数据)
 * 
 * @return PNode 表头
 */
PNode initalList(){
    /** 表头不存储数据*/ 
    PNode pHead = (PNode) malloc(sizeof(Node));
    pHead -> next = NULL;
    return pHead;
}

/**
 * @brief 在尾部插入一个元素
 * 
 * @param pHead 链表头
 * @param data 数据值
 */
void insertInTail(PNode pHead, int data){
    
    PNode pCurrent = pHead;
    while(pCurrent -> next != NULL){
        pCurrent = pCurrent -> next;
    }
    pCurrent -> next = (PNode)(malloc(sizeof(Node)));
    pCurrent -> next -> next = NULL;
    pCurrent -> next -> data = data;
}

/**
 * @brief 在任意索引插入一个元素
 * 1是在表头后面(第一个元素)插入
 * 
 * @param pHead 链表头 
 * @param index 索引
 * @param data 数据值
 */
bool insertByIndex(PNode pHead, int index, int data){
    PNode pCurrent = pHead;
    int i = 1;
    while(pCurrent != NULL){
        if(i == index){
            PNode pNewNode = (PNode)malloc(sizeof(Node)); // 新节点
            pNewNode -> data = data;
            pNewNode -> next = pCurrent -> next;
            pCurrent -> next = pNewNode;
            return true;
        }
        pCurrent = pCurrent -> next;
        i ++;
    }
    printf("索引大于链表长度+1\n");
    return false;
}

/**
 * @brief 删除尾部元素
 * 
 * @param pHead 链表头
 */
void deleteTail(PNode pHead){
    PNode pCurrent = pHead;
    PNode pPrev = NULL;
    while(pCurrent -> next != NULL){
        pPrev = pCurrent;
        pCurrent = pCurrent -> next;
    }
    pPrev -> next = NULL;
    free(pCurrent);
}

bool deleteByIndex(PNode pHead, int index){
    PNode pCurrent = pHead;
    for(int i = 1; i < index; i++){
        if(pCurrent -> next != NULL){
            pCurrent = pCurrent -> next;
        }
        else{
            printf("索引大于链表长度\n");
            return false;
        }
        // pCurrent是要删除的前一个节点
    }
    if(pCurrent -> next == NULL){ // 这就是最后一个节点
        printf("索引大于链表长度\n");
        return false;
    }
    PNode pNext = pCurrent -> next -> next;
    free(pCurrent -> next);
    pCurrent -> next = pNext;
    return true;
}

/**
 * @brief 打印链表
 * 
 * @param pHead 链表头
 */
void printList(PNode pHead){
    PNode pCurrent = pHead -> next;
    printf("打印链表: ");
    while(pCurrent != NULL){
        printf("%d ", pCurrent -> data);
        pCurrent = pCurrent -> next;
    }   
}

int main(){
    printf("----------------\n");
    PNode pHead = initalList();
    insertInTail(pHead, 2);
    insertInTail(pHead, 4);
    insertInTail(pHead, 10);
    insertByIndex(pHead, 10, 7);
    deleteByIndex(pHead, 2);
    printList(pHead);
    printf("\n----------------\n");
    return 0;
}