# 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.