자료구조

배열과 리스트

왜 맨 앞에 끼우면 느릴까

왜 밀어야 할까

• 칸이 딱 붙어 있다 — 중간에 빈칸이 없다. 끼우려면 뒤 사람을 전부 밀어야 한다
• 맨 뒤는 비어 있다 — 밀 사람이 없으니 그냥 붙이면 된다
• 그 대신 번호로 바로 간다 — 3번 칸은 번호만 알면 줄을 세지 않고 곧장 찾아간다

가끔은 append 도 오래 걸립니다. 칸이 꽉 차면 줄 전체를 더 큰 자리로 옮기기 때문입니다. 파이썬이 그때 칸을 넉넉하게 잡아 두어서 평균하면 append 한 번은 칸 하나 옮기는 일 정도입니다.

코드는 뒤에서부터 한 칸씩 민다

다음을 눌러 한 줄씩 넘기며 빈자리가 맨 앞으로 오는 걸 보세요.

• arr.append(None) — 줄 맨 뒤에 빈자리를 하나 만든다
• range(len(arr) - 1, 0, -1) — 뒤에서 앞으로 센다. 앞에서부터 밀면 뒤 사람을 덮어쓴다
• moved — 한 칸 밀 때마다 1씩 는다. 끝나면 줄 길이와 같다

한 줄이어도 한 번이 아니다

아래 시간은 Python 3.14 에서 직접 잰 값입니다. 컴퓨터마다 달라서 비율만 보세요.

• arr.pop(0) — 맨 앞을 빼면 나머지를 한 칸씩 당긴다. 10만 칸에서 5만 번 하면 0.58초. arr.pop() 은 0.0015초
• arr.insert(0, x) — 맨 앞 끼우기를 10만 번 하면 1.6초. append 10만 번은 0.002초
• x in arr — 앞에서부터 하나씩 본다. 100만 칸에서 맨 끝 값을 찾는 데 약 0.005초. 반복문 안에서 1,000번 쓰면 약 5초
• arr[1:] — 줄을 통째로 복사한 새 리스트다. 반복문 안에서 arr = arr[1:] 을 하면 칸 수만큼 복사가 되풀이된다

줄 서기(맨 앞에서 빼고 맨 뒤에 넣기)를 리스트로 흉내 내면 pop(0) 이 계속 나옵니다. 뒤에서 볼 큐와 덱의 deque 는 같은 일을 당기기 없이 한 번에 합니다.

문제에서 이 말이 보이면

다음 장에서는 한쪽 끝에서만 넣고 빼는 스택을 봅니다.