链表，是一种链式数据结构，大概长下面这样：

链表的节点由两部分组成：数据域和地址域。地址域包括前驱指针和后继指针，需要注意的是，不同类型的链表，节点是不一样的。

单链表

单链表，顾名思义，即链表节点地址域仅含有后继指针的链表。

单链表的插入元素操作

上一张图给大家理解下：

最下方的元素是待插入元素，上面的是链表，要插入元素，只需将插入位置前一个节点的后继指向这个节点，把这个节点的后继指向后一个节点。

核心伪代码如下（q为待插入节点，p为前一个节点）：

q.next=p.next; p.next=q;

单链表的删除元素操作

与插入元素十分相似，只需将待删除节点的前一个节点的后继指向待删除节点的后继节点。

核心伪代码如下（q为待删除节点，p为前一个节点）：

p.next=q.next;

单链表的修改元素操作

这个不用讲了吧，直接修改就OK了。

单链表的遍历

核心核心伪代码如下：

for(int i=head;i;i=i.next) //do something...

单链表的实现

首先，我们需要一个虚拟节点：head。它是整个链表最开始的部分，然后，其他的只要按照上面所说的写代码就行了。

代码如下（数组版）：

template<class T>struct list { struct node//链表节点 { T data; int next; }; node a[100010]; int t=0; void push(T num,int cnt)//在第cnt个节点后插入节点num; { if(!t)a[1]=(node){num,0},t=1; for(int i=1;i;i=a[i].next) if(!(--cnt)) { a[++t].next=a[i].next; a[i].next=t; a[t].data=num; break; } } void pop(int cnt)//删除第cnt个节点 { for(int i=1;i;i=a[i].next) if((--cnt)==1) { a[i].next=a[a[i].next].next; break; } } }; //使用方法： //定义： list</*数据类型*/>/*链表名称*/ //插入： /*链表名称*/.push(...,...); //删除： /*链表名称*/.pop(...);

指针版：

template<class T>struct list { struct node { T data; node *next; }*head,*p,*q; void push(int i,T x) { node *P,*S; int j; P=head; j=0; while((P!=NULL)&&(j<i-1)) { P=P->next; j++; } S=new node; S->data=x; S->next=P->next; P->next=S; } void pop(int i) { node *P,*S; int j; P=head; j=0; while((P->next!=NULL)&&(j<i-1)) { P=P->next; j++; } S=P->next; P->next=P->next->next; free(S); } void start()//初始化，使用前必须初始化！！！ { head=new node; q=head; } }; //使用方法同数组版，但必须初始化

双向链表

单链表，顾名思义，即链表节点地址域含有前驱指针和后继指针的链表。

双向链表的操作

插入、删除：和单链表差不多，只是增加了前驱指针的修改。

修改：直接修改即可。

遍历：可以从两个方向遍历。

伪代码不放了。

双向链表的实现

数组版：

template<class T>struct list { struct node { T data; int next,last; }; node a[100010]; int t=0; void push(T num,int cnt) { if(!t)a[1]=(node){num,0,0},t=1,sum++; for(int i=1;i;i=a[i].next) if(!(--cnt)) { a[++t].next=a[i].next; a[i].next=t; a[a[t].next].last=t; a[t].last=i; a[t].data=num; break; } } void pop(int cnt) { for(int i=1;i;i=a[i].next) if((--cnt)==1) { a[i].next=a[a[i].next].next; a[a[i].next].last=i; break; } } };

指针版：

template<class T>struct list { struct node { T data; node *next,*pre; }*head,*p,*q; void push(int i,T x) { node *P,*S; int j; P=head; j=0; while((P->next!=NULL)&&(j<i)) { P=P->next; j++; } S=new node; S->pre=p->pre; S->data=x; S->next=P; P->pre->next=S; } void pop(int i) { node *P,*S; int j; P=head; j=0; while((P->next!=NULL)&&(j<i-1)) { P=P->next; j++; } P->pre->next=P->next; P->next->pre=p->pre; free(S); } void start() { head=new node; q=head; } };

循环链表

即头尾相连的链表，分单循环链表和双向循环链表。

代码不放了，就比上面的多了几句，相信聪明的同学能够自己写出来。

转载于:https://www.cnblogs.com/Naive-Cat/p/10706903.html