연결리스트

양규빈·2024년 1월 26일

자료구조

목록 보기

4/6

연결리스트란?

연결리스트는 데이터 요소가 순서대로 연결된 자료구조입니다.
각 데이터 요소를 노드라고 부르며, 노드는 데이터 필드와 다음 노드를 가리키는 링크로 구성됩니다.

이때, 링크가 하나인지, 혹은 두 개인지에 따라서 단일 연결리스트, 혹은 이중 연결리스트로 나뉩니다.

만약 마지막 노드가 첫 번째 노드를 가리키고 있다면, 순환구조를 이루기 때문에 원형 연결리스트가 됩니다.
원형 연결리스트는 단일 연결리스트로 만드는 것도 이중 연결리스트로 만드는 것도 모두 가능합니다.

연결리스트는 배열과 달리 메모리에 연속적으로 저장되지 않습니다. 각 노드가 다음 노드의 주소를 가리키기 때문에 메모리에 흩어져서 데이터를 저장하는 것도 가능합니다.

이러한 연결리스트는
스택 및 큐의 구현에 사용되거나 파일 시스템, 페이지 교체 알고리즘인 LRU 등에 사용됩니다.

단일 연결리스트

연결리스트의 구조를 그림으로 표현하면 다음과 같습니다.
{10, 20, 30, 40} 각각의 노드는 다음 노드를 가리키고 있습니다.

이러한 노드를 코드로 표현하면 다음과 같습니다.
구조체 형태로 구현된 Node에는 Node를 저장하는 포인터 변수와 int를 저장하는 값 변수를 가지고 있습니다.

단순하게 구현된 노드를 이용하여 생성하고 연결하는 코드는 위와 같습니다.
next 변수에 생성한 노드를 연결하면, 다음 노드를 정상적으로 가리키게 할 수 있습니다.

이러한 단일 연결리스트는 스택 자료구조의 구현에 이용됩니다.

단일 연결리스트의 삽입

연결리스트의 삽입에는 두가지 방법이 있습니다.
연결리스트의 중간에 삽입하는 방법과 마지막에 삽입하는 방법.

리스트의 마지막에 삽입

단일 연결리스트의 마지막 노드 포인터는 항상 nullptr을 가리키고 있습니다.
그렇기 때문에, 마지막 노드에 삽입하는 방법은 비교적 쉽습니다.

기존의 마지막 노드를 찾아서,
해당 노드의 next 변수에 새로 만든 노드를 가리키게 하는 것입니다.

아래는 이를 코드로 구현한 것입니다.

current 노드의 next가 nullptr을 가리킬 때까지 반복하여, 탐색을 이어갑니다.
마지막을 찾았다면, current의 next 변수를 새로운 노드(newNode)로 설정해줍니다.

리스트의 중간에 삽입

단일 연결리스트의 중간 삽입입니다.
제시된 순서 번째 노드에 도달할 때까지 탐색을 이어갑니다.

노드를 찾았다면, 먼저. 새로운 노드의 next 변수(노드 포인터)에 기존 노드의 next 변수값을 초기화 해줍니다.

이후에, 기존 노드의 next 변수를 새로운 노드 자신을 가리키도록 해줍니다.

이 변수 설정 순서를 틀려서는 안 됩니다.
연결이 끊어질 수 있기 때문입니다.
연결리스트의 연결이 끊어지면, 더이상 접근할 수 없기 때문에 그대로 쓰레기 값이 되어 불필요한 메모리를 차지하게 됩니다.

위 코드는 단일 연결리스트의 중간 삽입을 구현한 함수입니다.
앞서 설명한 바와 같이, 위치 인덱스 값인 pos에 도달할 때까지 currentPos를 이용하여 탐색을 이어가고,

새노드->포인터 = 현재노드->포인터
현재노드->포인터 = 새노드

순서로 연결리스트가 끊어지지 않게 코드를 작성했습니다.

단일 연결리스트 삭제

단일 연결리스트의 노드 삭제 시에도 연결리스트가 끊어지지 않도록 순서에 주의해야 합니다.

리스트의 마지막 삭제

마지막 노드의 삭제는 간단합니다.
연결리스트의 탐색을 이어가, 마지막 노드를 찾고. 해당 노드를 제거한 후에,
이전 노드의 next 변수를 null값으로 재설정 해줍니다.

다만 삽입과 다르게 주의해야할 점이 있다면,
삭제는 연결리스트가 비어있을 수도, 혹은 노드가 하나 뿐일 수도 있다는 것입니다.

이러한 상황을 고려하여 안전하게 코드를 작성해야 합니다.

head가 nullptr일 경우에는 연결리스트가 null이므로 적절하게 예외처리해줍니다.

만약 head의 next가 null을 가리킬 경우에는 head 노드 하나 뿐이기 때문에, head를 제거하고 null처리 해줍니다.

위 조건을 모두 만족했다면,
연결리스트의 노드가 널인 것도, 1개인 것도 아니므로 탐색을 시작합니다.

마지막 노드를 찾았다면,
prev(마지막의 전 노드)와 current(마지막 노드)의 처리를 해줍니다.

마지막 노드를 delete하여 제거하고,
마지막 이전 노드의 next를 null로 재설정 해줍니다.

리스트의 중간 삭제

단일 연결리스트의 중간 노드 삭제도 비교적 단순하지만,
삭제 노드의 이전 노드의 next 변수(노드 포인터)가 삭제 노드의 next(삭제노드의 다음 노드)를 가리킬 수 있도록 해주는 것을 신경써야 합니다.

만약, 이전 노드의 next를 수정하지 않고 삭제노드를 먼저 제거한다면,
연결리스트가 끊어져서 메모리 누수가 일어나게 됩니다.

연결리스트가 널인지, 혹은 한 개의 노드를 가지고 있는지 체크한 후에.

마찬가지로 순서 인덱스 변수인 pos의 값과 대조하여 중간 순서의 노드를 찾아냅니다.
prev 노드와 current 노드를 찾았다면, prev노드의 next 변수를 삭제 노드의 다음 노드로 설정해줍니다.

그리고 삭제노드를 delete로 제거합니다.

이중 연결리스트

이중 연결리스트는 단일 연결리스트에 한 개의 포인터 변수를 더 추가한 자료구조입니다.
현재 노드의 다음 노드를 가리키는 next.
현재 노드의 이전 노드를 가리키는 prev.

즉, 이중 연결리스트는 각 노드에 두 개의 링크를 유지해서 더 효율적인 탐색을 할 수 있도록 하는 자료구조입니다.

위 그림과 같이, 각 노드의 링크에는 이전 노드와 다음 노드를 가리키고 있습니다.
이를 코드로 구현하면 다음과 같습니다.

위 노드를 단순하게 생성하고 링크를 연결하면 아래와 같습니다.

head와 tail 노드.
그리고 몸통이 되는 노드가, 서로 연결되어 있는 것을 확인할 수 있습니다.

이러한 이중 연결리스트는 큐의 구현에 사용될 수 있습니다.

이중 연결리스트의 삽입

이중 연결리스트의 삽입은 링크가 두 개로 늘어났기 때문에 앞뒤 노드의 연결이 끊어지지 않도록 더 신경써야 합니다.

리스트의 마지막 삽입

이중 연결리스트의 마지막 노드에 새로운 노드를 삽입하는 과정은 다음과 같습니다.
null을 가리키는 노드(마지막)을 찾습니다.
찾은 노드(마지막 노드)의 next 변수에 새로 삽입하는 노드를 설정합니다.
삽입 노드의 prev 변수에 기존의 마지막 노드를 설정합니다.

이를 코드로 나타내면 다음과 같습니다.

리스트의 중간 삽입

이중 연결리스트의 중간 삽입과정은 다음과 같습니다.
1. 삽입 지점에 위치한 노드(current)를 가져온다.
2. 삽입 노드의 next를 current의 next로 설정한다.
즉, 이전 노드의 next를 그대로 이식하는 것입니다.
3. 이전 노드의 next가 null이 아니라면, 해당 노드의 prev를 삽입 노드로 설정한다.
4. 삽입 노드의 prev를 current(find한 노드)로 설정한다.
5. current 노드의 next를 삽입 노드로 설정한다.

이렇게 함으로써 이전노드(current) - 삽입노드 - 다음노드(current-next) 간의 이중 연결을 완성합니다.