是否可以拥有不同数据类型的链表？

This is just another interview question.

这只是另一个采访问题。

Can we have a linked list of different data types, i.e. each element in a linked list can have different structure or union elements? If it's possible can you please explain with an example?

我们可以有一个不同数据类型的链表,即链表中的每个元素可以有不同的结构或联合元素吗?如果有可能请你举个例子解释一下?

10 个解决方案

#1

Use union to create the datatype

使用union创建数据类型

union u_tag{
    char ch;
    int d;
    double dl;
};

struct node {
    char type;
    union u_tag u;
    struct node *next;
};

Use struct node to create linked list. type decides what is the datatype of the data.

使用struct node创建链表。 type决定数据的数据类型。

Harsha T, Bangalore

Harsha T,班加罗尔

#2

Well in a linked list you don't HAVE to link like for like structs together. As long as they have the appropriate forward and/or backwards pointers you are fine. For example:

好吧,在一个链表中,你不需要像喜欢结构一样链接。只要他们有适当的前进和/或后退指针你就可以了。例如:

struct BaseLink
{
   BaseLink* pNext;
   BaseLink* pPrev;
   int       typeId;
};

struct StringLink
{
    BaseLink baseLink;
    char* pString;
};

struct IntLink
{
    BaseLink baseLink;
    int   nInt;
};

This way you'd have a linked list that goes from BaseLink to BaseLink. The extra data is not a problem. You want to see it as a StringLink? Then cast the BaseLink to a StringLink.

这样你就有了一个从BaseLink到BaseLink的链表。额外的数据不是问题。你想看到它作为StringLink?然后将BaseLink转换为StringLink。

Just remember that you need some form of typeid in there so you know what to cast it to when you arrive at it.

请记住,你需要某种形式的typeid,所以当你到达时,你知道要把它投射到什么。

#3

You can use a union type:

您可以使用联合类型:

enum type_tag {INT_TYPE, DOUBLE_TYPE, STRING_TYPE, R1_TYPE, R2_TYPE, ...};
struct node {
  union {
    int ival;
    double dval;
    char *sval;
    struct recordType1 r1val;
    struct recordType2 r2val;
    ...
  } data;
  enum type_tag dataType;
  struct node *prev;
  struct node *next;
};

Another method I've explored is to use a void* for the data and attach pointers to functions that handle the type-aware stuff:

我探索的另一种方法是对数据使用void *并将指针附加到处理类型感知内容的函数:

/**
 * Define a key type for indexing and searching
 */
typedef ... key_t;                 

/**
 * Define the list node type
 */
struct node {
  void *data;
  struct node *prev;
  struct node *next;
  void *(*cpy)(void *);            // make a deep copy of the data
  void (*del)(void *);             // delete the data
  char *(*dpy)(void *);            // format the data for display as a string
  int (*match)(void *, key_t);     // match against a key value
};

/**
 * Define functions for handling a specific data type
 */
void *copyARecordType(void *data)
{
  struct aRecordType v = *(struct aRecordType *) data;
  struct aRecordType *new = malloc(sizeof *new);
  if (new)
  {
    // copy elements of v to new
  }
  return new;
}

void deleteARecordType(void *data) {...}
char *displayARecordType(void *data) {...}
int matchARecordType(void *data, key_t key) {...}

/**
 * Define functions for handling a different type
 */
void *copyADifferentRecordType(void *data) {...}
void deleteADifferentRecordType(void *data) {...}
char *displayADifferentRecordType(void *data) {...}
int matchADifferentRecordType(void *data, key_t key) {...}

/**
 * Function for creating new list nodes
 */
struct node *createNode(void *data, void *(*cpy)(void *), void (*del)(void *), 
    char *(*dpy)(void *), int (*match)(void *, key_t))
{
  struct node *new = malloc(sizeof *new);
  if (new)
  {
    new->cpy = cpy;
    new->del = del;
    new->dpy = dpy;
    new->match = match;
    new->data = new->cpy(data);
    new->prev = new->next = NULL;
  }
  return new;
}

/**
 * Function for deleting list nodes
 */
void deleteNode(struct node *p)
{
  if (p)
    p->del(p->data);
  free(p);
}

/**
 * Add new node to the list; for this example, we just add to the end
 * as in a FIFO queue.  
 */
void addNode(struct node *head, void *data, void *(*cpy)(void*), 
  void (*del)(void *), char *(*dpy)(void *), int (*match)(void*, key_t))
{
  struct node *new = createNode(data, cpy, del, dpy, match);
  if (!head->next)
    head->next = new;
  else
  {
    struct node *cur = head->next;
    while (cur->next != NULL)
      cur = cur->next;
    cur->next = new;
    new->prev = cur;
  }
}

/**
 * Examples of how all of this would be used.
 */
int main(void)
{
  struct aRecordType r1 = {...};
  struct aDifferentRecordType r2 = {...};

  struct node list, *p;
  addNode(&list, &r1, copyARecordType, deleteARecordType, displayARecordType,
    matchARecordType);
  addNode(&list, &r2, copyADifferentRecordType, deleteADifferentRecordType,
    displayADifferentRecordType, matchADifferentRecordType);
  p = list.next;
  while (p)
  {
    printf("Data at node %p: %s\n", (void*) p, p->dpy(p->data));
    p = p->next;
  }
  return 0;
}

Obviously, I've left out some error checking and handling code from this example, and I don't doubt there are a host of problems with it, but it should be illustrative.

显然,我从这个例子中省略了一些错误检查和处理代码,我不怀疑它有很多问题,但它应该是说明性的。

#4

You can have each node in a linked list have a void* that points to your data. It's up to you how you determine what type of data that pointer is pointing to.

您可以让链接列表中的每个节点都具有指向您的数据的void *。由您决定指针指向哪种类型的数据取决于您。

#5

If you don't want to have to specify the type of every node in the list via the union solution you can always just store the data in a char* and take type-specific function pointers as parameters to type-sensitive operations such as printing or sorting the list. This way you don't have to worry about what node is what type and can just cast the data however you like.

如果您不想通过union解决方案指定列表中每个节点的类型,您始终只需将数据存储在char *中,并将类型特定的函数指针作为参数进行类型敏感操作(如打印)或排序列表。这样您就不必担心哪个节点是什么类型,只需按照您喜欢的方式转换数据。

/* data types */

typedef struct list_node list_node;
struct list_node {
    char *data;
    list_node *next;
    list_node *prev;
};

typedef struct list list;
struct list {
    list_node *head;
    list_node *tail;
    size_t size;
};

/* type sensitive functions */

int list_sort(list *l, int (*compar)(const void*, const void*));
int list_print(list *l, void (*print)(char *data));

#6

Yes, I do this by defining the list's element's value as a void pointer void*. In order to know the type stored in each element of the list I also have a .type field in there, so I know how to dereference what the pointer is pointing to for each element.

是的,我通过将列表的元素值定义为void指针void *来实现此目的。为了知道存储在列表的每个元素中的类型,我也有一个.type字段,所以我知道如何取消引用指针指向每个元素的内容。

struct node {
    struct node* next;
    int type;
    void* value;
};

Here's a full example of this:

这是一个完整的例子:

//                                                                                                                                                                                          
// An exercise to play with a struct that stores anything using a void* field.                                                                                                              
//                                                                                                                                                                                          

#include <stdio.h>

#define TRUE 1

int TYPE_INT = 0;
int TYPE_STRING = 1;
int TYPE_BOOLEAN = 2;
int TYPE_PERSON = 3;

struct node {
  struct node* next;
  int type;
  void* value;
};

struct person {
  char* name;
  int age;
};

int main(int args, char **argv) {

  struct person aPerson;
  aPerson.name = "Angel";
  aPerson.age = 35;

  // Define a linked list of objects.                                                                                                                                                       
  // We use that .type field to know what we're dealing                                                                                                                                     
  // with on every iteration. On .value we store our values.                                                                                                                                
  struct node nodes[] = {
    { .next = &nodes[1], .type = TYPE_INT    , .value=1                   },
    { .next = &nodes[2], .type = TYPE_STRING , .value="anyfing, anyfing!" },
    { .next = &nodes[3], .type = TYPE_PERSON , .value=&aPerson            },
    { .next = NULL     , .type = TYPE_BOOLEAN, .value=TRUE                }
  };

  // We iterate through the list                                                                                                                                                            
  for ( struct node *currentNode = &nodes[0]; currentNode;  currentNode = currentNode->next) {
    int currentType = (*currentNode).type;
    if (currentType == TYPE_INT) {
      printf("%s: %d\n", "- INTEGER", (*currentNode).value); // just playing with syntax, same as currentNode->value                                                                        
    } else if (currentType == TYPE_STRING) {
      printf("%s: %s\n", "- STRING", currentNode->value);
    } else if (currentType == TYPE_BOOLEAN) {
      printf("%s: %d\n", "- BOOLEAN (true:1, false:0)", currentNode->value);
    } else if (currentType == TYPE_PERSON) {
        // since we're using void*, we end up with a pointer to struct person, which we *dereference                                                                                        
        // into a struct in the stack.                                                                                                                                                      
        struct person currentPerson = *(struct person*) currentNode->value;
        printf("%s: %s (%d)\n","- TYPE_PERSON", currentPerson.name, currentPerson.age);
      }
  }

    return 0;
}

Expected output:

- INTEGER: 1
- STRING: anyfing, anyfing!
- TYPE_PERSON: Angel (35)
- BOOLEAN (true:1, false:0): 1

#7

As said, you can have a node this questionwith a void*. I suggest using something to know about your type :

如上所述,你可以让这个问题的节点带有一个void *。我建议使用一些东西来了解你的类型:

typedef struct
{
    /* linked list stuff here */    

    char m_type;
    void* m_data;
} 
Node;

See this question.

看到这个问题。

#8

Actually, you don't have to put the pointer first in the structure, you can put it anywhere and then find the beginning fo the struct with a containerof() macro. The linux kernel does this with its linked lists.

实际上,您不必将指针放在结构中,您可以将它放在任何位置,然后使用containerof()宏找到结构的开头。 linux内核使用其链表进行此操作。

http://isis.poly.edu/kulesh/stuff/src/klist/

#9

I use these macros I wrote to make general linked lists. You just create your own struct and use the macro list_link somewhere as a member of the struct. Give that macro one argument naming the struct (without the struct keyword). This implements a doubly linked list without a dummy node (e.g. last node links back around to first node). The anchor is a pointer to the first node which starts out initialized by list_init(anchor) by giving it the lvalue (a dereferenced pointer to it is an lvalue). Then you can use the other macros in the header. Read the source for comments about each available macro functions. This is implemented 100% in macros.

我使用我写的这些宏来制作一般的链表。您只需创建自己的结构并在某处使用宏list_link作为结构的成员。给该宏指定一个命名结构的参数(不带struct关键字)。这实现了没有虚节点的双链表(例如,最后节点链接回第一节点)。锚是指向第一个节点的指针,该节点由list_init(锚)初始化,通过给它左值(对它的解引用指针是左值)。然后,您可以使用标头中的其他宏。阅读有关每个可用宏功能的注释的来源。这是在宏中实现的100%。

http://phil.ipal.org/pre-release/list-0.0.5.tar.bz2

#10

Just an FYI, In C# you can use Object as your data member.

只是一个FYI,在C#中你可以使用Object作为你的数据成员。

class Node
{
     Node next;
     Object Data;
}

User can then use something like this to find out which Object the Node stores:

然后,用户可以使用类似的东西来找出节点存储的对象:

if (obj.GetType() == this.GetType()) //
{

}