Linked List
Computer Science: OCR A Level, topic 4.2.2
Linked List
Linked lists are commonly used data structures with benefits of flexibility and ease of use. They can be used to implement other data structures such as stacks and queues.
Linked list
- Linked lists consist of nodes.
- Each node contains a data item and a pointer to the next node in the sequence.
- A null pointer is used to identify the last item of data.
- The use of pointers means that unlike arrays, data in linked lists do not have to be stored contiguously in memory.
- They are also referred to as being ‘dynamic’ in that they can grow or shrink in size as and when necessary.
Example
- The diagram shown is graphical representation of a linked list containing the names of three animals in alphabetical order.
Adding nodes
- To add ‘Tiger’ to the list alphabetically, the pointer of node 1 is updated to point to the new node, which in turn points to the next in the sequence (node 2).
Deleting nodes
- To delete ‘Rhino’ from the list, the pointer of node 0 is updated to point to node 3.
- The data of node 1 is deleted.
- This node becomes the first of a separate list of empty nodes, ready to be filled again.