数据结构_知识点_循环链表&双链表

1. 循环链表

与单链表基本无异，但有如下两点需要注意：
(1)最后一结点的指针域必须指向头结点，这样才能循环
（注意，指向的是没有存数据头结点，而非第一个存有数据的结点）

(2)使用尾指针而非头指针表示链表，这样找寻头结点和尾结点的时间复杂度为O(1)。

2. 双链表定义

//结点定义，每个结点除了数据项还有前驱指针和后继指针
typedef struct Node
{
    elemType data;
    Node *prior,*next;  
};

typedef Node *List;

3. 创建双链表

这里值得注意的是，链表为空是，头结点的前驱指针和后继指针均指向它自己。
因而在创建或插入结点的时候，要记得把头结点的前驱指针修改成最后一个结点。

4. 插入和删除

插入：查找到插入位置，修改前驱结点和后继结点的指针

bool insert(List &l,int i,elemType e)
{
    Node *p,*q,*s;
    int j;

    p = l->next;
    
    //找寻插入位置 
    for(j = 1;j<i && p;j++)
    {
        p = p->next;
    }
    
    s = (Node *)malloc(sizeof(Node));
    s->data = e;
     
    s->prior = p->prior;
    s->next = p;
    
    //修改前驱结点的后继指针 
    p->prior->next = s;
    //修改后继结点的前驱指针 
    p->prior = s;   
}

删除：找到删除结点，修改前驱结点的后继指针，后继结点的前驱指针

bool deleteNode(List &l,int i)
{
    Node *p;
    int j;
    
    p = l->next;
    
    for(j = 1;j<i;j++)
    {
        p = p->next;
    }
    
    //修改前驱结点的后继指针 
    p->prior->next = p->next;
    //修改后继结点的前驱指针 
    p->next->prior = p->prior;
    //释放结点 
    free(p);
}