Page 1 of 1
linkedlist
Posted: Wed Jan 12, 2005 1:39 pm
by Master_thunder
Hello.
I want to know if somebody know a site which give all functions of linkedlist in C. For information, in my OS, I don't have the memory allocation and I must do whithout. Please help me.
Re:linkedlist
Posted: Wed Jan 12, 2005 5:00 pm
by IRBMe
I'm not sure I understand your question, but basically a linked list is simply a list such that each entry in the list tells you where to find the next entry.
You could make a limked list like implementation using an array, where each entry in the array contains a value and the index of the next entry. This could be useful for sorting, for example, since all you need to move around are the indices instead of the values which may be large structs.
Usually it's done with pointers where each entry in the list contains it's value, and a pointer to the next (or/and previous) entry. This is useful because you can allocate objects (structs or whatever - not objects as in the OOP sense) and are then given a pointer to them, which you can shove in a linked list, giving you a dynamic data structure.
If you don't have memory allocation working, then you can still use linked list data structures. Infact, linked lists are often used in the memory manager themselves.
Perhaps you may want to elaborate slightly on your question and make it a little more precise so that people can give you better more specific answers.
Re:linkedlist
Posted: Thu Jan 13, 2005 4:09 am
by Pype.Clicker
You may wish to have a look at
http://www.nist.gov/dads/, the dictionary of algorithms and datastructures ...
[*] basic linked list simply assume each struct has a "next" field of the same struct type. (e.g.
struct item { struct item* next; ... };) and that some item* variable retains the list. You may link whatever you wish together, including static variables.
[*] more evolved linked list assume that the "list" itself is an "object", e.g. you add items to the list rather than linking items together.
Code: Select all
struct list {
struct *item first;
struct *item last;
};
#define EMPTY_LIST (struct list){first:NULL, last:NULL};
static inline void lpush(struct list* l, struct item* it) {
if (l->last) l->last=it;
else {
l->first=it; l->last=it;
}
}
static inline void lunshift(struct list* l, struct item *it) {
it->next=l->first;
l->first=it->next;
}
static inline struct item* lshift(struct list* l) {
struct item* it=l->first;
if (it) l->first=it->next;
return it;
}
HTH.
Re:linkedlist
Posted: Thu Jan 13, 2005 4:45 am
by distantvoices
@pype: just a question concerning your item_add function.
Code: Select all
static inline void lpush(struct list* l, struct item* it) {
it->next=NULL;
if (l->last){
l->last->next=it; //shan't we add the item to the list too?
l->last=it;
} else {
l->first=it; l->last=it;
}
}
Re:linkedlist
Posted: Thu Jan 13, 2005 6:40 am
by Pype.Clicker
beyond infinity wrote:
@pype: just a question concerning your item_add function.
Oops ... Yes we should
