Code:
struct my_struct
{
int num;
struct my_struct *next;
};
struct my_struct *list_head = NULL;
struct my_struct *new_node(void)
{
struct my_struct *new;
new = malloc(sizeof(my_struct));
// Possibly do some initialization here for new nodes.
new->next = list_head;
list_head = new;
return new;
}
int main(void)
{
struct my_struct *ptr;
ptr = new_node();
ptr->num = 86;
ptr = new_node();
ptr->num = 17;
for(ptr = list_head;ptr != NULL;ptr = ptr->next)
printf("%d\n", ptr->num);
return 0;
}
Now, this is just one way to implement a linked list and it's really not very useful in this little example program. There are an uncountable number of uses for linked lists and there are also several different kinds.
The one in my example is a very simple one known as a
singly-linked list or just
linked list. The start of the list is marked by the variable list_head. The end of the list is marked by a NULL value. This makes cycling through the list very simple and straight-forward, as you can see from the example. Every time a node is created, it's added to the head of the list. The output from the program above would show 17 before 86.
There are also implementations where the tail of the list (the last node) points to the head of the list instead of pointing to NULL. This is known as a
circularly-linked list (just try to picture it and you can see why).
Then you can also have
doubly-linked lists. In that case there would be a prev pointer in addition to the next pointer inside the structure. The prev pointer would (duh) point to the node before it. If you're planning on doing a lot of node removal this makes it a lot easier. It also adds the ability to cycle through the list backwards. The next pointer of the list tail would point to NULL and the prev pointer of the list head would also point to NULL.
Then you have your
circular doubly-linked lists. This is where the next pointer of the list tail points to the list head and the prev pointer of the list head points to the list tail.
You can also have different combinations of what's listed above or even have more than just a next and prev pointer or they might have names like left and right instead (as is the case usually for binary trees). But the styles I listed above are common.
The bottom line, I guess, is linked lists are highly flexible and can look however you want, but if you have a structure with a member that's a pointer to the same structure then you can bet it's used for a linked list. Each instance of the structure in the list is a node.
Linked lists are very useful in situations where you might normally use an array, but you'll be doing a lot of insertions and deletions. With an array you'd have to do a lot of value copying to make it happen, but with a linked list you just change a couple of pointers. They're also used in hash tables (basically an array of linked lists), vitual memory mangers, and compression algorithms, just to name a few examples.
There's enough information on linked lists that you could write whole book on them (and I'm sure there's a few out there already!) so I don't want to get into too much detail. Hopefully this information gives you an understandable overview, but I'll be happy to answer any specific questions you might have.
