单链表需要注意的主要是在插入和删除的时候。

  • 1.插入链表的时候:需要有两种情况需要考虑,插入链表头和插入其他位置的时候。一般来说,要把一个元素插入到链表中,需要将新元素的next指针指向它之后的那个元素,然后将新元素位置之前的节点next指向新插入的元素,但是,当从链表头插入元素的时候,新元素之前没有别的节点,因此,在这种情况下,将新元素的next指针指向当前链表的头部,然后重置头结点指针,使其指向新的元素,另外需要注意的是,无论何时当插入的元素位于链表末尾时,都必须更新链表数据结构的tail成员使其指向新的节点。
  • 2.删除链表的时候:当移除目标节点是头节点的时候,目标节点之前并没有其他元素,因此。需要将链表的head成员指向目标节点的下一个元素

代码实现

#ifndef MYLIST_H
#define MYLIST_H
#include <stdlib.h>

//表示链表中的单个成员
typedef struct listElmt_
{   char *data; //数据
    struct listElmt_ *next; //下一个节点指针
}ListElmt;

//链表结构体
typedef struct list_
{

    int size; //数据大小
    int (*match)(const void*key1,const void* key2);
    void (*destroy)(void *data);
    ListElmt *head;//头节点
    ListElmt *tail;//尾节点
}List;

#define list_size(list)((list)->size)
#define list_head(list)((list)->head)
#define list_tail(list)((list)->tail)
#define list_is_head(list,element)((element)== list->head?1:0)
#define list_is_tail(list,element)((element)->next == NULL?1:0)
#define list_data(element)(element->data)
#define list_next(element)(element->next)


class mylist
{
public:
    mylist();

public:
    void list_init(List* list,void(*destroy)(void* data));
    void list_destroy(List*list);
    int  list_ins_next(List*list,ListElmt* listElmt,const void *data);
    int  list_rem_next(List*list,ListElmt*listElmt,void**data);

};

#endif // MYLIST_H
#include "mylist.h"

mylist::mylist()
{
}
# if 1
void mylist::list_init(List *list, void (*destroy)(void *))
{
    list->size =0;
    list->head = NULL;
    list->tail = NULL;
    return;
}

void mylist::list_destroy(List *list)
{
    void *data;
    while(list_size(list) > 0)
    {
        if(list_rem_next (list,NULL,(void**)data) == 0 && (list->destroy!=NULL))
        {
            list->destroy(data);
        }
    }
    //memset(list,0,sizeof(list));
    return;
}

int mylist::list_ins_next(List *list, ListElmt *listElmt, const void *data)
{
    ListElmt* newElmt = new ListElmt;
    newElmt->data  = (char*)data;
    //这里需要如要注意如果插入的是头节点
    if(listElmt == NULL)
    {
        //插入头节点
        if(list_size(list) == 0)
            list->tail= newElmt;
        newElmt->next = list->head->next;
        newElmt = list->head;

    }
    else
    {
        //如果插入的节点识尾节点
        if(listElmt->next == NULL)
            list->tail = NULL;
        newElmt->next = listElmt->next;
        listElmt->next =newElmt;
    }
    list->size++;
    return 0;
}

int mylist::list_rem_next(List *list, ListElmt *listElmt, void**data)
{
    ListElmt* oldElmt ;
    if((list->size) == 0)
        return -1;

    //移除头节点
    if(listElmt == NULL)
    {
        //数据
        *data = list->head->data;
        list->head=list->head->next;
        if(list_size(list) == 1)
        {
            list->tail = NULL;
        }

    }
    else
    {
        //使用后继节点将当前节点覆盖,删除后继节点
        *data = listElmt->next->data;
        listElmt->next = listElmt->next->next;
        oldElmt = listElmt->next;
        if(listElmt->next = NULL)
            return -1;

    }
    delete oldElmt;
    list->size--;
    return 0;
}
#endif

链表反转的实现,这里有很好的讲解,我根据讲解自己画图实现了下,这里附上讲解的链接

发表评论

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