pointer rewiring
삽입과 삭제는 값을 옮기지 않고 링크를 바꾼다
연결리스트의 핵심은 data가 아니라 next를
어떤 순서로 바꾸느냐이다. 순서를 틀리면 기존 노드로 가는 길을
잃는다.
head
리스트 시작점을 보존한다
prev
삽입·삭제 위치의 이전 노드
target
삭제하거나 건너뛸 노드
메모리 연결 상태 비교
기존
10
next: 20
20 prev
next: 30
30
next: NULL
끝
삽입 후
10
next: 20
20 prev
next: 25
25 new
next: 30
30
next: NULL
삭제 후
10
next: 30
20 target
free 대상
30
next: NULL
target은 리스트 밖
포인터 변경 순서
| 상황 | 먼저 할 일 | 다음 할 일 | 틀리면 생기는 문제 |
|---|---|---|---|
| 중간 삽입 |
newNode->next = prev->next
|
prev->next = newNode |
기존 다음 노드 주소를 잃을 수 있다 |
| 중간 삭제 |
prev->next = target->next
|
free(target) |
해제 후 접근하면 잘못된 메모리를 본다 |
| 첫 노드 삭제 | target = head |
head = head->next |
head를 잃으면 리스트 입구가 사라진다 |
1
주소 보존
기존 다음 노드 주소를 먼저 새 노드에 저장한다.
2
연결 우회
삭제는 target을 지우기 전에 prev가 다음을 가리키게 한다.
3
입구 관리
첫 노드는 이전 노드가 없으므로 head 자체를 바꾼다.