链表

链表是一种逻辑结构上的线性表，物理结构上的非线性表
链表由许多节点组成，每个节点有对应的值和指向下一个节点的指针
第一个节点称为首节点，最后一个节点称为尾节点，尾节点的指向为空.
特点:
查找某一节点都是由头开始遍历查找，增加节点的效率比顺序表快，删除节点的效率比顺序表快，查找节点的效率比顺序表慢
代码示例:

#include<iostream>
using namespace std;
//创建链表结构体,数据成员有值和指向下一节点的指针
struct list{
    int value;
    list *next;
    list(int x){
        value = x;
        next = nullptr;
    }
};
//在n节点后插入p节点
void insert(list *n, list *p){
    p->next = n->next;
    n->next = p;
}
//删除n节点的下一个节点
void remove(list *n){
    if(n->next == nullptr){
        return;
    }
    list *p = n->next;
    list *n1 = p->next;
    n->next = n1;
    delete p;
}
//访问索引index的节点
list *access(list *head, int index){
    for(int i = 0; i < index; i++){
        if(head == nullptr){
            return nullptr;
        }
        head = head->next;
    }
    return head;
}
//查找值为target的节点,输出索引
int find(list *head, int target){
    int index = 0;
    while(head != nullptr){
        if(head->value == target){
            return index;
        }
        head = head->next;
        index++;
    }
    return -1;
}

int main(){
    //创建节点
    list *n1 = new list(1);
    list *n2 = new list(2);
    list *n3 = new list(3);
    //连接节点
    n1->next = n2;
    n2->next = n3;
    //测试函数
    list *p = new list(10);
    insert(n1, p);
    remove(n2);
    list *p1 = access(n1, 1);
    cout << find(n1, 10) << endl;

    return 0;
}