如何在C中实现链表？

I am creating a linked list as in the previous question I asked. I have found that the best way to develop the linked list is to have the head and tail in another structure. My products struct will be nested inside this structure. And I should be passing the list to the function for adding and deleting. I find this concept confusing.

我正在创建一个链接列表,就像我之前提出的问题一样。我发现开发链表的最好方法是将头部和尾部放在另一个结构中。我的products struct将嵌套在这个结构中。我应该将列表传递给添加和删除功能。我发现这个概念令人困惑。

I have implemented the initialize, add, and clean_up. However, I am not sure that I have done that correctly.

我已经实现了initialize,add和clean_up。但是,我不确定我是否正确地做到了这一点。

When I add a product to the list I declare some memory using calloc. But I am thinking shouldn't I be declaring the memory for the product instead. I am really confused about this adding.

当我将产品添加到列表中时,我使用calloc声明了一些内存。但我想我不应该为产品声明内存。我对此添加感到困惑。

Many thanks for any suggestions,

非常感谢任何建议,

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

#define PRODUCT_NAME_LEN 128

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct product_data_t *next;
}product_data_t;

typedef struct list 
{
    product_data_t *head;
    product_data_t *tail;
}list_t;

void add(list_t *list, int code, char name[], int cost); 
void initialize(list_t *list);
void clean_up(list_t *list);

int main(void)
{
    list_t *list = NULL;

    initialize(list);
    add(list, 10, "Dell Inspiron", 1500);
    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    // Allocate memory for the new product
    list = calloc(1, sizeof(list_t));
    if(!list)
    {
        fprintf(stderr, "Cannot allocated memory");
        exit(1);
    }

    if(list)
    {
        // First item to add to the list
        list->head->product_code = code;
        list->head->product_cost = cost;
        strncpy(list->head->product_name, name, sizeof(list->head->product_name));
        // Terminate the string
        list->head->product_name[127] = '/0';
    } 
}

// Initialize linked list
void initialize(list_t *list)
{
    // Set list node to null
    list = NULL;
    list = NULL;
}

// Release all resources
void clean_up(list_t *list)
{    
    list_t *temp = NULL;

    while(list)
    {
        temp = list->head;
        list->head = list->head->next;
        free(temp);    
    }
    list = NULL;
    list = NULL;
    temp = NULL;
}

============================== Edited ============================

==============================编辑=================== =========

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

#define PRODUCT_NAME_LEN 64

// typedef struct product_data product_data_t;
typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
}product_data_t;

typedef struct list
{
    struct list *head;
    struct list *tail;
    struct list *next;
    struct list *current_node;
    product_data_t *data;

}list_t;

void add(list_t *list, int code, char name[], int cost); 

int main(void)
{
    list_t *list = NULL;
    list = initialize(list);
    add(list, 1001, "Dell Inspiron 2.66", 1299);

    add(list, 1002, "Macbook Pro 2.66", 1499);

    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    /* Allocate memory for the new product */
    product_data_t *product = (product_data_t*) calloc(1, sizeof(*product));
    if(!product)
    {
        fprintf(stderr, "Cannot allocate memory.");
        exit(1);
    }

    /* This is the first item in the list */
    product->product_code = code;
    product->product_cost = cost;
    strncpy(product->product_name, name, sizeof(product->product_name));
    product->product_name[PRODUCT_NAME_LEN - 1] = '\0';

    if(!list->head)
    {
        /* Assign the address of the product. */
        list = (list_t*) product;   
        /* Set the head and tail to this product */
        list->head = (list_t*) product;
        list->tail = (list_t*) product;
    }
    else
    {
        /* Append to the tail of the list. */
        list->tail->next = (list_t*) product;
        list->tail = (list_t*) product;
    }

    /* Assign the address of the product to the data on the list. */
    list->data = (list_t*) product;
}

14 个解决方案

#1

In your case the head and tail could simply point to the beginning and end of a linked-list. With a singly linked-list, only the head is really needed. At it's most basic, a linked-list can be made by using just a struct like:

在您的情况下,头部和尾部可以简单地指向链表的开头和结尾。使用单链表,只需要头部。在最基本的情况下,可以通过仅使用如下结构来创建链接列表:

typedef struct listnode
{
   //some data
   struct listnode *next;
}listnodeT;

listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;

and as long as list is always pointing to the beginning of the list and the last item has next set to NULL, you're fine and can use current_node to traverse the list. But sometimes to make traversing the list easier and to store any other data about the list, a head and tail token are used, and wrapped into their own structure, like you have done. So then your add and initialize functions would be something like (minus error detection)

只要list总是指向列表的开头而最后一个项目下一次设置为NULL,你就可以了,并且可以使用current_node来遍历列表。但有时为了更容易遍历列表并存储有关列表的任何其他数据,使用头尾令牌,并将其包装到自己的结构中,就像您所做的那样。那么你的添加和初始化函数就像(减去错误检测)

    // Initialize linked list
void initialize(list_t *list)
{
    list->head = NULL;
    list->tail = NULL;
}

void add(list_t *list, int code, char name[], int cost)
{
    // set up the new node
    product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t));
    node->code = code;
    node->cost = cost;
    strncpy(node->product_name, name, sizeof(node->product_name));
    node->next = NULL;

    if(list->head == NULL){ // if this is the first node, gotta point head to it
        list->head = node;
        list->tail = node;  // for the first node, head and tail point to the same node
    }else{
        tail->next = node;  // append the node
        tail = node;        // point the tail at the end
    }
}

In this case, since it's a singly linked-list, the tail is only really useful for appending items to the list. To insert an item, you'll have to traverse the list starting at the head. Where the tail really comes in handy is with a doubly-linked list, it allows you to traverse the list starting at either end. You can traverse this list like

在这种情况下,由于它是一个单独的链表,尾部只对将项添加到列表中非常有用。要插入项目,您必须从头部开始遍历列表。尾部真正派上用场的地方是双向链表,它允许你从两端开始遍历列表。你可以遍历这个列表

// return a pointer to element with product code
product_data_t*  seek(list_t *list, int code){
   product_data_t* iter = list->head;
   while(iter != NULL)
       if(iter->code == code)
           return iter;
       iter = iter->next;
   }
   return NULL; // element with code doesn't exist
}

Often times, the head and tail are fully constructed nodes themselves used as a sentinel to denote the beginning and end of a list. They don't store data themselves (well rather, their data represent a sentinel token), they are just place holders for the front and back. This can make it easier to code some algorithms dealing with linked lists at the expense of having to have two extra elements. Overall, linked lists are flexible data structures with several ways to implement them.

通常,头部和尾部是完全构造的节点,它们本身用作标记来表示列表的开头和结尾。它们本身并不存储数据(更确切地说,它们的数据代表了一个标记符号),它们只是正面和背面的占位符。这样可以更容易地编写一些处理链表的算法,但代价是必须有两个额外的元素。总的来说,链表是灵活的数据结构,有几种实现方式。

oh yeah, and nik is right, playing with linked-lists are a great way to get good with pointers and indirection. And they are also a great way to practice recursion too! After you have gotten good with linked-list, try building a tree next and use recursion to walk the tree.

哦是的,而且nik是对的,玩链接列表是一个很好的方法来获得指针和间接的好处。而且它们也是练习递归的好方法!使用链接列表后,请尝试构建一个树,然后使用递归来遍历树。

#2

Arguably you want your list data structure to be external to the data that it stores.

可以说,您希望列表数据结构在其存储的数据外部。

Say you have:

说你有:

struct Whatever
{
   int x_;
}

Then your list structure would look like this:

那么你的列表结构将如下所示:

struct Whatever_Node
{
   Whatever_Node* next_
   Whatever* data_
}

Ryan Oberoi commented similarly, but w/o example.

Ryan Oberoi同样评论,但没有例子。

#3

If you are looking to better understand the basics of linked lists, take a look at the following document:

如果您希望更好地了解链接列表的基础知识,请查看以下文档:

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

#4

If you are learning C pointer theory this is a good exercise. Otherwise, it feels like too much indirection for code that is not generic (as in a library).

如果你正在学习C指针理论,这是一个很好的练习。否则,对于非通用的代码(如在库中),感觉就像是太多间接。

Instead of allocating a static 128 byte character string, you might want to do some more pointer practice and use an allocated exact length string that you clean up at exit.

您可能希望执行更多指针练习,并使用在退出时清理的已分配的精确长度字符串,而不是分配静态128字节字符串。

Academically, kungfucraigs' structure looks more generic then the one you have defined.

在学术上,kungfucraigs的结构看起来比你定义的更通用。

#5

You're calloc'ing space for your list_t struct, just pointers to list head and tail, which isn't what you want to do.

你是list_t结构的calloc'ing空间,只是指向列表头部和尾部的指针,这不是你想要做的。

When you add to a linked list, allocate space for an actual node in the list, which is your product_data_t struct.

添加到链接列表时,为列表中的实际节点分配空间,这是您的product_data_t结构。

#6

You're allocating the wrong chunk of memory. Instead of allocating memory for each list element, you're allocating for the list head and tail.

你正在分配错误的内存块。您不是为每个列表元素分配内存,而是为列表头部和尾部分配。

For simplicity, get rid of the separate structure for the head and tail. Make them global variables (the same scope they're in now) and change them to be listhead and listtail. This will make the code much more readable (you won't be needlessly going through a separate structure) and you won't make the mistake of allocating for the wrong struct.

为简单起见,摆脱头部和尾部的独立结构。使它们成为全局变量(与它们现在相同的范围)并将它们更改为listhead和listtail。这将使代码更具可读性(您不会不必要地通过单独的结构)并且您不会错误地分配错误的结构。

You don't need a tail pointer unless you're going to make a doubly linked list. Its not a major element to add once you create a linked list, but not necessary either.

你不需要尾指针,除非你打算制作一个双向链表。创建链表后,它不是添加的主要元素,但也不是必需的。

#7

I am not writing the code here but you need to do the following:

我不是在这里编写代码,但您需要执行以下操作:

• Create and object of list, this will remain global for the length of program.

创建列表的对象,这将在程序的长度上保持全局。

• Malloc the size of product _ data _ t.

malloc产品_ data _ t的大小。

• For first element (head is NULL), point head to the malloced' address.

对于第一个元素(head为NULL),指向malloced'地址。

• To add next element, move to the end of list and then add the pointer of malloced address to next of last element. (The next of the last element will always be NULL, so thats how you traverse to end.)

要添加下一个元素,请移至列表末尾,然后将malloced地址的指针添加到最后一个元素。 (最后一个元素的下一个元素将始终为NULL,因此您将如何遍历结束。)

• Forget tail for a while.

忘了尾巴一会儿。

#8

In memory your items are linked by pointers in the list structure

在内存中,您的项目通过列表结构中的指针链接

item1 -> item2

item1 - > item2

Why not make the list structure part of your item?

为什么不将列表结构作为项目的一部分?

Then you allocate a product item, and the list structure is within it.

然后分配一个产品项,列表结构就在其中。

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct list_t list; // contains the pointers to other product data in the list
}product_data_t;

#9

I think u first need to Imagin back-end. Code are nothing to important. Go here and visualize back-end basic c code of all insertion. 1) Insertion at beginning Visit and scroll to get every instruction execution on back- end And u need front and imagin Go here Back end imagin

我想你首先需要Imagin后端。代码没什么重要的。转到此处,可视化所有插入的后端基本c代码。 1)在开始时插入访问并滚动以获得后端的每个指令执行并且你需要前面和想象去这里返回结束imagin

And All other possible insertion here.

所有其他可能插入此处。

And important thing u can use this way.

重要的是你可以用这种方式。

struct Node{
int data;//data field
struct Node*next;//pointer field
};

struct Node*head,*tail; // try this way

struct Node * head,* tail; //试试这个

or short cut

或捷径

struct Node{
int data;//data field
struct Node*next;//pointer field
}*head,*tail; //global root pointer

And

<< Click >> To visualize other linked list problem.

<< Click >>可视化其他链表问题。

Thanks.

#10

A demo for Singly Linked List. If you prefer, try to check Circular Linked List and Doubly Linked List.

单链表的演示。如果您愿意,请尝试检查循环链接列表和双向链接列表。

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


typedef struct node {
    int val;
    struct node * next;
} node_t;


// Iterating over a list
void
print_list(node_t *head)
{
    node_t *current = head;

    while(current != NULL)
    {
        printf("%d\n", current->val);
        current = current->next;
    }
}


// Adding an item to the end of the list
void
push_end(node_t *head, int val)
{
    node_t *current = head;
    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

// Adding an item to the head of the list
void
push_head(node_t **head, int val)
{
    node_t *new_node = NULL;

    new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = *head;

    *head = new_node;
}

// Removing the head item of the list
int
pop_head(node_t **head)
{
    int retval = -1;
    node_t *next_node = NULL;

    if (*head == NULL) {
        return -1;
    }

    next_node = (*head)->next;
    retval = (*head)->val;
    free(*head);
    *head = next_node;

    return retval;
}

// Removing the last item of the list
int
pop_last(node_t *head)
{
    int retval = 0;
    node_t *current = NULL;

    if (head->next == NULL) {
        retval = head->val;
        free(head);
        return retval;
    }

    /* get to the second to last node in the list */
    current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    /* now current points to the second to last item of the list.
       so let's remove current->next */
    retval = current->next->val;
    free(current->next);
    current->next = NULL;

    return retval;
}

// Removing a specific item
int
remove_by_index(node_t **head, int n)
{
    int i = 0;
    int retval = -1;
    node_t *current = *head;
    node_t *temp_node = NULL;

    if (n == 0) {
        return pop_head(head);
    }

    for (i = 0; i < n - 1; i++) {
        if (current->next == NULL) {
            return -1;
        }
        current = current->next;
    }

    temp_node = current->next;
    retval = temp_node->val;
    current->next = temp_node->next;
    free(temp_node);

    return retval;
}


int
main(int argc, const char *argv[])
{
    int i;
    node_t * testnode;

    for (i = 0; i < argc; i++)
    {
        push_head(&testnode, atoi(argv[i]));
    }

    print_list(testnode);

    return 0;
}

// http://www.learn-c.org/en/Linked_lists
// https://www.geeksforgeeks.org/data-structures/linked-list/

#11

The linked list implementation inspired by the implementation used in the Linux kernel:

受Linux内核中使用的实现启发的链表实现:

// for 'offsetof', see: https://*.com/q/6433339/5447906.
#include <stddef.h>

// See: https://*.com/q/10269685/5447906.
#define CONTAINER_OF(ptr, type, member) \
    ( (type *) ((char *)(ptr) - offsetof(type, member)) )

// The macro can't be used for list head.
#define LIST_DATA(ptr, type, member) \
    CONTAINER_OF(ptr, type, member);

// The struct is used for both: list head and list nodes.
typedef struct list_node
{
    struct list_node *prev, *next;
}
list_node;

// List heads must be initialized by this function.
// Using the function for list nodes is not required.
static inline void list_head_init(list_node *node)
{
    node->prev = node->next = node;
}

// The helper function, mustn't be used directly.
static inline void list_add_helper(list_node *prev, list_node *next, list_node *nnew)
{
    next->prev = nnew;
    nnew->next = next;
    nnew->prev = prev;
    prev->next = nnew;
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_after(list_node *node, list_node *nnew)
{
    list_add_helper(node, node->next, nnew);
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_before(list_node *node, list_node *nnew)
{
    list_add_helper(node->prev, node, nnew);
}

// 'node' must be part of a list.
static inline list_node *list_del(list_node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    return node->prev;
}

Example of usage:

用法示例:

#include <stdio.h>

// The struct must contain 'list_node' to be able to be inserted to a list
typedef struct
{
    int       data;
    list_node node;
}
my_struct;

// Convert 'list_node *' to 'my_struct*' that contains this 'list_node'
static inline my_struct* get_my_struct(list_node *node_ptr)
{
    return LIST_DATA(node_ptr, my_struct, node);
}

void print_my_list(list_node *head)
{
    printf("list: {");
    for (list_node *cur = head->next; cur != head; cur = cur->next)
    {
        my_struct *my = get_my_struct(cur);
        printf(" %d", my->data);
    }
    printf(" }\n");
}

// Print 'cmd' and run it. Note: newline is not printed.
#define TRACE(cmd) \
    (printf("%s -> ", #cmd), (cmd))

int main()
{
    // The head of the list and the list itself. It doesn't contain any data.
    list_node head;
    list_head_init(&head);

    // The list's nodes, contain 'int' data in 'data' member of 'my_struct'
    my_struct el1 = {1};
    my_struct el2 = {2};
    my_struct el3 = {3};

    print_my_list(&head); // print initial state of the list (that is an empty list)

    // Run commands and print their result.
    TRACE( list_add_after (&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_add_after (&head    , &el2.node) ); print_my_list(&head);
    TRACE( list_add_before(&el1.node, &el3.node) ); print_my_list(&head);
    TRACE( list_del       (head.prev)            ); print_my_list(&head);
    TRACE( list_add_before(&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_del       (&el3.node)            ); print_my_list(&head);

    return 0;
}

The result of execution of the code above:

执行上面代码的结果:

list: { }
list_add_after (&head , &el1.node) -> list: { 1 }
list_add_after (&head , &el2.node) -> list: { 2 1 }
list_add_before(&el1.node, &el3.node) -> list: { 2 3 1 }
list_del (head.prev) -> list: { 2 3 }
list_add_before(&head , &el1.node) -> list: { 2 3 1 }
list_del (&el3.node) -> list: { 2 1 }

http://coliru.stacked-crooked.com/a/6e852a996fb42dc2

Of course in real life you will most probably use malloc for list elements.

当然,在现实生活中,您最有可能将malloc用于列表元素。

#12

In C language, we need to define a Node to store an integer data and a pointer to the next value.

在C语言中,我们需要定义一个Node来存储一个整数数据和一个指向下一个值的指针。

struct Node{
    int data;
    struct Node *next;
};

To add a new node, we have a function add which has data as an int parameter. At first we create a new Node n. If the program does not create n then we print an error message and return with value -1. If we create the n then we set the data of n to have the data of the parameter and the next will contain the root as it has the top of the stack. After that, we set the root to reference the new node n.

要添加新节点,我们有一个函数add,它将数据作为int参数。首先,我们创建一个新的Node n。如果程序没有创建n,那么我们打印一条错误消息并返回值-1。如果我们创建n,那么我们将n的数据设置为具有参数的数据,而下一个将包含根,因为它具有堆栈的顶部。之后,我们将根设置为引用新节点n。

#13

#include <stdio.h>
struct node
 {
  int data;
  struct node* next;
 };

int main()
{

//create pointer node for every new element

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

//initialize every new pointer with same structure memory

head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

head->data = 18;
head->next = second;

second->data = 20;
second->next = third;


third->data = 31;
third->next = NULL;

//print the linked list just increment by address 

  for (int i = 0; i < 3; ++i)
    {
      printf("%d\n",head->data++);
      return 0;
    }
 }

This is a simple way to understand how does pointer work with the pointer. Here you need to just create pointer increment with new node so we can make it as an automatic.

这是一种了解指针如何与指针一起工作的简单方法。在这里,您需要使用新节点创建指针增量,以便我们可以将其设置为自动节点。

#14

Go STL route. Declaring linked lists should be agnostic of the data. If you really have to write it yourself, take a look at how it is implemented in STL or Boost.

去STL路线。声明链接列表应该与数据无关。如果您真的必须自己编写,请查看它在STL或Boost中的实现方式。

You shouldn't even keep the *next pointer with your data structure. This allows you to use your product data structure in a various number of data structures - trees, arrays and queues.

您甚至不应该将* next指针与数据结构保持一致。这允许您在各种数据结构中使用您的产品数据结构 - 树,数组和队列。

Hope this info helps in your design decision.

希望此信息有助于您的设计决策。

Edit:

Since the post is tagged C, you have equivalent implementations using void* pointers that follow the basic design principle. For an example, check out:

由于帖子被标记为C,因此您使用遵循基本设计原则的void *指针进行等效实现。例如,请查看:

Documentation | list.c | list.h

文档| list.c | list.h