單鏈表的基本操作

一、初始化

初始化是使用單鏈表前必須要進行的操作。因為一個新的單鏈表並沒有指向任何節點，所以必須將其初始化為空，即頭指針指向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 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 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;
}