Списки

Array (as in Python):

• хранится сплошным куском в памяти
• доступ O(1) к любому элементу
• дорого вставлять элемент в середину списка

Linked List (as in Haskell):

• элементы хранятся в разных местах в памяти (каждый элемент содержит ссылку на следующий)
• доступ O(n) к любому элементу
• дёшево вставлять элементы в середину списка

Словари

As Data Structure:

• Hash Table
• Hash Map
• Hash Set

As ADT (abstract data type):

• Associative Array
• Map
• Symbol Table
• Dictionary