单向链表(LinkedList)

链表

(1)链表可以更加方便的插入,删除,增加数据.并且链表的大小可以动态调整
(2)数组的访问支持随机访问,数据量大的情况访问速度优于链表很多.单向链表的访问需要从头结点开始遍历,所需时间比数组长.

链表结构体

typedef struct ListNode{
    DataType data;          //节点的数据
    struct ListNode *next;  //节点指针
}ListNode;

创建一个节点

ListNode *CreateNode(DataType data){
    struct ListNode *node;     
    node=(ListNode*)malloc(sizeof(ListNode)); //创建一个节点并分配空间
    node->data=data;
    node->next=NULL;
    return node; //返回该节点
}

插入一个节点

//插入一个节点到位置k
int Insert_Kth(ListNode **head,ListNode *node,int k){ //node为插入的节点
    ListNode **curr,*entry;int i;
    for(curr=head,i=0;i<k;i++){ //寻找位置,溢出则跳出
        if(!*curr) return 0;
        entry=*curr;
        curr=&entry->next;
    }
    node->next=*curr; //将节点插入当中
    *curr=node; //*curr 相当于前驱
    return 1;
} 

//插入为头结点(头插法链表,栈)不带头结点
int Insert_head(ListNode **head,ListNode *node){
    node->next=*head;
    *head=node;
    return 1;
}
//插入为头结点,带头节点
int Insert_head(ListNode *head,ListNode *node){
    node->next=head->next;
    head->next=node;
    return 1;
}
//插入为尾节点
int Insert_tail(ListNode **head,ListNode *node){
    ListNode **curr,*entry;
    for(curr=head;*curr;){ //移动到尾节点
        entry=*curr;
        curr=&entry->next;
    }
    node->next=*curr;
    *curr=node;
    return 1;
}

查找一个节点

//查找k位置的节点并返回,未找到返回空节点
ListNode* FindNode_Kth(ListNode **head,int k){
    ListNode **curr,*entry;
    int i;
    for(curr=head,i=0;i<k&&*curr;i++){
        entry=*curr;
        curr=&entry->next;
    }
    return *curr;
}

删除一个节点

//删除节点为val的所有节点
void DeleteNode(ListNode **head,DataType val){ //传入指向头节点地址的指针
    for(ListNode **curr=head;*curr;){ 
        ListNode *entry=*curr; //节点地址
        if(entry->data==val){
            *curr=entry->next; //*curr 的值相当与 pre->next
            free(entry); //释放该节点
        }
        else 
            curr=&entry->next; //curr指向entry下一个节点的地址
    }
}
//删除位置为k的节点
void DeleteNode_Kth(ListNode **head,int k){
    ListNode **curr,*entry;
    int i;
    for(curr=head,i=0;i<k&&*curr;i++){ //查找节点
        entry=*curr;
        curr=&entry->next;
    }
    entry=*curr;
    if(!entry) return;
    *curr=entry->next;
    free(entry);
}
//二重指针的骚操作建议用Clion(其他IDE)Debug搞清楚