0

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

Oka Prinarjaya
  • 91
  • 7

2 Answers2

1

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.

Sasha Nicolas
  • 159
  • 1
  • 9
  • Nicolas - Hi, thank you very much your answer. Please correct me, that's not special, i think we can keep track the size of the list without using other struct. Just increment or decrement an integer variable outside the struct. Any other special thing / benefit if i store linked list using other struct? – Oka Prinarjaya May 28 '15 at 16:28
  • Yes, you can keep a variable outside for that. I can't think of other benefit than keep things organized and more clear. – Sasha Nicolas May 29 '15 at 01:05
0

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.

sth
  • 222,467
  • 53
  • 283
  • 367