链表及其基本操作

1.单链表：

1.1定义/性质：

• 链表是线性表的链式存储方式。

• 单链表通过指针线性遍历，删除/增加节点时间复杂度为O(1）,访问节点时间复杂度为O(n)。

• 单链表分为带头结点和不带头结点两种，带头结点是为了方便统一操作（删除和插入操作都是通过指next指针来完成的，当只有一个节点的时候做删除操作/没有节点的时候做插入操作，这两种情况要特殊处理）。

对节点的描述如下：

typedef struct LNode{ElemType Data;//数据域struct Lnode next;//指针域
}Node;

1.2单链表的操作：

默认下列情况都有头结点。

1.2.1初始化（创建）：

该操作初始化头指针和头结点：

Node* init(){Node* L=(Node*)malloc(sizeof(struct LNode));L->next=NULL;return L;
}

1.2.2插入操作：

有头插法和尾插法两种方法：

对于头插法，先插入的在后，后插入的在前：

Node* HeadInsert(){Node* tmp=(Node*)malloc(sizeof(struct LNode));//创建新节点tmp->next=L->next;//新节点指向头节点的指向L->next=tmp;//头结点指向新节点return L;
}

对于尾插法，要设置一个尾指针，通过尾指针完成插入

1.2.3删除操作：

删除操作要通过next指针完成，并且单链表是单向的，所以只能删除遍历到的节点的下一个节点（只能改变该节点的指向，也就是下一个节点）。

bool Delete(Node* L,int P){//删除值为p的节点for(Node* i=L,i;i=i->next){if(L->next->Data=P){//如果下一个节点的值为PL->next=L->next->next;return true;}}return false;
}

1.2.4反转操作：

法一：空间复杂度O(n)

遍历链表并使用头插法建立一个新链表即可。

法2：空间复杂度O(1)

借助两个辅助指针p,q；

初始p指向头结点（p=L），原指针L指向尾节点的指向(L=NULL）；

具体步骤：p用于遍历链表，每次操作q取出p遍历到的节点并且连接到L的前面（包括头结点都逆转了），再让L指向q指向的（L=q）。

1.3其他单链表：

循环单链表：

尾节点指向头结点而不是NULL，判断链表是否为空的方法是尾节点的指针是否等于头结点的指针。

2双链表：

在单链表的基础上，每个节点增加了一个指向前驱的指针pre。

2.1双链表的操作：

在做双链表的操作时要注意每一步的先后顺序。

对于该双链表：

2.1.1插入操作：

在p指针指向的节点后插入一个节点a：

1. 更新a的前后指针；

2. 通过a来更新p,q的指针，由于我们的指针是p，所以先更新q再更新p（q要通过p得到）。

2.1.2删除操作

假设a节点已经插入了，删除节点a:

先更新q再更新p即可。