C单链列表的实现

Question

我意识到我的代码相当长，所以如果你的时间很短，我想主要就几件事发表意见：

1)返回INT_MIN以表示它是空的。

2) removeHead和removeTail函数。

欢迎加入更多的批评。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct node{
    int value;
    struct node *next;
}Node;

typedef struct
{
    Node* head;
    Node* tail;
}LinkedList;

void printListRec(Node* node);
void printHeadAndTail(LinkedList* list);
int printList(LinkedList* list);
int linkedListSize( LinkedList* list );
int searchForElement( LinkedList* list , int value );
int isEmpty( LinkedList* list );
int removeElement( LinkedList* list , int value);
int removeTail( LinkedList* list );
int removeHead( LinkedList* list );
void addTail( LinkedList* list , int value);
void addHead( LinkedList* list , int value);
LinkedList* initialize() ;

//implement a clear list function

int main()
{
    LinkedList* linkedlist = initialize();

    addHead(linkedlist , 1);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addHead(linkedlist , 2);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    removeTail(linkedlist);
    printHeadAndTail(linkedlist);
    printList(linkedlist);

    addTail(linkedlist , 3);
    printHeadAndTail(linkedlist);
    printList(linkedlist);



    return 0;
}

LinkedList* initialize() //creates linked list with no nodes, initializes head & tail to 0
{
    LinkedList* list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void addHead( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        newNode->next = list->head;
        list->head = newNode;
    }
    puts("Add head");
}

void addTail( LinkedList* list , int value)
{
    Node* newNode = malloc( sizeof(Node) );
    newNode->value = value;
    newNode->next = NULL;

    if( isEmpty(list) )
    {
        newNode->next = NULL;
        list->head = list->tail = newNode;
    }

    else
    {
        list->tail->next = newNode;
        list->tail = newNode;
    }
    puts("Add tail");
}

int removeHead( LinkedList* list )
{
    if(isEmpty(list))
        return INT_MIN;

    Node* nodeToDelete = list->head;
    int value = nodeToDelete->value;


    if(list->head == list->tail) //if node is the only node present
        list->head = list->tail = NULL;
    else
        list->head = list->head->next;

    free(nodeToDelete);
    puts("Remove head");
    return value;
}

int removeTail( LinkedList* list )
{
    if( isEmpty(list) )
        return INT_MIN;

    int value ;
    if(list->head == list->tail)
    {
        value = list->tail->value;
        free(list->tail);
        list->head = list->tail = NULL;
        return value;
    }

    Node* nodeToDelete = list->tail;
    value = nodeToDelete->value;

    Node* nodeBeforeTail = list->head;
    while( nodeBeforeTail->next != nodeToDelete )
        nodeBeforeTail = nodeBeforeTail->next;

    nodeBeforeTail->next = NULL;
    list->tail = nodeBeforeTail;

    free(nodeToDelete);
    puts("Remove tail");
    return value;
}

int removeElement( LinkedList* list , int value)
{
    if( list->head->value == value )
    {
        removeHead(list);
        return 0; //element found
    }

    if(list->tail->value == value)
    {
        removeTail(list);
        return 0;
    }

    Node* node = list->head;
    while( (node->next) != list->tail )
    {
        if( node->next->value == value)
        {
            Node* nodeToDelete = node->next;
            node->next = node->next->next;
            free(nodeToDelete);
            return 0;
        }
        node = node->next;
    }
    return 1;
}

int isEmpty( LinkedList* list )
{
    return !list->head && !list->tail;
}

int searchForElement( LinkedList* list , int value )
{
    if(isEmpty(list))
        return -1;

    Node* node = list->head;

    do
    {
        if(node->value == value) return 0;
    }while( (node = node->next) );

    return 1;
}

int linkedListSize( LinkedList* list )
{
    int counter = 0;
    Node* node = list->head;
    while( node )
    {
        counter++;
        node = node->next;
    }
    return counter;
}

void printHeadAndTail(LinkedList* list)
{
    if(isEmpty(list))
    {
        printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
        return;
    }
    printf("Head pointer: %d , Head's pointer to next : %d\n" , list->head, list->head->next );
    printf("Tail pointer: %d , tail's pointer to next : %d\n" , list->tail, list->tail->next );
}

void printListRec(Node* node)
{
    if( !node )
        return;
    printf("%d " , node->value);
    printListRec(node->next);
}

int printList(LinkedList* list)
{
    if( isEmpty(list) )
    {
        puts("List is empty");
        return 1;
    }

    puts("\nPrint Linked List: ");
    Node* node = list->head;
    while( node )
    {
        printf("%d " , node->value);
        node = node->next;
    }

    puts("\n*******************\n");

    return 0;
}

Answer 1

    LinkedList* list = malloc(sizeof(LinkedList));

始终确保分配函数malloc和好友成功。这些函数在无法分配内存时返回一个null指针。如果环境没有配置为在malloc失败时保护/崩溃，那么就会有一堆导致未定义行为的null指针取消引用。

    puts("Add head");

这些信息只会产生噪音。您应该使用预编译器指令在调试生成中切换函数调用跟踪，或者将跟踪移动到测试驱动程序。更好的是，使用调试器。

int removeHead( LinkedList* list )
{
    if(isEmpty(list))
        return INT_MIN;
    // ...
}

不要试图通过相同的返回变量返回错误代码和实际可表示的数据。库用户可能在数据集中使用INT_MIN，对removeXXXX()的调用可能会导致某些用户代码认为某些数据实际上已被删除。决定是否要将成功或失败通知被叫人，不要费心从列表中返回数据。如果被调用者真的想要数据，他们可以在删除之前自己复制数据。

保持功能简洁。当函数的长度超过几行时，请寻找机会将其重构到更高的抽象级别。例如，您的removeTail函数有一个大块，本质上是removeHead，另一个块实质上找到了前一个节点。

int isEmpty( LinkedList* list )
{
    return !list->head && !list->tail;
}

是否存在list->head或list->tail存在而另一个不存在的情况？如果被调用方传递一个list，即null，会发生什么情况？

        if(node->value == value) return 0;
    }while( (node = node->next) );

    if(isEmpty(list))
    if( !node )

与您的格式一致。

    if( isEmpty(list) )
    if( !node )

注意安全，并始终支撑你的单线身体范围。它们不会被维护人员(人和机器)误解。

    if( node->value == value) 
    {
        return 0;
    }
}
while( (node = node->next) );

需要考虑的问题:将控制结构与函数调用区分开来，以帮助实现可读性和代码理解。阅读代码将比编写代码花费更多的时间。例如：

    if (node->value == value) 
    {
        return 0;
    }
}
while (node = node->next);

int linkedListSize( LinkedList* list )
{
    int counter = 0;
    Node* node = list->head;
    while( node )
    {
        counter++;
        node = node->next;
    }
    return counter;
}

计算尺寸是一种线性运算。您是否考虑过只将当前大小存储在LinkedList结构中，并在对列表进行操作时更新值？这将使调用大小成为一个以int大小为代价的恒定时间操作。

释放列表的函数在哪里？printList()是前向声明的。没有执行？

Answer 2

匹配类型为

的printf转换

GCC警告我：

190060.c:220:35: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
         printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
                                  ~^                          ~~~~~~~~~~
190060.c:220:55: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘Node *’ {aka ‘struct node *’} [-Wformat=]
         printf("\nHead pointer : %d , tail pointer : %d\n" , list->head , list->tail);
                                                      ~^                   ~~~~~~~~~~

(还有更多)。我们希望*p作为指针：

void printHeadAndTail(LinkedList* list)
{
    if(isEmpty(list))
    {
        printf("\nHead pointer : %p , tail pointer : %p\n" , (void*)list->head , (void*)list->tail);
        return;
    }
    printf("Head pointer: %p , Head's pointer to next : %p\n" , (void*)list->head, (void*)list->head->next );
    printf("Tail pointer: %p , tail's pointer to next : %p\n" , (void*)list->tail, (void*)list->tail->next );
}

使用const进行非修改操作(

)。

这很简单：

void printListRec(const Node *node);
void printHeadAndTail(const LinkedList *list);
int printList(const LinkedList *list);
int linkedListSize(const LinkedList *list);
int searchForElement(const LinkedList *list, int value);
int isEmpty(const LinkedList *list);

实现clearList函数

有一种常见的情况是，它是缺失的；没有它，就很难检查内存泄漏。

void clearList(LinkedList *list)
{
    Node *n = list->head;
    while (n) {
        Node *n2 = n->next;
        free(n);
        n = n2;
    }
    list->head = list->tail = NULL;
}

考虑一个“虚拟头”实现

如果我们创建一个从未用于值的head元素，但只用于其next成员，则可以降低许多函数的复杂性。这是Null对象设计模式的一个例子。

例如：

// allocation error-checking omitted - please add some!

void addHead(LinkedList* list, int value)
{
    Node* newNode = malloc(sizeof *newNode);
    newNode->value = value;
    newNode->next = NULL;

    if (!list->head.next) {
        list->tail = newNode;
    }
    newNode->next = list->head.next;
    list->head.next = newNode;
    puts("Add head");
}

void addTail(LinkedList* list , int value)
{
    Node* newNode = malloc(sizeof *newNode);
    newNode->value = value;
    newNode->next = NULL;

    list->tail->next = newNode;
    list->tail = newNode;
    puts("Add tail");
}

int removeHead(LinkedList* list)
{
    Node* nodeToDelete = list->head.next;
    int value = INT_MIN;
    if (nodeToDelete) {
        value = nodeToDelete->value;
        list->head.next = nodeToDelete->next;
        free(nodeToDelete);
        if (!list->head.next) {
            list->tail = &list->head;
        }
    }
    puts("Remove head");
    return value;
}

int removeTail(LinkedList* list)
{
    if (!list->head.next)
        return INT_MIN;

    Node *n = &list->head;
    while (n->next->next) n = n->next;

    Node* nodeToDelete = n->next;
    int value = nodeToDelete->value;

    n->next = NULL;
    list->tail = n;

    free(nodeToDelete);
    puts("Remove tail");
    return value;
}

int removeElement(LinkedList* list , int value)
{
    Node *n = &list->head;
    while (n->next && n->next->value != value)
        n = n->next;

    if (!n->next)
        /* not found */
        return 0;

    if (list->tail == n->next)
        return removeTail(list), 1;

    Node *newNext = n->next->next;
    free(n->next);
    n->next = newNext;
    return 1;
}

int searchForElement(const  LinkedList* list , int value)
{
    const Node *n = &list->head;
    while ((n=n->next)) {
        if (n->value == value) return 0;
    }
    return 1;
}

我不确定这到底是更简单还是更清晰，但这是一种需要注意的技术，并且在需要时可以使用。在双链接列表中，它往往更有用。

还请考虑拥有tail指针是否值得保持其更新的成本。它可能用于附加到的长列表中，但是如果您可以将其放在前面，那么最好省略它。