Martin Broadhurst

Data Structures

Preface

This is a collection of data structures and data structure related algorithms I've written in C.

Contents

• Dynamic array
• Dynamic array with centring of the used block
• Singly-linked list
• Reversing a singly-linked list
• Singly-linked list with free nodes at the head
• Doubly-linked list
• Sorting a linked list by turning it into a binary tree
• Circular linked list
• Linked list embedded in an array
• Linked list embedded in an array with compaction
• Linked list with node recycling
• Stack
• Queue
• Circular queue
• Deque
• Binary tree
• Loading a binary tree with sorted data
• Counting nodes in a binary tree recursively
• Finding the height of a binary tree recursively
• Finding the nth element in a binary tree
• Randomised binary tree
• Binary tree balanced by access frequency
• Move-to-top binary tree
• Hash table

Source code

Each of the following archives contains the full source code, example programs, tests and build instructions:

• mbds.tar.gz (27 KB, Linux)
• mbds.zip (55 KB, Windows)