相比于数组而言，链表是跳跃式索引的结构。
链表分为带头结点的链表和不带头结点的链表，前者在处理链表为空或仅一个元素时有更强的通用性，而后者在处理类似问题时通常做额外处理来避免出错。
链表常见问题
- 链表为空或仅一个元素问题
- 删除某结点失去后序索引问题
链表的头结点往往要单独处理。
结点定义
struct node{
int data;
node* next;
};
遍历及相关操作
处理链表时通常传入链表头指针，因为某些操作通常会改变链表头指针，所以返回新链表的头指针。
遍历
要点：通过p=p->next来实现指针后移
void printLink(node* H){
node* p=H;
while(p){
std::cout<<p->data<<" ";
p=p->next;
}
std::cout<<'\b';
}
Tip:输出数组或链表时，为了防止多输出空格，可以输出'\b'退格符。
索引
要点：通过p=p->next来实现指针后移，至计数满或指针无效
node* pEle(node* H,size_t i){
if(H==nullptr)
return nullptr;
node* p=H;
for(size_t j=0;j<i;++j){
p=p->next;
if(p==nullptr)
return nullptr;
}
return p;
}
注意：因为如果需要对某结点做处理，该结点前的结点通常也会改变。所以经常要索引至该结点前一个结点。
求长
要点：遍历链表，如果当前指针有效，则计数加一。
size_t LinkLen(node* L){
size_t len=0;
node* p=L;
while(p){
++len;
p=p->next;
}
return len;
}
销毁
要点：从头节点开始逐个销毁。预先保存下个结点的地址，再删除当前结点。
void destroyLink(node* L){
node* p=L;
while(p){
node* temp=p->next;//保留剩下链表的头
delete p;
p=temp;
}
}
插入和删除操作
数组的插入和删除
- 插入：从尾部元素依次向后移一格，直至待出入点处。插入元素。注意数组容量。
-
删除：从待插入点处至尾，依次前移一格。
链表的插入和删除
- 插入
- 创建结点
- 更改结点的next
- 更改插入点前结点的next
- 删除
- 保存待删结点的地址
- 更改删除点前结点的next
-
删除目标结点
插入
要点：定位前节点，新节点next赋值前节点的next，前节点next赋值新节点
//插入元素:需要更改i-1项
int insertEle(node* L,size_t i,eletype e){
if(L==nullptr){
if(i==0){
L=new node;
L->data=e;
L->next=nullptr;
return 0;
}
else
return -1;
}
else{
node* p=pEle(L,i-1);
if(p==nullptr)
return -1;
node* newp=new node;
newp->data=e;
newp->next=p->next;
p->next=newp;
return 0;
}
}
删除
要点：定位前节点，保留待删节点地址temp，前节点next赋值temp的next，删除temp节点
int deleteEle(node* L,size_t i){
if(L==nullptr){
return -1;
}
else{
node* p=pEle(L,i-1);
if(p==nullptr)
return -1;
node* temp=p->next;
p->next=temp->next;
delete temp;
return 0;
}
}
创建:尾插法和头插法
- 尾插：用指针记录上次处理的结点，新节点加在其后面
- 头插：用指针记录上次处理的结点，加入到新节点后面
尾插
要点：新节点地址放入上次完成的节点的next中
//p指向上次完成的节点；新建node分配为newp；p的next赋值为newp；p=p->next
void createLinkT(node* &L,eletype* arr,size_t len){
L=new node;
L->data=arr[0];
node* p=L;
for(size_t i=1;i<len;++i){
node* newp=new node;
newp->data=arr[i];
p->next=newp;
p=newp;
}
p->next=nullptr;
}
头插
要点：上次完成的节点地址放入新节点的next中
void createLinkH(node* &L,eletype* arr,size_t len){
if(len==0){
L=nullptr;
return;
}
node* p=new node;
p->data=arr[len-1];
p->next=nullptr;
/*for(size_t i=len-2;i>=0;--i){
node* newp=new node;
newp->data=arr[i];
newp->next=p;
p=newp;
}*/
for(size_t i=0;i<len-1;++i){
node* newp=new node;
newp->data=arr[len-1-i];
newp->next=p;
p=newp;
}
L=p;
}
// tip:如果没有 if(i==0) break;语句会报错，因为i是size_t，当i为0时，减一就变成了一个很大的数，依然是正的。循环不可能终止。
//在一个无符号数递减至0的过程中，应该特别注意.所以尽量用递增式计数
循环链表和双向链表
循环链表：最末结点指向头结点。
- 遍历时需要预先记录头结点的地址，用来判断是否遍历完成的依据。
- 索引时可以循环索引计数，不必担心越界。
- 插入和删除时，额外注意特别情况。
- 为了便于使用，可以额外记录尾指针
双向链表：多了指向前驱的指针域。
- 向前索引更方便
- 插入删除时需要修改4个指针值。
