分类	描述
单向链表	每一个节点包含了数据块和指向下一个节点的指针
双向链表	每一个节点包含了数据块和指向下一个节点的指针以及指向前一个节点的指针

咋们先来看单向链表:

单向链表

单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点 (node)?，每一个节点包含了数据块(data)和指向下一个节点的指针(next)，链表有一个头节点，图中以?head?表示。可以看出，??head?指向第一个元素，第一个元素的?next?又指向第二个元素……直到最后一个元素，该元素不再指向其他元素，它称为表尾，它的?next?为空(NULL)，链表到此结束。

可以看到，要找链表中的某一元素，必须先找到上一个元素，根据它提供的下一个元素的地址才能找到下一个元素。如果不提供头指针，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。

我们使用数组模拟的方法来学习链表。我们创建一个结构体，这个结构体有两个?𝑖𝑛𝑡int?型的变量，分别是data?和next?，data?就是链表当前节点存储的数据，next?指向下一个节点的节点编号（在数组中的编号，这样可以避免使用指针）(讲的真好!!~~)。

die码:

struct node{  //next即后面节点的编号，data就是需要维护的数据
    int next,data;
}a[10000];
int head;    //head即头指针
//head节点是头结点， 不存储数据， 作用只是用来找到链表的第一个节点。

?链表的常用操作

操作	描述
查找	找到符合条件的节点
插入	添加一个新节点
删除	删除一个存在的节点

查找操作

如何根据给出的数据，找到链表中符合条件的节点呢？需要从头节点开始，逐个向后遍历节点，比较?p?的?data?同待查找的数据是否相同，相同则返回当前节点。

struct node{  //next即后面节点的编号，data就是需要维护的数据
    int next,data;
}a[10000];
int head; //head即头节点的编号
node find(int value){
    int p=head; //从
    while(a[p]!=NULL){
        if(value==a[p].data)
            return a[p];
        p=a[p].next;
    }
    return NULL;
}

插入操作?

我们先通过一个选择题了解插入操作

在一个单链表中，若要在p节点后，插入一个q节点，则执行（??? ）

A. p -> next = q -> next; q -> next = p;

?B.q -> next = p -> next; p -> next = q;

?C.p -> next = q -> next; p -> next = q;

?D.q -> next = p -> next; p = q;

?答案:B

分析思路:

若要在p节点后，插入一个q节点，则需要:q -> next = p -> next;?? ?p -> next = q;

链表如何实现插入操作呢？如果我们想在第?p?个节点之后插入一个新节点，因为我们不能像使用数组一样直接访问下标，链表只能头遍历，直到走到第?p?个节点。

到达第?p?个节点之后，我们需要先将新节点的next?指向当前?p?节点next?指向的节点，再将?p?节点的next?指向这个新的节点?

struct node{ //next即后面节点的编号，data就是需要维护的数据
    int next,data;
}a[10000];
int head;  //head即头节点的编号
//注意要使用引用传递
void insert(int newIndex, node &pre){
    a[newIndex].next=pre.next;
    pre.next=newIndex;
}

?删除操作

删除与插入操作类似，如果我们想要删除第?p?个节点，那么我们先要从头遍历到第p?1?的节点，将p?1?节点的next?指向?p?的next?，同时，那么第?p?个节点就从当前的链表中移除了。?

struct node{    //next即后面节点的编号，data就是需要维护的数据
    int next,data;
}a[10000];
int head;    //head即头节点的编号
void delete(node &delNode, node &pre){
    pre.next=delNode.next
}

?链表与数组

操作	链表	数组
查找	从头节点开始查找	从下标?00?开始查找
插入	很快，因为只需要修改?𝑝𝑟𝑒pre?以及新节点的?𝑛𝑒𝑥𝑡next?编号	所有后面的节点都要向后移?11?位
删除	很快，因为只需要修改?𝑝𝑟𝑒pre?的?𝑛𝑒𝑥𝑡next?编号	所有后面的节点都要向前移?11?位