双链表的实现

需要注意的地方:
– 前插:在前插入的时候需要判断此时链表是否为空链表
– 后插:在后插的时候,需要判断传进来的的节点是不是尾节点
– 删除:删除的时候分情况处理,删除的如果是头部节点是一种情况,删除的如果是尾节点是一种情况,删除的是中间节点
– 更新链表指针的需要理清关系,一般是需要重新链接四个指针。

具体代码

dlist.h

#ifndef DLIST_H
#define DLIST_H

typedef struct DListElmt_
{
    void* data;
    struct DListElmt_ *prev;
    struct DListElmt_ *next;

}DListElmt;

typedef struct DList_
{
    int size;
    int (*match)(const void*key1,const void*key2);
    void (*destory)(void *data);
    DListElmt* head;
    DListElmt* tail;
}DList;

#define dlist_size(list)((list)->size)
#define dlist_head(list)((list)->head)
#define dlist_tail(list)((list)->tail)
#define dlist_is_head(element)((element)->prev == NULL?1:0)
#define dlist_is_tail(element)((element)->next == NULL?1:0)
#define dlist_data(element)((element)->data)
#define dlist_next(element)((element)->next)
#define dlist_prev(element)((element)->prev)


class dlist
{
public:
    dlist();

public:
    void dlist_init(DList*list,void(*destory)(void *data));
    void destory(DList* list);
    int dlist_ins_next(DList* list,DListElmt*element,const void*data);
    int dlist_ins_prev(DList* list,DListElmt*element,const void*data);
    int dlist_remove(DList* list,DListElmt*element,void **data);
};

#endif // DLIST_H
dlist.cpp

#include "dlist.h"
#include <stdlib.h>
#include <memory.h>
dlist::dlist()
{
}

void dlist::dlist_init(DList *list, void (*destory)(void *))
{
    list->head = NULL;
    list->size = 0;
    list->tail = NULL;
    list->destory=destory;
}

void dlist::destory(DList *list)
{
    void *data;

    while(dlist_size(list) > 0)
        {
        if(dlist_remove (list,dlist_tail(list),(void**)data) == 0 && list->destory!=NULL)
            {
            list->destory(data);
        }
    }
    memset (list,0,sizeof(DList));
    return ;
}

int dlist::dlist_ins_next(DList *list, DListElmt *element, const void *data)
{
    DListElmt *newElmt = new DListElmt;
    if(element == NULL && dlist_size(list) != 0)
        return -1;
    newElmt->data = const_cast<void*>(data);

    if(dlist_size(list) == 0)
    {

        list->head = newElmt;
        list->tail = newElmt;
        newElmt->prev = NULL;
        newElmt->next = NULL;

    }
    else
    {
        newElmt->next = element->next;
        //需要判断element 是不是尾
        if(element->next = NULL)
            list->tail= newElmt;
        else
            element->next->prev = newElmt;
        newElmt->prev = element;
        element->next = newElmt;


    }
    list->size++;
    return 0;
}

int dlist::dlist_ins_prev(DList *list, DListElmt *element, const void *data)
{
    DListElmt *newElmt = new DListElmt;
    if(element == NULL && dlist_size(list) == 0)
        return -1;

    newElmt->data = (void*)data;
    //如果插入的是一个空链表
    if(dlist_size(list) == 0)
    {
        list->head = newElmt;
        list->head->prev = NULL;
        list->head->next = NULL;
        list->tail = newElmt;

    }
    else
    {
        newElmt->next = element;
        newElmt->prev = element->prev;

        if(element->prev == NULL)
        {
            list->head = newElmt;
        }
        else
        {
            element->prev->next=newElmt;
        }
        element->prev = newElmt;
    }

    list->size++;
    return 0;
}

int dlist::dlist_remove(DList *list, DListElmt *element, void **data)
{
    if(element == NULL || dlist_size(list)==0)
        return -1;

    *data = element->data;
    if(element == list->head)
    {
        list->head = element->next;
        //删除的头节点
        if(list->head == NULL)
            list->tail=NULL;
        else
            element->next->prev= NULL;//将下一个节点设为头节点
    }
    else
    {
        //如果删除的节点是尾节点
        if(element->next == NULL)
            list->tail = element->prev;//更新尾节点
        else
            element->next->prev = element->prev;
    }

    delete element;
    list->size--;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注