teach-ict.com logo

THE education site for computer science and ICT

3. Linked List

Linked lists are a valuable programming tool. They allow you to add even more structure than just ordering a list.

Every element (or node) in a linked list points to a neighbouring node. This means if the progam accesses any node, it can then find its linked node. For example:

linked list

This is a singly-linked list. Each node in the above diagram has two parts. The node item itself, and a "pointer". The pointer tells the program where the next associated node is located.

The node item can be anything from a single byte to a complicated data structure of itself. Nodes do not have to be of the same type (unlike an array- see later).

A slightly more complicated version is the doubly-linked list. For example:

linked list

A doubly-linked list has two pointers. One references the location of the next node and the other points to the previous node. If the 'previous node' is null, then that is the start of the list. If the 'next pointer' is null, then that is the end of the list.

These pointers and the links they create make it simple to insert or delete items from a list without breaking the order. If an item is added or removed, the pointers of its neighbours are updated. They also make it simple for a program to traverse the list.

Linked lists are the basis of much more complicated structures such as stacks, queues and trees.

Challenge see if you can find out one extra fact on this topic that we haven't already told you

Click on this link: What is a linked list