散々語り尽くされていますが、リストの先頭に対する要素の挿入（insert）や要素の削除（pop）の計算コストはO(N)かかります。このことは公式ドキュメントのcolections.dequeの説明に記載されていているのでその該当箇所を引用すると、

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

と書いてあります。

つまり、N回のforループ内で先頭に要素を追加する処理をしたら計算コストはO(N²)になります。

具体的に言うと、 C - pushpush のような問題でリストを使って解こうとすると、TLEします。

よって、先頭に対する挿入や削除操作を何度もするときはリストの代わりにcolections.dequeを使うと良いという話になります。deque（デックと読む）の先頭に対する挿入や削除操作の計算コストはO(1)です。ただしソートは使えないので注意。

検証

リストとdequeの検証を少ししてみます。

listとdequeの先頭の要素に対する操作の比較 · GitHub

from collections import deque
import time

N = 2*10**5

def list_append():
    a = []
    start = time.time()

    for i in range(N):
        a.append(100)  # 末尾に要素を追加

    end = time.time()

    print(f"list_pop: {end-start}sec.")


def list_insert():
    a = []
    start = time.time()

    for i in range(N):
        a.insert(0, 100)  # 先頭に要素を挿入

    end = time.time()

    print(f"list_insert: {end-start}sec.")


def list_pop():
    a = [1] * N
    start = time.time()

    for i in range(N):
        a.pop(0)  # 先頭の要素の削除

    end = time.time()

    print(f"list_pop: {end-start}sec.")


def deque_append():
    a = deque()
    start = time.time()

    for i in range(N):
        a.append(100)  # 末尾に要素を追加

    end = time.time()

    print(f"deque_append: {end-start}sec.")

def deque_appendleft():
    a = deque()
    start = time.time()

    for i in range(N):
        a.appendleft(100)  # 先頭に要素を挿入
    
    end = time.time()

    print(f"deque_appendleft: {end-start}sec.")


def deque_popleft():
    a = [1] * N
    a = deque(a)
    start = time.time()

    for i in range(N):
        a.popleft()  # 先頭の要素の削除
    
    end = time.time()

    print(f"deque_popleft: {end-start}sec.")


if __name__ == "__main__":
    list_append()
    list_insert()
    list_pop()

    print()

    deque_append()
    deque_appendleft()
    deque_popleft()

結果は以下の通り。

list_append: 0.009970903396606445sec.
list_insert: 5.814519643783569sec.
list_pop: 3.187533140182495sec.

deque_append: 0.008010149002075195sec.
deque_appendleft: 0.00896906852722168sec.
deque_popleft: 0.008002996444702148sec.

やはりリストでは、先頭に対する挿入と削除操作（insertとpop）は時間がかかっています。appendは両方共高速です。