CODEWITHSUNDEEP
cdata-structureslinked-list
Oka Prinarjaya
Oka Prinarjaya

Reputation: 101

Which better to store ANSI C linked list? By using *head OR by using other structure?

I was studying linked list (single & double) in C. From many basic tutorials i've read, the average of the tutorials have two way to store linked list. Such as:

  1. Using *head
struct ListItem *head;

struct ListItem *a = (struct ListItem *) malloc(sizeof(struct ListItem));
a->data = 10;
a->next = NULL;

struct ListItem *b = (struct ListItem *) malloc(sizeof(struct ListItem));
b->data = 25;
b->next = NULL;

// Link it!
head = a;
a->next = b;
  1. Using other structure (struct jsw_list) as code example below:
struct jsw_list {
    struct jsw_node *head;
    struct jsw_node *tail;
    size_t size;
};

struct jsw_list *new_list(int has_dummy_head, int has_dummy_tail)
{
    struct jsw_list *rv = (struct jsw_list *) malloc(sizeof(struct jsw_list));
    //.
    //.
    //.
}

struct jsw_list *list = new_list(1,1);
struct jsw_node *node;

node = insert_after(list, list->head, 10000);
node = insert_after(list, node, 5000);

Which better?

Please Enlightenment

Thank You

Upvotes: 0

Views: 82

Answers (2)

Sasha Nicolas
Sasha Nicolas

Reputation: 169

Short answer: there's no better way.

But... it might depend on what you aim to do. Let say you want work with single linked list, just to store with no fancy operations.

You will only need the list item, and keep the first as follow;

typedef struct listItem{
    void * content;
    struct * listItem next;
}ListItem;

ListItem first;

Or if you want a double linked list:

typedef struct listItem{
    void * content;
    struct * listItem previous;
    struct * listItem next;
}ListItem;

ListItem first;

On the other hand, if you want to keep track of size, and other stuff, let say quantity of certain types in the list, among others, it might be a good choice to have a new data structure in order to keep track of them.

typedef struct listItem{
    void * content;
    struct * listItem previous;
    struct * listItem next;
}ListItem;

typedef struct list{
    ListItem * first, * last;
    int quantity;
}List;

List myList;

You don't have to have a pointer for the list. But you can. In the second implementation, you gain performance on things you would have to go through the list in order to get such as the quantity. But now you have to keep updating the quantity every time you add or remove an item.

Upvotes: 1

sth
sth

Reputation: 229754

One version also keeps track of the tail pointer and the size of the list, so it has additional features. It's up to you to decide of those features are a helpful addition or useless bloat in your particular situation.

Which version is better depends on the specific use case.

Upvotes: 0

Related Questions