单链表的基本操作

一、初始化

初始化是使用单链表前必须要进行的操作。因为一个新的单链表并没有指向任何节点，所以必须将其初始化为空，即头指针指向NULL。

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

//初始化链表
LinkList initList(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

以上代码中，我们定义了一个结构体Node，包括数据域data和指针域next。而LinkList类型是struct Node*的别名，可以直接使用LinkList作为函数返回值。

二、插入元素

单链表的插入操作分为头插法和尾插法。其中头插法将新节点插入到链表头部，尾插法则将新节点插入链表尾部。

1.头插法

头插法是将每个新节点插入到链表头部。主要步骤有：

1.创建新节点p，设置其数据域为x，并将其next指针指向头节点的下一个节点。

2.将头节点的next指针指向新节点p。

//头插法插入节点
void insertHead(LinkList L, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = L->next;
    L->next = p;
}

2.尾插法

尾插法是将每个新节点插入到链表尾部。主要步骤也很简单：

1.创建新节点p，设置其数据域为x，并将其next指针指向NULL。

2.找到链表最后一个节点，并将其next指针指向新节点p。

//尾插法插入节点
void insertTail(LinkList L, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    Node *cur = L;
    while(cur->next) cur = cur->next;
    cur->next = p;
}

三、删除元素

删除元素就是将链表中指定的节点删除。其步骤包括：

1.查找需要删除的节点。

2.将待删除节点的前一个节点的next指针指向待删除节点的下一个节点。

3.释放待删除节点的内存。

//删除链表中第i(i>=1)个节点
void deleteNode(LinkList L, int i){
    Node *cur = L;
    for(int j = 1; j < i && cur; j++) cur = cur->next;
    if(!cur || !cur->next) return;    //链表长度不够i个
    Node *del = cur->next;
    cur->next = del->next;
    free(del);
}

四、遍历链表

遍历链表就是按照链表的顺序将节点的值输出。遍历操作很简单，只需要从头节点的下一个节点开始依次遍历到链表结尾即可。

//遍历链表并输出每个节点的值
void traverse(LinkList L){
    Node *cur = L->next;
    while(cur){
        printf("%d ", cur->data);
        cur = cur->next;
    }
}

五、查找元素

查找元素需要遍历链表，查找目标节点的值与链表中每个节点的值逐一比较。如果查找到目标节点，则返回该节点在链表中的位置，否则返回0。

//查找值为x的节点并返回其位置
int search(LinkList L, int x){
    int i = 1;
    Node *cur = L->next;
    while(cur){
        if(cur->data == x) return i;
        cur = cur->next;
        i++;
    }
    return 0;
}

六、完整代码示例

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

//初始化链表
LinkList initList(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

//头插法插入节点
void insertHead(LinkList L, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = L->next;
    L->next = p;
}

//尾插法插入节点
void insertTail(LinkList L, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    Node *cur = L;
    while(cur->next) cur = cur->next;
    cur->next = p;
}

//删除链表中第i(i>=1)个节点
void deleteNode(LinkList L, int i){
    Node *cur = L;
    for(int j = 1; j < i && cur; j++) cur = cur->next;
    if(!cur || !cur->next) return;    //链表长度不够i个
    Node *del = cur->next;
    cur->next = del->next;
    free(del);
}

//遍历链表并输出每个节点的值
void traverse(LinkList L){
    Node *cur = L->next;
    while(cur){
        printf("%d ", cur->data);
        cur = cur->next;
    }
}

//查找值为x的节点并返回其位置
int search(LinkList L, int x){
    int i = 1;
    Node *cur = L->next;
    while(cur){
        if(cur->data == x) return i;
        cur = cur->next;
        i++;
    }
    return 0;
}

//测试代码
int main(){
    LinkList L = initList();
    insertHead(L, 1);
    insertTail(L, 2);
    insertTail(L, 3);
    deleteNode(L, 2);
    traverse(L);
    printf("\n%d\n", search(L, 2));
    return 0;
}