Связанный список решает такую задачу: как хранить коллекцию объектов, добавляя и удаляя туда объекты. (Простите, что я не пишу характеристики того и другого, почитайте это в умных книгах)
В чистом виде связанный список используется крайне редко из-за ограничений, но представьте себе объектный пул (кучу готовых к использованию объектов), и надо хранить список свободных — очень удобно использовать связанный. Также связанным иногда хранят содержимое гнезда в хэш-таблице.
Хэш-таблица решает другую задачу: наладить отображение ключ→значение. Например, «осёл → иа, петух → кукареку», и так далее. Массив, только индексом будет не цифра, а что-то другое: x[«осёл»] = «иа». Так называемый ассоциативный массив.
Если индексом массива может быть только цифра, поступим так: превратим нашего осла в цифру — например, о+с+ё+л = 4363 (в Юникоде), и пусть 63 — это номер гнезда. В 63-м элементе массива пусть и лежит наше «осёл → иа».
Если у другого животного значением хэша будет 63 — это хэш-коллизия, и в разных реализациях решается по-разному. Я знаю такое: в гнезде лежит не просто один элемент, но связанный список. Главное, что такое слегка снижает производительность, но допустимо.
Простой
Сложный
Средний
