数据结构--利用Python实现常用的链表结构

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。如下图所示：

链表的分类

单向链表：双向链表：循环链表：如下图给出区别：

数据结构--利用Python实现常用的链表结构

单向链表的C语言实现（插入数据）

数据结构--利用Python实现常用的链表结构

双向链表的C语言实现（插入数据, 删除数据）

// 节点定义
typedef struct DListElement
{
    void * data;
    struct DListElement_ *prev;
    struct DListElement_ *next;
}DListElement;
// 链表定义
typedef struct DList_
{
    int size;
    DListElement *head;
    DListElement *tail;
}Dlist;
3、从某个节点的头部插入
int dlist_ins_prev(Dlist *list, DListElement *element, const void *data)
{
    DListElement *new_element;
    if (element == NULL && list->size != 0)//给定的节点无效
        return -1;
    if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
        return -1;
    new_element->data = (void *)data;
    if (list->size == 0)//插入的为头节点
    {
        list->head = new_element;
        list->tail = new_element;
        new_element->prev = NULL;
        new_element->next = NULL;
    }
    else//剩下的情况插入操作都是一样的
    {
        element->prev->next = new_element;
        new_element->prev = element->prev;
        element->prev = new_element;
        new_element->next = element;
    }
    list->size++;
    return;
}
// 从某个节点的尾部插入
int dlist_ins_next(Dlist *list, DListElement *element, const void *data)
{
    DListElement *new_element;
    if (element == NULL && list->size != 0)
        return -1;
    if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
        return -1;
    new_element->data = (void *)data;
    if (list->size == 0)//插入的为头节点
    {
        list->head = new_element;
        list->tail = new_element;
        new_element->prev = NULL;
        new_element->next = NULL;
    }
    else
    {
        if (element->next == NULL)//插入的为尾节点
        {
            new_element->next = NULL;
            list->tail = new_element;
        }
        else
        {
            new_element->next = element->next;
            element->next->prev = new_element;
        }
        element->next = new_element;
        new_element->prev = element;
    }
    list->size++;
    return;
}
// 删除节点
int dlist_rm_node(Dlist *list, DListElement *element, void **data)
{
    if (element == NULL || list->size == 0)
        return -1;
    //这里有一个关于二重指针作为传出参数的操作，主要原因是，因为我们需要传出的是一个一重指针的值，所以需要传入他的地址，即二重指针来获取。如果传入一重指针，则最后的结果和两个变量的问题一样。
    *data = element->data;//获取节点的数据
    if (element->prev == NULL)//删除头部节点
    {
        list->head = element->next;
        list->head->prev = NULL;
    }
    if (element->next == NULL)//删除尾部节点
    {
        list->tail = element->prev;
        list->tail->next = NULL;
    }
    else//删除中间节点
    {
        element->prev = element->next;
        element->next->prev = element->prev;
    }
    if (element != NULL)
    {
        free(element);
    }
    list->size--;
    return;
}
// 链表的遍历
//遍历整个链表
int dlist_ergodic(Dlist *list)
{
    DListElement *p;
    p = list->head;
    while (p->next != NULL)
    {
        printf("%d-", (int)(p->data));
        p = p->next;
    }
    printf("%d-", (int)(p->data));
    printf("\n链表的长度为%d.\n", list->size);
    return;
}

总结：

单链表：如果访问任意结点每次只能从头开始顺序向后访问，只能在当前结点后插入和删除

单循环链表：可以从任何一个结点开始，顺序向后访问到达任意结点，

双向链表：可以从任何结点开始任意向前向后双向访问操作，可以在当前结点前面或者后面插入，可以删除前趋和后继

数据结构--利用Python实现常用的链表结构

单向链表的C语言实现（插入数据）

双向链表的C语言实现（插入数据, 删除数据）

总结：

相关推荐