1.4 循环链表、双向链表

单向循环链表

循环链表(Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。
当链表遍历时，判别当前指针 p是否指向表尾结点的终止条件不同。在单链表中，判别条件为 p!=NULL或 p->next!=NULL，而循环单链表的判别条件为p!=L 或 p->next!=L（L为头节点）。

双向链表

链式存储结构的节点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他节点。若要寻查结点的直接前驱、则必须从表头指针出发。换句话说，在单链表中，查找直接后继的执行时间为 〇(1)，而查找直接前驱的执行时间为 O(n)为克服单链表这种单向性的缺点，可利用双向链表(Double Linked List)。在双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

typedef int ElemType;

typedef struct node
{
    ElemType data;
    struct node* prev,*next;
}Node;

插入双链表（头插法）：

typedef struct node
{
    ElemType data;
    struct node* prev,*next;
}Node;

int insertHead(Node* L,ElemType e)//L为头链表
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = L->next;
    p->prev = L;

    if(L->next != NULL)
    {
        L->next->prev = p;
    }

    L->next = p;
    return 1;
}

插入双链表（尾插法）：

typedef struct node
{
    ElemType data;
    struct node* prev,*next;
}Node;

Node* Returntail(Node* L)
{
    while(L->next !=NULL)
    {
        L = L->next;
    }
    return L;
}

Node* insertTail(Node* tail,ElemType e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->prev = tail;
    p->next = NULL;

    tail->next = p;
    return p;
}

插入双链表（指定位置插入）：

typedef struct node
{
    ElemType data;
    struct node* prev,*next;
}Node;

int insertNode(Node* L,int pos,ElemType e)
{
    Node* p = L;
    int i = 0;

    //找到要插入结点的上一个结点
    while(i < pos-1)
    {
        p = p->next;
        i++;
        if(p == NULL)
        {
            return 0;
        }
    }

    Node* q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    q->prev = p;
    p->next = q;
    if(q->next != NULL)
    {
        q->next->prev = q;
    }
    return 1;
}

双向链表删除结点：

typedef struct node
{
    ElemType data;
    struct node* prev,*next;
}Node;

int DeleteNode(Node* L,int pos)
{
    Node* p;
    int i = 0;

    //找到要删除结点的上一个节点
    while(i < pos-1)
    {
        L = L->next;
        i++;
        if(L == NULL)
        {
            return 0;
        }
    }
    //开始删除节点,L目前是删除节点的前置结点
    p = L->next;
    if(p == NULL)
    {
        return 1;
    }
    else
    {
        L->next = p->next;
        if(p->next != NULL)
        {
            p->next->prev = L;
        }
        free(p);
        return 1;
    }
}