포인터 연결 순서

연결리스트는 데이터를 밀지 않고 링크를 다시 잇는다

중간 삽입은 새 노드가 먼저 기존 다음 노드를 붙잡아야 하고, 삭제는 이전 노드가 삭제 대상의 다음 노드를 건너뛰게 만든 뒤 메모리를 반환합니다.

1

기준 노드 고정

20과 30 사이에 넣는다면 20을 prev로 보고, 30은 prev->next에 남아 있어야 합니다.

prev = 20

2

새 노드 next 먼저 연결

새 노드 25의 next를 기존 30으로 연결해야 뒤쪽 리스트를 잃지 않습니다.

newNode->next = prev->next;

3

이전 노드가 새 노드로

prev의 next를 25로 바꾸면 10, 20, 25, 30 순서가 완성됩니다.

prev->next = newNode;

4

삭제는 건너뛰기

20을 지울 때는 10의 next가 30을 가리키게 한 뒤 target을 free합니다.

prev->next = target->next;

연결리스트 기준

위치 탐색

삽입할 위치를 찾는 과정은 head부터 따라가므로 O(n)일 수 있습니다.

연결 변경

prev를 이미 알고 있다면 실제 링크 변경 자체는 O(1)입니다.

포인터 연결 순서

순서 반전

prev->next를 먼저 바꾸면 기존 30으로 가는 주소를 놓칠 수 있습니다.

첫 노드

첫 노드 삭제는 prev가 없으므로 head = head->next가 핵심입니다.