A list implemented by each item (called a node) linking to the next item. It is one of the fundamental data structures (other examples are arrays and trees). The head of a linked list is its first node. Borrowing C's syntax, we can refer to the next node after the head (i.e. the second node) as head->next, the third node as head->next->next, and so on. The final node of a list traditionally points to null (usually equivalent to zero) which is an address that can never house a list node.

Advantages linked lists have over arrays include ${\displaystyle O(1)}$ insertion and removal, but at the cost of slower random access time, ${\displaystyle O(n)}$. Sometimes a program needs only to access a list sequentially: the perfect place to use a linked list. Furthermore, you need not allocate all the memory required for a linked list at once like you do for an array.

By far the most common type of linked list is the singly linked list, which this article describes, though variations do exist, each with their own advantages and disadvantages. Some of the popular variations are described below.

## Example

Here's are a few example declarations and functions in C of a linked list that keeps track of players in a game. The unusual struct declaration is a result of the self-referential nature of linked lists. Note that, outside of the struct, the list nodes are referred to as "player" but inside, they are "player_node".

```typedef struct player_node
{
struct player_node* next; /* Link to the next player */
char name[20];
int level;
} player;

player* head = NULL; /* Link to the first player, who is currently nonexistent */

{
/* Sometimes we don't care about the order of a list -- this makes insertion very easy. */
}

void send_message_to_all_players(char* message)
{
player* p;

/*
* The following line of code is a convenient way to traverse a linked list
* but don't attempt to change the list infrastructure (i.e. add or remove
* items) while this loop is active, which could be disastrous.
*/
for (p = head; p != NULL; p = p->next)
send_message_to_one_player(p, message);
}
```

## Variations

### Circular Lists

```function add_node_circular(head, node)
node->next = node
else
end function
```

The programmer of a circular list must be extra vigilant about segfaults. If the error checking in the pseudocode above was absent, the program would segfault when trying to add a node to a zero- or one-element list.

One of the problems with a linked list is that it can be difficult to remove an arbitrary node without traversing the list. This is because you have to find the element in the list that directly precedes it so you can change its next pointer. The singly-linked-list node removal operation might be coded as follows.

```function remove_node_singly(head, node)
while (tempnode->next != node)
tempnode = tempnode->next
tempnode->next = node->next
end function
```

With a doubly linked list, every node stores both a pointer to the next node and a pointer to the previous node. This makes the removal of an arbitrary node ${\displaystyle O(1)}$ instead of the usual ${\displaystyle O(n)}$, at the cost of having to use twice as much memory for list infrastructure. The doubly-linked-list node removal operation might be coded as follows.

```function remove_node_doubly(node)
node->prev->next = node->next
node->next->prev = node->prev
end function
```

## References

• Donald Knuth. "The Art of Computer Programming", Volume 1: "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3: "Linked Allocation", 2.2.4: Circular Lists, and 2.2.5: "Doubly Linked Lists".