Согласно официальной документации они реализованы как linked list.
Списки Redis реализованы через связанные списки. Это означает, что даже если у вас есть миллионы элементов внутри списка, операция добавления нового элемента в заголовок или в конец списка выполняется за постоянное время. Скорость добавления нового элемента с помощью команды LPU SH в заголовок списка из десяти элементов такая же, как при добавлении элемента в заголовок списка с 10 миллионами элементов.
В чем обратная сторона? Доступ к элементу по индексу происходит очень быстро в списках, реализованных с помощью массива (индексированный доступ с постоянным временем), и не так быстро в списках, реализованных связанными списками (где операция требует объема работы, пропорционального индексу элемента, к которому осуществляется доступ).
Из-за этого LPOP / RPOP или LPUSH / PUSH временная сложность равна O(1), так как они имеют дело с орлом / решкой. В то время как временная сложность LINDEX s равна O(N).