鏈表性質(zhì)——此處略

簡單的鏈表基本結(jié)構(gòu)（cpp）：

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node* next;
    Node(int _data) {
        data = _data;
        next = NULL;
    }
};
class LinkList {
private:
    Node* head;
public:
    LinkList() {
        head = NULL;
    }

};
int main() {
    LinkList linklist;
    return 0;
}

實現(xiàn)鏈表插入函數(shù)——參數(shù)為Node*和int，分別表示要插入的節(jié)點和插入節(jié)點的Index，即插入節(jié)點后的節(jié)點為第Index個節(jié)點

void insert(Node* node,int index){
        if(head==NULL){//第一種情況——原鏈表為空，直接把head設(shè)置為node
            head=node;
            return;
        }
        if(index==0){//第二種情況：index=0.也就是把node插入到鏈表的首位，直接把head接在node上，然后把node設(shè)置成head
            node->next=head;
            head=node;
            return;
        }
        int count=0;
        Node* current_node=head;
        while(current_node->next!=NULL&&count<index-1){
            current_node=current_node->next; //遍歷鏈表尋找index的前一位
            count++;
        }    
        if(count==index-1){
            node->next=current_node->next;//先把node的下一位設(shè)置成current的下一位，然后再把current的下一位設(shè)置成node，注意順序不能變
            current_node->next=node;
        }

}

總結(jié)整個插入操作流程：

1、首先檢查鏈表是否為空，如果為空則直接把node設(shè)置為head

2、檢查index是否為0，若為0則表示將node插入到鏈表的首位——直接把node設(shè)置成head前一位，然后更新head為node即可

3、建立一個指針指向當(dāng)前節(jié)點，同時附帶一個計數(shù)器，依次遍歷鏈表尋找index的前一位（即index-1）

4、檢查count==index-1以確保index的值合法，然后執(zhí)行插入操作：把node的下一位設(shè)置成current的下一位，然后更新current的下一位為node，注意順序不能亂

遍歷輸出函數(shù)（解說略）

void output(){
        Node* current_node;
        if(head!=NULL){
            current_node=head;
        }
        else{
            return;
        }
        while(current_node!=NULL){
            cout<<current_node->data<<endl;
            current_node=current_node->next;
        }
        cout<<endl;
    }