链表入门

相比于数组而言，链表是跳跃式索引的结构。

链表分为带头结点的链表和不带头结点的链表，前者在处理链表为空或仅一个元素时有更强的通用性，而后者在处理类似问题时通常做额外处理来避免出错。

链表常见问题

1. 链表为空或仅一个元素问题
2. 删除某结点失去后序索引问题

链表的头结点往往要单独处理。

结点定义

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;
    }
}

插入和删除操作

数组的插入和删除

• 插入：从尾部元素依次向后移一格，直至待出入点处。插入元素。注意数组容量。

• 删除：从待插入点处至尾，依次前移一格。

  
  

链表的插入和删除

• 插入
  1. 创建结点
  2. 更改结点的next
  3. 更改插入点前结点的next
• 删除
  1. 保存待删结点的地址
  2. 更改删除点前结点的next

  3. 删除目标结点

     
     

插入

要点：定位前节点，新节点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个指针值。