C 链表添加和删除

Question

typedef struct _readyQ {
    pcb_t *pcb;
    struct _readyQ  *next;
} readyQ;

static readyQ *ready_queue_head = NULL, *ready_queue_tail = NULL;
static void submit_ready_request(pcb_t *pcb);

static void submit_ready_request(pcb_t *pcb)
{
    readyQ *r;
    /* Build I/O Request */
    r = malloc(sizeof(readyQ));
    assert(r != NULL);
    r->pcb = pcb;
    r->next = NULL;

    pthread_mutex_lock(&readyQ_mutex);
    /* Add request to head of queue */
    if (ready_queue_tail != NULL)
    {
        ready_queue_tail->next = r;
        ready_queue_tail = r;
    }
    else
    {
        ready_queue_head = r;
        ready_queue_tail = r;
    }
    pthread_mutex_unlock(&readyQ_mutex);
}

最初 head/tail 都是 NULL。
所以，当我第一次通过 submit_ready_request 添加时，我会去其他部分

ready_queue_head = r;
ready_queue_tail = r;

都指向同一个readyQ r。

现在，当我添加另一个时，它将转到

ready_queue_tail->next = r;
ready_queue_tail = r;

我想知道在这种情况下， ready_queue_head->next上面的代码执行后会指向r吗？

因为我试图通过这个删除但它不起作用

readyQ *r;
r = malloc(sizeof(readyQ));
if (ready_queue_head != NULL) {   //not empty so remove
       r = ready_queue_head;  
       if(ready_queue_head->next != NULL){   
          ready_queue_head = ready_queue_head->next; 
        } else {    //only one in the queue
          ready_queue_head = NULL;
          ready_queue_tail = NULL;
       }
}

Answer 1

一、没有malloc()应该在 pop 操作上需要。其次，你的 push 和 pop 都过于迂腐。非常仔细地盯着这个推送和弹出逻辑，在你知道它是如何工作之前不要合并它。您需要考虑两者如何协同工作才能真正掌握简单性。

首先是推送逻辑。以下假设 r是新分配的节点下一个指针为 NULL :

if (ready_queue_head != NULL)
    ready_queue_tail->next = r;
else
    ready_queue_head = r;
ready_queue_tail = r;

同样，流行逻辑

r = ready_queue_head;
if (r != NULL) 
   ready_queue_head = r->next

在您的脑海中考虑一些测试用例。

推逻辑

在空列表中插入新节点时会发生什么？由于列表为空，头指针将为 NULL，因此头指针和尾指针最终都将引用新节点。

插入一个只有一个元素的列表怎么样？由于头指针非空，所以也必须有一个有效的尾指针，所以将其next指针设置为新节点，然后将尾指针设置为新节点。

如果插入前列表中有多个节点，情况会改变吗？一点也不。

流行逻辑

当你从一个空队列请求一个 pop 时会发生什么？由于空队列上的头指针为NULL，返回值r也将为 NULL。

当您从单元素队列请求 pop 时会发生什么？头指针引用单个元素，所以 r将被正确设置。自 r非空，头指针前进到它的 next指针，它将为 NULL。该列表现在为空(head 为 NULL)并且返回节点指针已设置。

一个包含多个节点的列表呢？单节点弹出中的所有内容都适用，但退出时头指针不会为 NULL，因此列表仍然不为空(但比以前短一个元素。再次，正确设置了返回节点指针 r。

无论如何，我希望它有所帮助。很难理解尾指针在所有这些中的参与程度有多大，但在您考虑一段时间之后就不会了。另外，这是一个非常复杂的 is-empty 逻辑。

return (ready_queue_head != NULL);