generic linked list

[sengupta_arka123]

How do I implement a generic linked list?

 

[Malcolm McLean]

How do I implement a generic linked list?

typedef struct node
{
struct node *prev;
struct node *next;
void *data;
} NODE;

typedef struct
{
struct node *first;
struct node *last;
} LINKEDLIST;

 

[Eric Sosman]

How do I implement a generic linked list?

What do you mean by "generic?"

 

[Michael Mair]

How do I implement a generic linked list?

Depends.
The usual way is to have a struct containing
the list infrastructure and a pointer to the data
and provide ways for the user to affect the data,
e.g. via function pointers.

With
struct GenSLList {
struct GenSLList *pNext;
void *pData;
};
you can perform some operations purely on the linked list,
like inserting new nodes
struct GenSLList *pNode1, *pNode2;
....
pNode1->pNext = pNode2;
whereas things like creating new nodes, deleting nodes, sorting
the list etc. need your input:
struct GenSLList*
CreateSllNode (int (*CreateDataFrom)(void**, void*),
void *pTemplateData);
which provides a new list node and, depending on the CreateDataFrom
and pTemplateData parameters, may do things to also provide
new data or set the pData member to pTemplateData or ...

Note that general programming / algorithm / data structure questions
may be better asked in comp.programming. As soon as you have written
some C code and have specific questions regarding that code, you can
ask here.


Cheers
Michael

 

[karthikbalaguru79]

How do I implement a generic linked list?

What do you mean by generic ?

Is your query related with .NET - Generic Class Linked List ? (
http://msdn2.microsoft.com/en-us/library/he2s3bh7.aspx)

Karthik Balaguru

 

[user923005]

How do I implement a generic linked list?

The question is a little vague.
Linked lists contain all sorts of variants.
There are ordered linked lists (skiplists).
There are circular linked lists.
There are doubly linked lists.

What do you want to accomplish with your list?

 

[Ravishankar S]

How do I implement a generic linked list?

Use the list.h set of interfaces from the linux kernerl sources

 

[pete]

How do I implement a generic linked list?

/* BEGIN Lf_sort_2.c */
/*
** Demonstration of use of generic list functions
** to sort a list of long double values.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUMBERS \
{15,14,13,7,20,9,8,12,11,6}

#define NMEMB(A) (sizeof (A) / sizeof *(A))

struct list_node {
struct list_node *next;
void *data;
};

typedef struct list_node list_type;

int Lf_comp(const list_type *a, const list_type *b);
int Lf_fprintf(const list_type *node, FILE *stream);
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size);
void list_free(list_type *node, void (*free_data)(void *));
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_node (list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
static list_type *split_list(list_type *head);

int main(void)
{
list_type *head;
list_type *tail;
long double numbers[] = NUMBERS;
long double *const after = numbers + NMEMB(numbers);
long double *ptr;

puts("/* BEGIN Lf_sort_2.c output */");
puts("\nOriginal order of list of long doubles:");
tail = head = NULL;
for (ptr = numbers; ptr != after; ++ptr) {
tail = list_append(&head, tail, ptr, sizeof *ptr);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
Lf_fprintf(head, stdout);
puts("\nList after mergesort:");
head = list_sort(head, Lf_comp);
Lf_fprintf(head, stdout);
list_free(head, free);
puts("\n/* END Lf_sort_2.c output */");
return 0;
}

int Lf_comp(const list_type *a, const list_type *b)
{
long double *const a_Lf_ptr = a -> data;
long double *const b_Lf_ptr = b -> data;

return *b_Lf_ptr > *a_Lf_ptr ? -1 : *b_Lf_ptr != *a_Lf_ptr;
}

int Lf_fprintf(const list_type *node, FILE *stream)
{
int rc = 0;

while (node != NULL) {
long double *const Lf_ptr = node -> data;

if (0 > (rc = fprintf(stream, "%Lf\n", *Lf_ptr))) {
break;
}
node = node -> next;
}
return rc;
}

list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size)
{
list_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(size);
if (node -> data != NULL) {
memcpy(node -> data, data, size);
if (*head != NULL) {
tail -> next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}

void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}

static list_type *sort_node(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
list_type *tail;

if (head -> next != NULL) {
tail = split_list(head);
tail = sort_node(tail, compar);
head = sort_node(head, compar);
head = merge_lists(head, tail, compar);
}
return head;
}

static list_type *split_list(list_type *head)
{
list_type *tail;

tail = head -> next;
while ((tail = tail -> next) != NULL
&& (tail = tail -> next) != NULL)
{
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}

static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;
list = sorted = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = tail != NULL ? tail : head;
return list;
}

/* END Lf_sort_2.c */

 

[pete]

How do I implement a generic linked list?

/* BEGIN string_sort_2.c */
/*
** Demonstration of use of generic list functions
** to sort a list of strings.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct list_node {
struct list_node *next;
void *data;
};

typedef struct list_node list_type;

#define NUMBERS \
{"one","two","three","four","five",\
"six","seven","eight","nine","ten"}

#define NMEMB(A) (sizeof (A) / sizeof *(A))

int lencomp(const list_type *a, const list_type *b);
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size);
void list_free(list_type *node, void (*free_data)(void *));
int list_fputs(const list_type *node, FILE *stream);
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_node (list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *split_list(list_type *head);
static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));

int main(void)
{
list_type *head;
list_type *tail;
char *numbers[] = NUMBERS;
char **const after = numbers + NMEMB(numbers);
char **ptr;

puts("/* BEGIN string_sort_2.c output */");
puts("\nOriginal order of list of pointers to strings:");
tail = head = NULL;
for (ptr = numbers; ptr != after; ++ptr) {
tail = list_append(&head, tail, *ptr, strlen(*ptr) + 1);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
list_fputs(head, stdout);
puts("\nList after stable mergesort by string length:");
head = list_sort(head, lencomp);
list_fputs(head, stdout);
list_free(head, free);
puts("\n/* END string_sort_2.c output */");
return 0;
}

int lencomp(const list_type *a, const list_type *b)
{
const size_t a_len = strlen(a -> data);
const size_t b_len = strlen(b -> data);

return b_len > a_len ? -1 : b_len != a_len;
}

list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size)
{
list_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(size);
if (node -> data != NULL) {
memcpy(node -> data, data, size);
if (*head != NULL) {
tail -> next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}

void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

int list_fputs(const list_type *node, FILE *stream)
{
int rc = 0;

while (node != NULL
&& (rc = fputs(node -> data, stream)) != EOF
&& (rc = putc('\n', stream)) != EOF)
{
node = node -> next;
}
return rc;
}

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}

static list_type *sort_node(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
list_type *tail;

if (head -> next != NULL) {
tail = split_list(head);
tail = sort_node(tail, compar);
head = sort_node(head, compar);
head = merge_lists(head, tail, compar);
}
return head;
}

static list_type *split_list(list_type *head)
{
list_type *tail;

tail = head -> next;
while ((tail = tail -> next) != NULL
&& (tail = tail -> next) != NULL)
{
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}

static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;
list = sorted = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = tail != NULL ? tail : head;
return list;
}

/* END string_sort_2.c */