C Language Linked lists
Remarks
The C language does not define a linked list data structure. If you are using C and need a linked list, you either need to use a linked list from an existing library (such as GLib) or write your own linked list interface. This topic shows examples for linked lists and double linked lists that can be used as a starting point for writing your own linked lists.
Singly linked list
The list contains nodes which are composed of one link called next.
Data structure
struct singly_node
{
struct singly_node * next;
};
Doubly linked list
The list contains nodes which are composed of two links called previous and next. The links are normally referencing to a node with the same structure.
Data structure
struct doubly_node
{
struct doubly_node * prev;
struct doubly_node * next;
};
Topoliges
Linear or open
Circular or ring
Procedures
Bind
Bind two nodes together.
void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
prev->next = next;
next->prev = prev;
}
Making circularly linked list
void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
doubly_node_bind (head, head);
}
Making linearly linked list
void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
head->prev = NULL;
tail->next = NULL;
doubly_node_bind (head, tail);
}
Insertion
Lets assume a empty list always contains one node instead of NULL. Then insertion procedures do not have to take NULL into consideration.
void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
doubly_node_bind (prev, insertion);
doubly_node_bind (insertion, next);
}
void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
doubly_node_insert_between (tail->prev, tail, insertion);
}
void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
doubly_node_insert_between (head, head->next, insertion);
}
