방송대 자료구조 5강 : 연결 리스트의 노드 연결과 삽입·삭제

방송대 자료구조 5강: 연결 리스트의 노드 연결과 삽입·삭제

중간에 원소 하나를 넣을 때 배열은 뒤 원소들을 움직여야 하지만, 연결 리스트는 이웃을 가리키는 주소만 바꾼다. 다만 포인터를 잘못된 순서로 갱신하면 남은 리스트를 잃는다. 이 글은 노드의 논리 순서를 따라 삽입·삭제 과정을 직접 추적하고, 공백·한 노드·여러 노드에서 달라지는 처리까지 판별하도록 구성했다.

리스트의 순서는 메모리 위치가 아니라 관계로 정해진다

리스트는 원소 사이에 논리적인 순서가 있는 자료구조다. 여기서 순서는 메모리 주소가 작은 원소부터 큰 원소로 이어진다는 뜻이 아니다. 사람이 정한 앞뒤 관계가 유지되면 물리적으로 떨어진 곳에 저장되어도 같은 리스트가 된다.

배열로 리스트를 구현하면 인덱스의 증가가 논리 순서와 물리 순서를 함께 나타낸다. 연결 리스트에서는 각 노드가 다음 노드의 주소를 저장하므로, 주소 5000의 노드가 주소 1200의 노드를 가리켜도 둘째 노드는 논리적으로 뒤에 있다. 개발자가 보는 순서는 포인터 연결을 따라 읽어야 한다.

판단 핵심: 노드의 주소값 자체를 정렬 기준으로 보지 않는다. head에서 시작해 각 link가 가리키는 노드를 차례로 방문한 결과가 리스트의 논리 순서다.

배열의 이동 비용이 연결 리스트를 필요하게 만든다

배열은 연속된 메모리에 원소를 저장하므로 인덱스로 원하는 원소에 직접 접근하기 쉽다. 그러나 가운데에 원소를 삽입하려면 삽입 위치 뒤의 원소들을 한 칸씩 뒤로 밀어야 한다. 삭제할 때는 빈자리를 없애기 위해 뒤 원소들을 앞으로 당겨야 한다. 초기 배열 공간이 가득 차면 더 큰 공간을 새로 확보하고 원소를 옮기는 상황도 생긴다.

연결 리스트는 원소값과 다음 노드의 위치 정보를 한 노드에 묶는다. 노드들은 물리적으로 연속될 필요가 없으며, 중간 삽입과 삭제는 관련 링크를 다시 연결하는 방식으로 처리한다. 원소 자체를 연쇄 이동하는 문제는 줄지만, 특정 위치를 찾으려면 앞에서부터 링크를 따라가야 하고 노드마다 주소 저장 공간이 필요하다.

판단 상황	배열 리스트	연결 리스트	선택 기준
중간 삽입·삭제가 잦음	뒤 원소 이동이 발생	이웃 링크를 갱신	위치를 이미 알고 있다면 연결 방식이 유리
임의 위치를 바로 읽음	인덱스로 직접 접근	앞에서부터 순회	접근 빈도가 높으면 배열이 단순
저장 공간 구성	연속 공간이 필요	노드를 필요할 때 동적 할당	크기 변화와 메모리 배치를 고려
원소별 부가 공간	값 중심	다음 주소를 함께 저장	링크 필드 비용을 포함해 판단

오개념 교정: 연결 리스트가 모든 연산에서 배열보다 빠른 것은 아니다. 삽입 위치의 이전 노드를 이미 알고 있을 때 연결 변경은 간단하지만, 그 노드를 찾는 순회에는 원소 수에 비례한 단계가 들 수 있다.

노드는 데이터와 다음 주소를 한 단위로 묶는다

단순 연결 리스트의 노드는 원소값을 담는 data 필드와 다음 노드의 주소를 담는 link 필드로 구성된다. head는 첫 노드의 주소를 보관하며, 마지막 노드의 link는 뒤에 노드가 없음을 나타내는 NULL이다. 공백 리스트에서는 head 자체가 NULL이다.

포인터 변수는 데이터 값이 아니라 데이터가 저장된 위치의 주소를 담는다. 동적 메모리 할당으로 새 노드를 만들면 먼저 data에 값을 넣고 link를 안전한 초기값으로 설정한다. 삽입이 끝나기 전에는 아직 리스트에 연결되지 않은 독립 노드일 뿐이다. 삭제한 노드는 연결에서 제외한 뒤 메모리를 반환해야 한다.

구성 요소	담는 정보	상태를 읽는 질문
data	현재 노드의 원소값	이 노드가 표현하는 값은 무엇인가?
link	다음 노드의 주소	다음에 방문할 노드는 어디인가?
head	첫 노드의 주소	순회를 어디에서 시작하는가?
NULL	가리키는 다음 노드가 없음	리스트가 끝났거나 비어 있는가?

삽입은 새 노드가 기존 뒷부분을 먼저 붙잡아야 안전하다

이전 노드 prev 뒤에 새 노드 new를 삽입한다고 하자. 삽입 전에는 prev.link가 원래 다음 노드 next를 가리킨다. 연결을 잃지 않으려면 새 노드가 먼저 next를 가리킨 뒤, prev가 새 노드를 가리켜야 한다.

1. 새 노드를 할당하고 원소값을 저장한다.
2. new.link = prev.link로 기존 뒷부분의 시작 주소를 보존한다.
3. prev.link = new로 앞부분과 새 노드를 연결한다.
4. head부터 링크를 따라가 새 순서가 유지되는지 검산한다.

직접 구성한 포인터 추적

리스트가 12 → 28 → 41이고 12 뒤에 19를 삽입한다고 가정하자. 먼저 새 노드 19의 링크를 28의 주소로 정한다. 그다음 12의 링크를 19의 주소로 바꾸면 12 → 19 → 28 → 41이 된다. 12의 링크를 먼저 19로 바꾸고 나서 new.link = prev.link를 수행하면, 이 시점의 prev.link는 이미 새 노드를 가리켜 19가 자기 자신을 가리키는 잘못된 연결이 생긴다.

삽입 순서 기억법: 뒤를 먼저 보존하고 앞을 나중에 바꾼다. 새 노드의 링크를 먼저, 이전 노드의 링크를 나중에 갱신한다.

머리와 끝 삽입은 같은 연결 원리에서 경계만 달라진다

공백 리스트에 첫 노드를 넣을 때는 기존 노드가 없으므로 새 노드의 링크를 NULL로 두고 head가 새 노드를 가리키게 한다. 머리 삽입이라면 새 노드가 기존 head를 가리키게 한 뒤 head를 새 노드로 바꾼다.

강의의 끝 삽입 코드는 공백 여부를 먼저 검사한다. 비어 있지 않으면 head에서 시작해 link == NULL인 마지막 노드를 찾고, 그 노드의 링크가 새 노드를 가리키게 한다. 꼬리 포인터를 별도로 보관하지 않는 이 구현에서는 마지막 노드를 찾기 위해 매번 순회가 필요하다.

삽입 위치	먼저 보존할 연결	마지막에 바꿀 포인터	경계 조건
공백 리스트의 첫 노드	새 노드 링크를 NULL로 초기화	head = new	head == NULL
머리	new.link = head	head = new	기존 첫 노드 보존
중간	new.link = prev.link	prev.link = new	prev가 유효해야 함
끝	new.link = NULL	last.link = new	마지막 노드 탐색

삭제는 우회 연결을 만든 뒤 노드의 메모리를 반환한다

중간 노드 del을 삭제할 때는 이전 노드 prev가 삭제 노드의 다음 노드를 직접 가리키게 해야 한다. 핵심 식은 prev.link = del.link다. 이 우회 연결로 리스트의 앞부분과 뒷부분을 이어 놓은 다음 free(del)로 삭제 노드의 메모리를 반환한다.

순서를 거꾸로 해 free(del)부터 실행하면 더 이상 유효하지 않은 삭제 노드의 link를 읽으려는 문제가 생긴다. 또 링크만 우회하고 메모리를 반환하지 않으면 리스트에서는 접근할 수 없지만 할당 상태로 남은 메모리가 발생한다. 따라서 삭제는 ‘다음 주소 확보 → 우회 연결 → 메모리 반환’의 세 단계로 읽어야 한다.

삭제 상태를 직접 추적하기

앞의 12 → 19 → 28 → 41에서 28을 삭제한다고 하자. prev는 19, del은 28을 가리킨다. 19의 링크를 28의 링크, 즉 41의 주소로 바꾸면 12 → 19 → 41로 연결된다. 그 뒤 28의 메모리를 반환한다. 값만 지우고 링크를 그대로 두는 것은 노드 삭제가 아니다.

잘못된 접근과 교정: 삭제 대상만 알고 이전 노드를 모르면 단순 연결 리스트에서는 우회시킬 링크를 바로 바꿀 수 없다. 검색할 때 현재 노드뿐 아니라 이전 노드도 함께 추적해야 하는 이유다.

마지막 노드 삭제는 공백·한 노드·여러 노드를 나눠 처리한다

끝 노드 삭제는 리스트 상태에 따라 처리가 달라진다. 공백 리스트라면 삭제할 대상이 없으므로 연산을 끝낸다. 노드가 하나라면 그 노드를 반환하고 head = NULL로 바꾼다. 노드가 여러 개라면 마지막 노드와 그 이전 노드를 함께 찾아야 한다.

1. head == NULL이면 종료한다.
2. head.link == NULL이면 한 노드만 있으므로 그 노드를 반환하고 head를 NULL로 만든다.
3. 여러 노드라면 prev와 del을 나란히 이동해 del.link == NULL인 지점까지 간다.
4. 마지막 노드 del을 반환하고 prev.link = NULL로 끝 표시를 갱신한다.

마지막 노드의 링크만 NULL로 바꾸는 것은 아무 변화가 없다. 마지막 노드는 원래부터 NULL을 갖기 때문이다. 반드시 이전 노드의 링크를 NULL로 바꿔야 삭제된 노드로 가는 연결이 끊긴다.

특정 값 삭제는 검색과 연결 변경을 하나의 흐름으로 묶는다

특정 값을 가진 노드를 삭제하려면 del이 현재 검사할 노드를, prev가 그 이전 노드를 가리키도록 함께 이동한다. del.data가 목표값과 같으면 삭제 함수에 두 포인터를 전달하고, 다르면 prev = del, del = del.link 순서로 한 칸 전진한다.

다만 첫 노드를 삭제하는 경우에는 실제 이전 데이터 노드가 없다. 강의 구현은 리스트 헤더 구조를 이전 위치처럼 활용해 head를 바꿀 수 있게 한다. 구현 방식이 달라 헤더가 없다면 첫 노드 삭제를 별도 경계 사례로 처리해야 한다. 중요한 것은 목표 노드만 찾는 것이 아니라, 목표로 들어오는 링크를 가진 위치까지 확보하는 것이다.

검색·삭제 체크: 공백인가 → 현재 노드가 목표인가 → 아니라면 이전·현재 포인터를 함께 전진하는가 → 찾았다면 우회 연결을 먼저 만드는가 → 메모리를 반환하는가를 순서대로 확인한다.

포인터 문제는 값보다 화살표의 전후 상태를 그려 검산한다

연결 리스트 코드에서 대입문은 단순한 값 변경이 아니라 화살표 하나를 옮기는 행위다. 따라서 각 문장을 실행하기 전과 후에 head, 이전 노드, 현재 노드, 새 노드가 무엇을 가리키는지 적으면 연결 손실을 찾기 쉽다.

1. 출발점 표시: head와 NULL을 먼저 표시한다.
2. 역할 구분: 새로 넣을 노드, 삭제할 노드, 이전 노드를 서로 다른 이름으로 둔다.
3. 보존 확인: 덮어쓸 링크가 가리키던 뒷부분의 주소를 다른 포인터가 잡고 있는지 확인한다.
4. 도달성 검사: 연산 뒤 head에서 모든 남은 노드에 도달하고 마지막 링크가 NULL인지 확인한다.
5. 메모리 검사: 삭제 노드는 연결을 끊은 뒤 반환했고, 새 노드는 정확히 한 번 연결했는지 확인한다.

자가 점검으로 A → B → C에서 B 뒤에 X를 넣는다면 먼저 바꿀 링크는 X.link이고 그 값은 C의 주소다. B를 삭제한다면 A의 링크를 C로 바꾼 뒤 B의 메모리를 반환한다. 두 경우 모두 기존 뒷부분 C를 잃지 않는지가 검산의 중심이다.

핵심 개념 정리

• 리스트의 논리 순서는 물리 주소의 크기가 아니라 head에서 link를 따라가는 관계로 결정된다.
• 배열은 직접 접근이 쉽지만 중간 삽입·삭제에 이동이 필요하고, 연결 리스트는 노드별 링크 비용과 순회 비용을 감수해 연결 변경으로 원소를 다룬다.
• 노드는 data와 link로 구성되며 공백 리스트의 head와 마지막 노드의 link는 NULL이다.
• 중간 삽입은 새 노드가 기존 뒷부분을 먼저 가리킨 뒤 이전 노드가 새 노드를 가리켜야 한다.
• 삭제는 이전 노드가 삭제 노드의 다음 노드를 가리키게 한 후 삭제 노드의 메모리를 반환한다.
• 공백·한 노드·여러 노드와 첫 노드·중간 노드·마지막 노드는 경계 조건에 맞춰 포인터를 다르게 갱신한다.

전체 사고 흐름: 연결 리스트 연산은 ‘누가 누구를 가리키는가’를 연산 전후로 비교하는 문제다. 덮어쓸 링크의 기존 목적지를 먼저 보존하고, head에서 남은 노드까지의 도달성을 확인한 다음, 더 이상 연결되지 않은 삭제 노드만 반환한다.

예상문제 10선

1. 단순 연결 리스트에서 노드의 link 필드가 저장하는 것은?

① 현재 노드의 인덱스 번호 ② 논리적으로 다음에 올 노드의 주소 ③ 리스트에 저장된 전체 원소 수 ④ 현재 노드의 원소값 복사본

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 연결 리스트의 논리 순서는 배열 인덱스가 아니라 포인터 연결로 표현한다.
• ② 정답: link의 주소를 따라가면 현재 노드 다음의 논리적 원소에 도달한다.
• ③ 오답: 전체 원소 수는 별도로 관리할 수 있지만 각 link의 기본 역할은 아니다.
• ④ 오답: 원소값은 data 필드가 저장하며 link는 위치 정보를 담는다.

2. 배열 리스트와 연결 리스트의 중간 삽입을 옳게 비교한 것은?

① 배열은 링크만 바꾸고 연결 리스트는 모든 뒤 원소를 이동한다. ② 두 방식 모두 삽입 위치와 무관하게 원소 이동이 필요하다. ③ 연결 리스트는 위치 탐색과 링크 저장이 필요하지 않다. ④ 배열은 뒤 원소를 이동할 수 있고, 연결 리스트는 위치를 찾은 뒤 이웃 링크를 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 두 구현의 삽입 처리 방식을 서로 뒤바꿨다.
• ② 오답: 연결 리스트는 원소 연쇄 이동 대신 관련 포인터를 갱신한다.
• ③ 오답: 연결 리스트는 특정 위치까지 순회할 수 있고 노드마다 link 필드가 필요하다.
• ④ 정답: 연속 저장과 링크 저장의 차이가 삽입 과정의 차이로 이어진다.

3. prev 뒤에 new를 삽입할 때 안전한 포인터 갱신 순서는?

① new.link = prev.link 후 prev.link = new ② prev.link = NULL 후 new.link = prev ③ free(prev) 후 prev.link = new ④ new.link = new 후 prev.link = NULL

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 새 노드가 기존 뒷부분을 먼저 보존한 뒤 앞부분과 연결하므로 연결 손실이 없다.
• ② 오답: 기존 뒷부분의 주소를 NULL로 덮고 새 노드를 이전 방향으로 연결한다.
• ③ 오답: 삽입에 필요한 이전 노드를 반환한 뒤 접근하므로 유효한 연산이 아니다.
• ④ 오답: 새 노드가 자신을 가리키고 앞부분의 링크까지 끊어 정상 리스트가 되지 않는다.

4. 12 → 28 → 41에서 12 뒤에 19를 삽입한 최종 순서는?

① 19 → 12 → 28 → 41 ② 12 → 28 → 19 → 41 ③ 12 → 19 → 28 → 41 ④ 12 → 19 → 41

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 새 노드를 머리에 삽입한 순서이며 12 뒤라는 조건을 반영하지 않았다.
• ② 오답: 28 뒤에 삽입한 결과로 이전 노드를 잘못 선택했다.
• ③ 정답: 19가 기존 다음 노드 28을 가리키고 12가 19를 가리키면 이 순서가 된다.
• ④ 오답: 기존 노드 28로 가는 연결을 보존하지 않아 뒷부분의 일부를 잃었다.

5. 중간 노드 삭제에서 free(del)을 우회 연결보다 먼저 실행하면 안 되는 이유는?

① 삭제 노드의 data 값이 자동으로 정렬되기 때문이다. ② head가 언제나 마지막 노드를 가리키게 되기 때문이다. ③ 이전 노드의 메모리까지 함께 반환되기 때문이다. ④ 반환한 노드의 link에서 다음 주소를 읽으려는 잘못된 접근이 생길 수 있기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 메모리 반환은 값 정렬과 관계없으며 삭제 순서의 위험을 설명하지 않는다.
• ② 오답: head는 첫 노드를 가리키며 free의 순서가 그 역할을 마지막 노드로 바꾸지 않는다.
• ③ 오답: free(del)은 지정한 삭제 노드의 할당을 반환하며 이전 노드를 자동 반환하지 않는다.
• ④ 정답: 다음 주소를 우회 연결에 사용해야 하므로 유효한 동안 먼저 읽어 연결을 완성해야 한다.

6. 12 → 19 → 28 → 41에서 28을 삭제할 때 수행할 핵심 연결은?

① 12의 link가 28을 가리키게 한다. ② 19의 link가 41을 가리키게 한다. ③ 28의 link가 19를 가리키게 한다. ④ head가 41을 가리키게 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 19를 건너뛰고 삭제 대상 28로 연결해 목표와 반대가 된다.
• ② 정답: 삭제 노드의 이전 노드 19가 삭제 노드의 다음 노드 41을 직접 가리켜야 한다.
• ③ 오답: 삭제할 노드의 링크를 앞쪽으로 돌려도 리스트에서 28로 들어오는 연결은 남는다.
• ④ 오답: 중간 노드 삭제에서 head를 바꾸면 앞의 12와 19가 리스트에서 빠진다.

7. 공백 리스트와 한 노드 리스트에서 마지막 노드를 삭제하는 처리를 옳게 구분한 것은?

① 공백이면 종료하고, 한 노드이면 그 노드를 반환한 뒤 head를 NULL로 만든다. ② 공백이면 head를 반환하고, 한 노드이면 head를 그대로 둔다. ③ 두 경우 모두 이전 노드를 끝까지 순회해 찾아야 한다. ④ 두 경우 모두 head.link만 NULL로 바꾸면 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 삭제 대상 유무와 삭제 후 공백 상태를 각각 정확히 반영한다.
• ② 오답: 공백에는 반환할 노드가 없고 한 노드 삭제 후 head를 유지하면 해제된 노드를 가리킨다.
• ③ 오답: 공백과 한 노드는 조건 검사만으로 판별할 수 있어 여러 노드용 순회가 필요 없다.
• ④ 오답: 공백에서는 head가 NULL이고, 한 노드에서는 노드 반환과 head 갱신이 필요하다.

8. 특정 값을 검색하면서 prev와 del을 전진시키는 올바른 순서는?

① del = del.link 후 prev = del.link ② free(del) 후 prev = del ③ prev = prev.link 후 del = prev ④ prev = del 후 del = del.link

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 현재 노드를 먼저 옮긴 뒤 이전 위치를 그 다음 노드로 잡아 두 포인터의 관계가 어긋난다.
• ② 오답: 검색 중인 노드를 반환하면 그 주소를 이전 노드로 저장하거나 계속 탐색할 수 없다.
• ③ 오답: del이 이전 노드와 같아져 현재·이전 노드의 역할이 분리되지 않는다.
• ④ 정답: 현재 노드를 이전으로 보존한 다음 현재를 다음 노드로 옮겨 인접 관계를 유지한다.

9. 공백 단순 연결 리스트의 상태를 나타내는 것은?

① head가 임의의 마지막 노드 주소를 가진다. ② 첫 노드의 data가 0이면 공백이다. ③ head가 NULL을 가리킨다. ④ 모든 노드의 link가 head를 가리킨다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 공백 리스트에는 첫 노드도 마지막 노드도 존재하지 않는다.
• ② 오답: 0도 저장 가능한 원소값이며 공백 여부는 data 값으로 판정하지 않는다.
• ③ 정답: 시작할 첫 노드가 없으므로 head의 주소값이 NULL인 상태다.
• ④ 오답: 공백에는 노드가 없고 단순 연결 리스트의 마지막 link는 NULL이다.

10. 연결 리스트의 삽입·삭제 코드를 검토하는 절차로 가장 적절한 것은?

① data 값의 크기순 정렬만 확인하고 포인터는 확인하지 않는다. ② 경계 상태를 구분하고 기존 뒷연결 보존, 링크 갱신, 도달성, 메모리 반환을 확인한다. ③ 먼저 모든 관련 노드를 반환한 뒤 필요한 주소를 읽는다. ④ 주소값을 오름차순으로 바꾸면 논리 순서도 자동으로 맞는다고 판단한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 리스트 순서는 값의 크기보다 링크 관계가 결정하므로 핵심 검사를 빠뜨린다.
• ② 정답: 연산 전제와 포인터 변화, 결과 리스트, 동적 메모리 처리를 모두 점검하는 흐름이다.
• ③ 오답: 메모리 반환 뒤 그 노드의 주소 정보를 읽는 것은 잘못된 순서다.
• ④ 오답: 물리 주소의 대소와 논리적인 앞뒤 순서는 독립적이다.

참고 자료와 작성 기준

이 글은 방송대 컴퓨터과학과 「자료구조」 5강 ‘연결 리스트’ 강의록을 바탕으로 포인터의 연결 변화와 경계 조건을 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 12·19·28·41을 사용한 삽입·삭제 추적은 강의 원리를 연습하도록 직접 구성한 예입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 방송대 컴퓨터과학과 「자료구조」 5강 ‘연결 리스트’ 강의록(2023년 제작 자료)
• 외부 보충 자료: 사용하지 않음
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-18