链表复习（一）

链表性质——此处略

简单的链表基本结构（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;
}

实现链表插入函数——参数为Node*和int，分别表示要插入的节点和插入节点的Index，即插入节点后的节点为第Index个节点

void insert(Node* node,int index){
        if(head==NULL){//第一种情况——原链表为空，直接把head设置为node
            head=node;
            return;
        }
        if(index==0){//第二种情况：index=0.也就是把node插入到链表的首位，直接把head接在node上，然后把node设置成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的下一位设置成current的下一位，然后再把current的下一位设置成node，注意顺序不能变
            current_node->next=node;
        }

}

总结整个插入操作流程：

1、首先检查链表是否为空，如果为空则直接把node设置为head

2、检查index是否为0，若为0则表示将node插入到链表的首位——直接把node设置成head前一位，然后更新head为node即可

3、建立一个指针指向当前节点，同时附带一个计数器，依次遍历链表寻找index的前一位（即index-1）

4、检查count==index-1以确保index的值合法，然后执行插入操作：把node的下一位设置成current的下一位，然后更新current的下一位为node，注意顺序不能乱

遍历输出函数（解说略）

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;
    }