Adding a Node to a List

You can add a node to a list in any of the following ways:

The beginning or end of a list.
A position in the list that corresponds to the node's priority.
A position in the list determined by comparing one or more values contained in the node to values of nodes currently in the list, or relative to another node already in the list.

The following sections describe each of these cases.

Adding a Node to the Head of a List

To add a node to the head of a list, use the AddHead() function:

void AddHead( List *l, Node *n )

The l argument is a pointer to the list to which to add the node, while the n argument is a pointer to the node to add.

Adding a Node to the Tail of a List

To add a node to the tail of a list, use the AddTail() function:

void AddTail( List *l, Node *n )

The l argument is a pointer to the list to which to add the node, while the n argument is a pointer to the node to add.

Adding a Node After Another Node in a List

To add a node to a list and position it after another node already in the list, use the InsertNodeAfter() function:

void InsertNodeAfter( Node *oldNode, Node *newNode )

The oldNode argument is a pointer to a node already in the list, while the newNode argument is a pointer to the new node to insert.

Adding a Node Before Another Node in a List

To add a node to a list and position it before another node already in the list, use the InsertNodeBefore() function:

void InsertNodeBefore( Node *oldNode, Node *newNode )

The oldNode argument is a pointer to a node already in the list, while the newNode argument is a pointer to the new node to insert.

Adding a Node According to Its Priority

The nodes in a list are often arranged by priority. To insert a new node immediately before any other nodes of the same priority, use the InsertNodeFromHead() function:

void InsertNodeFromHead( List *l, Node *n )

As in the other functions for adding nodes, the l argument is a pointer to the list to which to add the node, while the n argument is a pointer to the node to add.

The name InsertNodeFromHead() refers to the way the kernel traverses the list to find the correct position for a new node: it compares the priority of the new node to the priorities of nodes already in the list, beginning at the head of the list, and inserts the new node immediately after nodes with higher priorities. If the priorities of all the nodes in the list are higher than the priority of the new node, the node is added to the end of the list.

To insert a new node immediately after all other nodes of the same priority, you use the InsertNodeFromTail() function:

void InsertNodeFromTail( List *l, Node *n )

Again, the l argument is a pointer to the list to which to add the node, while the n argument is a pointer to the node to add. As with InsertNodeFromHead(), the name InsertNodeFromTail() refers to the way the kernel traverses the list to find the correct position for the new node: it compares the priority of the new node to the priorities of nodes already in the list, beginning at the tail of the list, and inserts the new node immediately before nodes with lower priorities. If the priorities of all the nodes in the list are lower, the node is added to the head of the list.

Adding a Node According to Other Node Values

Arranging list nodes by priority is only one way to order a list. You can arrange the nodes in a list by node values other than priority by using the UniversalInsertNode() function to insert new nodes:

void UniversalInsertNode( List *l, Node *n, bool (*f)(Node *n, Node *m) )

The l argument is a pointer to the list to which to add the node, while the n argument is a pointer to the node to add. Like InsertNodeFromHead(), UniversalInsertNode() compares the node to be inserted with nodes already in the list, beginning with the first node. The difference is that it uses the comparison function f provided by your task to compare the new node to existing nodes. If the comparison function returns TRUE, the new node is inserted immediately before the node to which it was compared. If the comparison function always returns FALSE, the new node becomes the last node in the list. The comparison function, whose arguments are pointers to two nodes, can use any data in the nodes for the comparison.