c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

（1）定义双向链表的基本结构
复制代码 代码如下:
typedef struct _DOUBLE_link_NODE 
{ 
    int data; 
    struct _DOUBLE_link_NODE* prev; 
    struct _DOUBLE_link_NODE* next; 
}DOUBLE_link_NODE; 

（2）创建双向链表节点
复制代码 代码如下:
DOUBLE_link_NODE* create_double_link_node(int value) 
{ 
    DOUBLE_link_NODE* pDlinkNode = NULL; 
    pDlinkNode = (DOUBLE_link_NODE*)malloc(sizeof(DOUBLE_link_NODE)); 
    assert(NULL != pDlinkNode); 

    memset(pDlinkNode, 0, sizeof(DOUBLE_link_NODE)); 
    pDlinkNode->data = value; 
    return pDlinkNode; 
} 

（3）删除双向链表
复制代码 代码如下:
void delete_all_double_link_node(DOUBLE_link_NODE** pDlinkNode) 
{ 
    DOUBLE_link_NODE* pNode; 
    if(NULL == *pDlinkNode) 
        return ; 

    pNode = *pDlinkNode; 
    *pDlinkNode = pNode->next; 
    free(pNode); 
    delete_all_double_link_node(pDlinkNode); 
}

（4）在双向链表中查找数据
复制代码 代码如下:
DOUBLE_link_NODE* find_data_in_double_link(const DOUBLE_link_NODE* pDlinkNode, int data) 
{ 
    DOUBLE_link_NODE* pNode = NULL; 
    if(NULL == pDlinkNode) 
        return NULL; 

    pNode = (DOUBLE_link_NODE*)pDlinkNode; 
    while(NULL != pNode){ 
        if(data == pNode->data) 
            return pNode; 
        pNode = pNode ->next; 
    } 

    return NULL; 
} 

（5）双向链表中插入数据
复制代码 代码如下:
STATUS insert_data_into_double_link(DOUBLE_link_NODE** ppDlinkNode, int data) 
{ 
    DOUBLE_link_NODE* pNode; 
    DOUBLE_link_NODE* pIndex; 

    if(NULL == ppDlinkNode) 
        return FALSE; 

    if(NULL == *ppDlinkNode){ 
        pNode = create_double_link_node(data); 
        assert(NULL != pNode); 
        *ppDlinkNode = pNode; 
        (*ppDlinkNode)->prev = (*ppDlinkNode)->next = NULL; 
        return TRUE; 
    } 

    if(NULL != find_data_in_double_link(*ppDlinkNode, data)) 
        return FALSE; 

    pNode = create_double_link_node(data); 
    assert(NULL != pNode); 

    pIndex = *ppDlinkNode; 
    while(NULL != pIndex->next) 
        pIndex = pIndex->next; 

    pNode->prev = pIndex; 
    pNode->next = pIndex->next; 
    pIndex->next = pNode; 
    return TRUE; 
} 

（6）双向链表中删除数据
复制代码 代码如下:
STATUS delete_data_from_double_link(DOUBLE_link_NODE** ppDlinkNode, int data) 
{ 
    DOUBLE_link_NODE* pNode; 
    if(NULL == ppDlinkNode || NULL == *ppDlinkNode) 
        return FALSE; 

    pNode = find_data_in_double_link(*ppDlinkNode, data); 
    if(NULL == pNode) 
        return FALSE; 

    if(pNode == *ppDlinkNode){ 
        if(NULL == (*ppDlinkNode)->next){ 
            *ppDlinkNode = NULL; 
        }else{ 
            *ppDlinkNode = pNode->next; 
            (*ppDlinkNode)->prev = NULL; 
        } 

    }else{ 
        if(pNode->next) 
            pNode->next->prev = pNode->prev; 
        pNode->prev->next = pNode->next; 
    } 

    free(pNode); 
    return TRUE; 
} 

（7）统计双向链表中数据的个数
复制代码 代码如下:
int count_number_in_double_link(const DOUBLE_link_NODE* pDlinkNode) 
{ 
    int count = 0; 
    DOUBLE_link_NODE* pNode = (DOUBLE_link_NODE*)pDlinkNode; 

    while(NULL != pNode){ 
        count ++; 
        pNode = pNode->next; 
    } 
    return count; 
} 

（8）打印双向链表中数据
复制代码 代码如下:
void print_double_link_node(const DOUBLE_link_NODE* pDlinkNode) 
{ 
    DOUBLE_link_NODE* pNode = (DOUBLE_link_NODE*)pDlinkNode; 

    while(NULL != pNode){ 
        printf("%dn", pNode->data); 
        pNode = pNode ->next; 
    } 
} 

今天我们讨论的双向链表是非循环的，大家可以考虑一下如果改成循环双向链表，应该怎么写？如果是有序的循环双向链表，又该怎么写？