时间戳

首页 > 解决方案 > 链表没有删除/添加第一个头

c - 链表没有删除/添加第一个头

问题描述

我正在创建一个在匹配时添加/删除头部的程序，但是它不起作用。这两个功能有什么问题吗？我有更多的链表代码，但这是我在程序中使用的两个。

它们应该类似于堆栈的推送/弹出功能

linkedList* createLinkedList()
{
    linkedList* list;
    list = malloc(sizeof(linkedList));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}
void insertStart(linkedList* list, void* inData)
{
    listNode* node;
    node = (listNode*)malloc(sizeof(listNode));
    node->data = inData;
    list->size++;
    if (list->head == NULL)
    { 
        list->head = node;
        list->tail = node;
        node->next = NULL;
        node->prev = NULL;
    }
    else
    { 
    
        list->head->prev = node;
        node->next = list->head;
        node->prev = NULL;
        list->head = node;
    }
}

void* removeStart(linkedList* list)
{
    listNode* removed = NULL;
   /* void* outData = NULL;*/
 
        removed = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;
        list->size -= 1;
       /* outData = removed->data;
        free(removed);*/
   
    return removed;
}

标签： clinked-liststackdoubly-linked-listfunction-definition

解决方案

虽然insertStart可以正常工作，但可以大大简化：

void insertStart(linkedList* list, void* inData)
{
    listNode* node = malloc(sizeof *node);
    node->data = inData;
    node->next = list->head;
    node->prev = NULL;
    if (list->head)
        list->head->prev = node;
    else
        list->tail = node;
    list->head = node;
    list->size++;
}

然而，真正的问题是removeStart。它有几个明显的缺陷：

  1. 它不管理tail指针。
  2. 它假定列表是非空的。
  3. 返回的结果不正确。（你想返回数据成员；不是节点指针）

前者将完全破坏需要妥善管理的尾指针的一切；如果一个空列表，第二个将调用未定义的行为。最后一项只是监督。所有这些都可以用不到 20 行代码来解决：

void* removeStart(linkedList* list)
{
    void *data = NULL;

    if (list->head)
    {
        listNode* removed = list->head;
        list->head = removed->next;
        if (list->head)
            list->head->prev = NULL;
        else
            list->tail = NULL;
        data = removed->data;
        free(removed);
        --list->size;
    }
    return data;
}

推荐阅读