C语言实现单链表的基本操作

链表实现

1. 定义链表结点结构体

typedef struct node {
    int val;
    struct node* next;
} MyLinkedList, node;

1. 创建一个链表，即创建一个头结点

MyLinkedList* myLinkedListCreate() {
    MyLinkedList * obj = (MyLinkedList*)malloc(sizeof(node));
    obj->next = NULL;
    return obj;
}

1. 在链表首元结点之前添加一个结点，作为新的首元结点

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    node * newNode = (node*)malloc(sizeof(node));
    newNode->val = val;
    newNode->next = obj->next;
    obj->next = newNode;
}

1. 在链表尾结点之后添加一个结点，作为新的尾结点

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    node * newNode = (node*)malloc(sizeof(node));
    newNode->val = val;
    newNode->next = NULL;
    node* p = obj;
    while(p->next != NULL)
        p = p->next;
    p->next = newNode;
}

1. 在指定位置插入一个结点，值为val

int myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    node* p = obj;
    int j = 0;
    while (p && j < index) {
        p = p->next;
        ++j;
    }
    if (!p || j > index){
        printf("ERROR!\n");
        return -1;
    }
    node* newNode = (node*)malloc(sizeof(node));  // 生成新结点
    newNode->val = val;
    newNode->next = p->next;
    p->next = newNode;
    return 0;
}

1. 删除指定位置的结点

int myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    node* p = obj;
    int j = 0, val = 0;
    while (p->next && j < index) {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > index){
        printf("ERROR!\n");
        return -1;
    }
    node* q = p->next;
    p->next = q->next;  // 删除并释放结点
    val = q->val;
    free(q);
    return val;
}

1. 获取索引号为index的节点的数值，如果索引号错误则返回-1

int myLinkedListGet(MyLinkedList* obj, int index) {
    node* p = obj->next;
    int j = 0;
    while (p && j<index) {
        p = p->next;
        ++j;
    }
    if (!p || j>index){
        printf("ERROR!\n");
        return -1;
    }
    return p->val;
}

1. 释放链表

void myLinkedListFree(MyLinkedList* obj) {
    MyLinkedList * Transit;
    while(obj->next != NULL) {
        Transit = obj;
        obj = obj->next;
        free(Transit);
    }
    free(obj);
}

1. 打印链表

void showAll(MyLinkedList* obj) {
    if(obj->next == NULL) return;
    MyLinkedList *mov = obj->next;
    while(mov != NULL) {
        printf("%d ", mov->val);
        mov = mov->next;
    }
    printf("\n");
}

1. 主函数

#include <stdio.h>
#include <malloc.h>
int main() {
    MyLinkedList* obj = myLinkedListCreate();
    printf("初始的四个结点：");
    int i;
    for(i = 2; i < 6; i++) {
        myLinkedListAddAtTail(obj, i * i);
    }
    showAll(obj);
    printf("首元结点前插入：");
    myLinkedListAddAtHead(obj, 1);
    showAll(obj);
    printf("尾元结点后插入：");
    myLinkedListAddAtTail(obj, 36); 
    showAll(obj);
    printf("在指定坐标插入：");
    myLinkedListAddAtIndex(obj, 2, 6);
    showAll(obj);
    printf("在指定坐标删除：");
    myLinkedListDeleteAtIndex(obj, 3);
    showAll(obj);
    printf("获取指定坐标数值：%d\n", myLinkedListGet(obj, 3));
    myLinkedListFree(obj);
}

运行结果