먼저 삽입·삭제 연산을 살펴보겠습니다. 그림을 보세요.

▲ 그림 4-2 연결 리스트의 삽입 1

그림 4-2는 요소 세 개를 가진 연결 리스트에 새로운 노드를 삽입하는 첫 번째 과정입니다. 노드 1과 2 사이에 4를 삽입하려고 합니다. 동적 배열이었다면 2와 3 모두 옮기는 연산을 한 후 4를 삽입해야 하지만 연결 리스트는 다릅니다. 그저 그림 4-3과 같이 4의 link는 2를 가리키게 하고, 1의 link는 4를 가리키게 하면 됩니다.

▲ 그림 4-3 연결 리스트의 삽입 2

예제에서는 1 다음의 데이터가 두 개라서 연산 횟수의 차이를 느낄 수 없을지도 모릅니다. 하지만 1 이후의 데이터 개수가 10만 개였다면 동적 배열은 이동 연산이 10만 번 필요하고, 연결 리스트는 여전히 참조 할당 연산이 단 두 번만 필요합니다. 빅오는 O(1)인 것이지요. 삭제도 마찬가지로 빅오는 O(1)입니다.