맨 끝 삭제는 마지막 요소만 제거하면 되고, 맨 끝 삽입은 동적 배열 기준 용량이 남아 있으면 그 자리에 쓰면 됩니다. 이동이 없으니 $O(1)$입니다.

임의 위치는 다릅니다. 인덱스 2를 삭제하면 인덱스 3부터 끝까지 전부 한 칸씩 앞으로 당겨야 배열의 연속성이 유지됩니다. "인덱스로 바로 접근하니까 삭제도 $O(1)$"이라고 생각하기 쉽지만, 접근과 삭제 후 재정렬은 별개입니다.

배열의 모든 요소는 같은 타입이므로 크기가 고정입니다. int 배열이라면 요소 하나가 4바이트입니다. arr[5]의 주소는 &arr[0] + 5 * 4로 곱셈 한 번으로 계산합니다. 루프나 탐색 없이 CPU 명령어 하나로 끝납니다.

Python list처럼 다른 타입이 섞여도 $O(1)$인 이유는 list가 값을 직접 담지 않고 포인터(8바이트, 64bit)를 담기 때문입니다. 포인터 크기는 항상 고정이라 같은 계산이 성립합니다.

CPU 캐시는 메모리를 캐시 라인(보통 64바이트) 단위로 가져옵니다. 배열을 순회하면 인접한 요소들이 같은 캐시 라인에 있어 한 번 로드로 여러 요소를 처리합니다. 링크드 리스트는 노드가 힙에 흩어져 있어 다음 노드에 접근할 때마다 캐시 미스가 날 수 있습니다.

그래서 이론적으로 삽입/삭제가 $O(1)$인 링크드 리스트가 실제로는 배열보다 느린 경우가 많습니다. 요소 수가 작거나 캐시 미스 비용이 지배적이면 배열 순회가 압도적으로 빠릅니다.

"CPU 영향"이라는 표현이 애매한 이유는 두 관점의 답이 반대이기 때문입니다. 삽입·삭제 연산 횟수만 세면 포인터 두 개만 바꾸는 링크드 리스트가 일을 덜 하는 것처럼 보입니다. 하지만 CPU가 실제로 시간을 쓰는 곳은 연산이 아니라 메모리 대기입니다. RAM 접근은 캐시 적중보다 100배 안팎 느리므로, 캐시 미스가 반복되는 링크드 리스트 순회는 연산이 적어도 총 시간이 더 깁니다.

그래서 정확한 답은 조건부입니다. 노드 참조를 이미 들고 있는 삽입·삭제가 반복되는 구조라면 링크드 리스트가 CPU 일을 줄이고, 순회나 탐색이 섞이는 일반적인 사용이라면 배열이 캐시 효율 덕분에 빠릅니다. 모르는 관점의 질문을 받았을 때도 "어느 기준이라면 어느 쪽"이라는 조건부 형태로 답하면, 확신이 없는 상태에서도 판단 기준을 보여줄 수 있습니다.

단방향 링크드 리스트에서 노드를 삭제하려면 이전 노드의 next 포인터를 바꿔야 합니다. 삭제할 노드만 알고 이전 노드를 모르면, 처음부터 순회해 이전 노드를 찾아야 합니다.

단, 이중 연결 리스트(doubly linked list)는 각 노드가 이전 노드도 가리키므로 삭제할 노드만 알아도 $O(1)$에 삭제할 수 있습니다. 대신 노드 하나당 포인터가 두 개라 메모리를 더 씁니다.

C의 고정 배열은 선언 시 크기가 정해지고 바꿀 수 없습니다. 동적 배열(Python list, Java ArrayList, C++ vector)은 내부적으로 용량(capacity)을 관리합니다. 현재 크기가 용량에 도달하면 보통 2배로 새 배열을 할당하고 전체를 복사합니다.

2배씩 늘리면 복사 비용을 amortized $O(1)$로 만들 수 있습니다. n개를 append할 때 총 복사 횟수는 $1 + 2 + 4 + \cdots + n \approx 2n$이라 평균 $O(1)$입니다. 확장 순간만 $O(n)$이고, 나머지는 $O(1)$입니다.

LRU 캐시가 대표적인 예입니다. 최근에 사용된 항목을 앞으로 이동시키는 연산이 빈번한데, 이미 노드 참조를 갖고 있으므로 $O(1)$에 처리할 수 있습니다. HashMap과 이중 연결 리스트를 결합해 $O(1)$ get/put을 구현합니다.

OS의 프로세스 스케줄러나 메모리 할당기에서도 링크드 리스트를 씁니다. 가용 메모리 블록 목록을 관리할 때 블록을 추가하거나 제거하는 작업이 많고, 순서가 자주 바뀌기 때문입니다.

C의 memcpy처럼 연속된 메모리 블록을 통째로 복사합니다. 하드웨어 수준에서 최적화된 명령어를 쓰기 때문에 루프로 하나씩 복사하는 것보다 빠릅니다. Python의 list[:]나 list.copy()도 같은 방식으로 동작합니다.

복사 중에 원본이 변경되면 복사본에는 반영되지 않습니다. 얕은 복사(shallow copy)는 요소가 담고 있는 객체 참조만 복사하므로 중첩 구조는 원본과 복사본이 같은 내부 객체를 공유합니다.

C array는 int를 담으면 모든 요소가 4바이트로 고정이라 start + index * 4로 주소를 계산합니다. Python list는 int든 str든 객체든 상관없이 요소마다 포인터(8바이트, 64bit 기준)를 씁니다. 실제 값은 heap 어딘가에 있는 Python 객체이고, list는 그 포인터 배열입니다.

그래서 list[5]는 pointer_array_start + 5 * 8로 포인터 위치를 구하고, 그 포인터가 가리키는 Python 객체를 읽습니다. 타입이 달라도 포인터 크기는 항상 고정이라 $O(1)$입니다. 대신 실제 값에 접근하려면 포인터 역참조가 한 단계 더 필요합니다.

일반 배열로 저장하면 0이 대부분인 공간에 메모리를 낭비합니다. 사용자 100만 명 중 1%만 특정 플래그가 1이라면, 배열은 100만 칸 중 99만 칸이 0입니다.

Hash map은 값이 있는 사용자 ID만 key로 저장해 메모리를 아낍니다. 탐색은 $O(1)$이고, 없는 key는 0으로 취급합니다.

값이 0과 1만 있는 경우라면 bitset이 더 효율적입니다. 요소 하나를 1비트로 표현해 메모리가 1/8로 줄고, 비트 연산으로 여러 플래그를 한 번에 처리할 수 있습니다. DB에서 인덱스 최적화나 블룸 필터도 이 개념을 씁니다.