-
자료구조 - 5 | 연결 자료구조컴퓨터 공학/자료구조 2023. 1. 16. 14:42
연결 자료구조
자료들이 서로 1:1의 관계를 가지는 선형 자료구조에는 리스트, 스택, 큐, 데크 등의 여러 형태가 있다. 그중에서도 새로운 데이터를 삽입하거나 기존 데이터를 삭제하는데 별다른 제약이 없는 가장 기초적인 형태의 자료구조가 바로 리스트이다.
이러한 리스트는 순차 자료구조와 연결 자료구조로 분류할 수 있는데, 각각 순차 리스트와 연결 리스트로 부르기도 한다. 순차리스트는 보통 배열, 연결 리스트는 그냥 리스트라고 취급한다.
이전 포스트에서는 순차 자료구조에 대해 간단하게 알아보았다. 이번 포스트에서는 리스트를 만들 수 있는 또 다른 방식인 연결 자료구조에 대해 알아보고자 한다.
순차 자료구조의 문제점
기본적으로 연결 자료구조는 순차 자료구조의 문제점들을 개선한 구조를 가지고 있다. 따라서 순차 자료구조에 어떤 문제점이 있었는지를 다시 한번 간단하게 짚어보고자 한다.
다음의 순차 자료구조의 문제점을 간략하게 나타낸 것이다. 자세한 내용은 순차 자료구조 포스트를 참고하길 바란다.
- 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위한 추가 작업과 시간이 소요됨 (오버헤드 발생)
- 항목의 최대 개수 제한을 미리 설정해줘야 함 (능동적인 대처가 힘듦)
- 위의 이유로 최대 개수를 크게 하면 비어있는 공간이 많아져 메모리 효율이 낮아지고, 최대 개수를 작게 하면 데이터를 저장하지 못하는 상황이 발생할 수 있음 (배열의 메모리 사용 비효율성 문제)
따라서 이러한 문제를 개선하기 위한 새로운 자료 표현 방법이 필요한데, 연결 자료구조가 그 답이 될 수 있다.
연결 자료구조의 형태
연결 자료구조는 순차 자료구조와 달리 자료의 논리적인 순서와 물리적인 순서가 서로 불일치한다. 쉽게 말해 실제 메모리에 저장된 순서와 연결 자료구조에서 데이터를 저장하는 순서는 서로 아무 관계가 없다는 뜻이다. 즉, A데이터 다음에 B데이터를 추가하기 위해 메모리상에 A데이터가 저장된 다음 메모리 공간을 미리 비워둘 필요가 없다는 것이다.
따라서 미리 다음 메모리 공간을 확보해 두기 위해 항목의 최대 개수를 제한할 필요도 없고, 애초에 메모리 상으로는 각자 떨어진 서로 다른 곳에 값들이 위치하기 때문에 삽입, 삭제 연산으로 인해 연속적인 물리 주소를 유지하기 위한 추가 작업이 필요하지도 않다.
그렇다면 연결 자료구조는 어떤 방식으로 메모리상에 아무렇게나 떨어져 있는 데이터들을 모아서 하나의 순서를 가진 자료로 만들 수 있을까? 바로 각 데이터가 자신의 다음 데이터의 주소를 기억하는 방식으로 서로 연결되는 방식을 사용한다. 따라서 물리적으로는 서로 떨어져 있지만, 논리적으로는 연결되어 있다고 표현하는 것이다.
연결 리스트의 노드
위에서 설명한 연결 자료구조를 이용하여 리스트를 구현한다면 이는 연결 리스트라고 부를 수 있다. 이러한 연결 리스트는 연결하는 방식에 따라 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트, 이중 원형 연결 리스트 등 여러 형태로 표현할 수 있다.
중요한 것은 연결 리스트에서 연결 자료구조의 논리적인 연결이라는 개념을 구현하기 위해 노드라는 단위 구조를 사용한다는 것이다. 하나의 노드는 데이터 필드와 링크 필드로 나뉘는데, 데이터 필드는 실제 저장할 값을 저장하는 필드이고, 링크 필드는 자신 다음에 위치할 노드의 주소를 저장하는 필드이다. C언어를 기준으로 하자면 포인터를 사용하여 주소값을 저장하는 필드라고 볼 수 있다.
연결 리스트의 노드가 링크 필드에 의해 연결된 모습 이를 종합하여 순차 리스트와 연결 리스트의 차이를 살펴보면 다음과 같다.
순차 리스트는 메모리에 저장할 값을 그대로 저장한다. 단, 반드시 순서를 지켜서 메모리에 저장된 물리적인 순서와 리스트의 논리적인 순서가 같아야 한다. 이러한 이유로 계산을 통해 원하는 순서의 데이터가 저장된 메모리를 한 번에 찾을 수 있지만, 항상 물리적 순서와 논리적 순서를 맞추기 위해 추가 연산이 필요하다는 점과 전체 크기를 정해야 해서 메모리를 비효율적으로 사용해야 한다는 문제가 있다.
반면 연결 리스트는 메모리에 저장할 값을 노드의 형태로 저장한다. 각 노드에는 데이터 필드와 링크 필드가 있는데, 각각 실제 저장할 값과 다음 노드의 주소를 저장하고 있다. 이러한 노드는 메모리 상의 어느 위치에 저장되어도 큰 상관이 없기 때문에 순차 리스트의 단점을 해결할 수 있다.
단순 연결 리스트
단순 연결 리스트는 연결 자료구조를 이용하여 만들어 낼 수 있는 가장 단순한 형태의 연결 리스트이다. 이전에 설명했던 것과 동일하게, 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진다.
삽입 연산
단순 연결 리스트의 삽입 연산은 다음과 같은 순서로 진행된다.
- 삽입할 새로운 노드를 준비한다.
- 새로운 노드의 데이터 필드에 저장할 값을 저장한다.
- 삽입할 공간 앞 노드의 링크 필드를 복사해 새로운 노드의 링크 필드에 저장한다.
- 삽입할 공간 앞 노드의 링크 필드가 새로운 노드를 가리키도록 한다.
단순 연결 리스트의 삽입 연산 만약 가장 앞에 삽입하려 한다면, 해당 단순 연결 리스트 자체를 가리키는 리스트 포인터를 대상으로 해 삽입 연산을 실행한다. 리스트 포인터는 가장 첫 노드의 주소를 기억하고 있는데, 해당 주소를 새로 만든 노드의 링크 필드에 저장하고, 리스트 포인터에는 새로운 노드의 주소값으로 변경한다.
삭제 연산
단순 연결 리스트의 삭제 연산은 다음과 같은 순서로 진행된다.
- 해당 리스트가 비어있는지 확인한다. (비어있는 경우에는 오류 처리)
- 삭제할 노드의 앞 노드의 링크 필드를 임시로 저장한다. (삭제할 노드의 메모리주소를 저장)
- 삭제할 노드의 앞 노드의 링크 필드를 삭제할 노드의 링크 필드 값으로 변경한다.
- 임시로 저장된 삭제할 노드의 메모리 주소를 이용해 값을 반환하거나 메모리 공간을 비우는 작업을 진행한다.
단순 연결 리스트의 삭제 연산 만약 가장 앞의 노드를 삭제하려 한다면, 리스트 포인터를 대상으로 삭제 연산을 실행한다. 즉, 리스트 포인터의 값을 삭제할 노드의 링크 필드 값으로 변경한다.
단순 연결 리스트에서 가장 첫 노드 삭제 탐색 연산
단순 연결 리스트에서 원하는 값을 탐색하기 위한 탐색 연산은 다음과 같은 순서로 진행된다.
- 시작 노드 위치로 이동
- 해당 노드의 데이터 필드 값이 원하는 값과 같은지 비교
- 원하는 값과 같다면 해당 노드의 주소값을 반환
- 원하는 값과 다르다면 해당 노드의 링크 필드에 저장된 노드로 이동해 반복
- 끝까지 이동하였음에도 원하는 값을 찾지 못했다면 NULL을 반환
원형 연결 리스트
연결 자료구조를 이용한 연결 리스트의 경우 메모리의 물리적인 순서에 구애받지 않기 때문에 원형 연결 리스트라는 논리적으로만 가능한 구조를 만들 수도 있다. 원형 연결 리스트는 단순 연결 리스트에서 마지막 노드가 리스트의 가장 첫 노드를 가리키게 하여 리스트 구조를 원형으로 만든 리스트이다.
원형 연결 리스트 기존의 단순 연결 리스트에서는 항상 자신 다음의 노드로만 이동할 수 있었다. 노드의 링크 필드는 자신 다음의 노드만 가리키기 때문이다. 하지만 원형 연결 리스트의 경우 계속 순회하다 보면 다시 처음으로 돌아가기 때문에 이전 노드에도 접근이 가능하다.
삽입 연산
마지막 노드의 링크 필드를 첫 번째 노드로 연결시키는 것만 제외한다면, 원형 연결 리스트의 삽입 연산은 단순 연결 리스트의 삽입 연산과 동일하다.
- 삽입할 새로운 노드를 준비한다.
- 새로운 노드의 데이터 필드에 저장할 값을 저장한다.
- 삽입할 공간 앞 노드의 링크 필드를 복사해 새로운 노드의 링크 필드에 저장한다.
- 삽입할 공간 앞 노드의 링크 필드가 새로운 노드를 가리키도록 한다.
원형 연결 리스트의 삽입 연산 만약 공백 리스트에 처음 노드를 삽입하는 경우에는 리스트 포인터가 새로 생성한 노드를 가리키도록 하고, 새로 생성한 노드의 링크 필드는 자기 자신을 가리키도록 해야 한다.
공백 리스트에 노드 삽입 만약 노드를 원형 연결 리스트의 가장 처음으로 삽입하는 경우에는 리스트 포인터와 가장 마지막 노드의 링크 필드가 새로 생성한 노드를 가리키도록 하여야 한다. 이후 새로 생성한 노드의 링크 필드에는 리스트 포인터가 기존에 가리키던 첫 번째 노드의 주소를 넣는다.
- 삽입할 새로운 노드를 준비한다.
- 새로운 노드의 데이터 필드에 저장할 값을 저장한다.
- 리스트 포인터에 저장된 주소를 복사해 새로운 노드의 링크 필드에 저장한다.
- 리스트 포인터가 새로운 노드를 가리키도록 한다.
- 순회를 통해 가장 마지막 노드까지 이동한 다음, 마지막 노드의 링크 필드를 새로운 노드의 주소로 변경한다.
원형 연결 리스트 처음에 노드 삽입 삭제 연산
삭제 연산 역시 단순 연결 리스트의 삭제 연산과 동일하다.
- 해당 리스트가 비어있는지 확인한다. (비어있는 경우에는 오류 처리)
- 삭제할 노드의 앞 노드의 링크 필드를 임시로 저장한다. (삭제할 노드의 메모리주소를 저장)
- 삭제할 노드의 앞 노드의 링크 필드를 삭제할 노드의 링크 필드 값으로 변경한다.
- 임시로 저장된 삭제할 노드의 메모리 주소를 이용해 값을 반환하거나 메모리 공간을 비우는 작업을 진행한다.
원형 연결 리스트의 삭제 연산 가장 앞의 노드를 삭제하려 한다면, 리스트 포인터를 대상으로 삭제 연산을 실행한다. 즉, 리스트 포인터의 값을 삭제할 노드의 링크 필드 값으로 변경한다. 또한 가장 처음의 노드가 변경되었으므로, 가장 마지막 노드의 링크 필드 값 역시 새롭게 가장 첫 노드가 된 노드의 주소로 변경한다.
원형 연결 리스트에서 가장 앞 노드 삭제
이중 연결 리스트
이중 연결 리스트는 다음 차례의 노드로만 이동할 수 있었던 연결 리스트의 문제를 해결하기 위해 고안된 방식이다. 이중 연결 리스트에서 사용하는 노드는 두 개의 링크 필드를 가지는데, 각각 이전의 노드와 다음의 노드 주소를 저장한다. 따라서 이전의 노드로는 이동할 수 없었던 기존의 연결 리스트의 문제를 해결할 수 있다.
이중 연결 리스트 llink(left link)와 rlink(right link)는 각각 이전 노드와 다음 노드의 주소를 저장하는 필드이고, 리스트 포인터는 이중 연결 리스트의 가장 첫 노드를 가리킨다. (해당 리스트에 접근 시 사용)
삽입 연산
이중 연결 리스트는 양쪽의 노드 주소를 동시에 기억해야 하기 때문에 삽입 연산이 기존의 단순 연결 리스트에 비해 다소 복잡할 수 있다. 하지만 크게 어려울 것은 없으니 아래의 순서대로 진행하기만 하면 된다.
- 삽입할 새로운 노드를 준비한다.
- 새로운 노드의 데이터 필드에 저장할 값을 저장한다.
- 삽입할 공간 이전 노드를 기억하여 다음의 작업을 진행한다.
- 삽입할 공간 이전 노드의 오른쪽 링크 필드를 복사해 새로운 노드의 오른쪽 링크 필드에 저장한다.
- 삽입할 공간 이전 노드의 오른쪽 링크 필드에 새로운 노드의 주소를 저장한다.
- 삽입할 공간 다음 노드를 기억하여 다음의 작업을 진행한다.
- 삽입할 공간 다음 노드의 왼쪽 링크 필드를 복사해 새로운 노드의 왼쪽 링크 필드에 저장한다.
- 삽입할 공간 다음 노드의 왼쪽 링크 필드에 새로운 노드의 주소를 저장한다.
이중 연결 리스트의 삽입 연산 만약 가장 앞에 노드를 삽입하는 경우에는 삽입할 공간 이전 노드가 없으므로, 기존의 3번 작업을 리스트 포인터를 대상으로 하여 다음과 같이 진행한다.
- 리스트 포인터에 저장된 주소값을 복사해 새로운 노드의 오른쪽 링크 필드에 저장한다.
- 리스트 포인터에 새로운 노드의 주소를 저장한다.
이중 연결 리스트 가장 앞에 노드 삽입 만약 마지막에 노드를 삽입하는 경우에는 삽입할 공간 다음 노드가 없으므로, 기존의 4번 작업을 진행하지 않는다. 대신 새로운 노드의 왼쪽 링크 필드에 삽입할 공간 이전 노드의 주소를 저장한다.
이중 연결 리스트 마지막에 노드 삽입 삭제 연산
이중 연결 리스트의 삭제 연산은 다음과 같다.
- 해당 리스트가 비어있는지 확인한다. (비어있는 경우에는 오류 처리)
- 삭제할 노드의 메모리 주소를 임시로 저장한다.
- 삭제할 노드의 오른쪽 링크 필드 값을 복사해 삭제할 노드의 왼쪽 노드의 오른쪽 링크 필드에 저장한다.
- 삭제할 노드의 왼쪽 노드의 링크 필드 값을 복사해 삭제할 노드의 오른쪽 노드의 왼쪽 링크 필드에 저장한다.
- 임시로 저장된 삭제할 노드의 메모리 주소를 이용해 값을 반환하거나 메모리 공간을 비우는 작업을 진행한다.
이중 연결 리스트의 삭제 연산 만약 가장 앞의 노드를 삭제하는 경우에는 삭제할 노드의 왼쪽 노드가 없으므로, 기존의 3번 작업을 진행하지 않는다. 대신 삭제할 노드의 오른쪽 링크 필드 값을 복사해 리스트 포인터에 저장한다.
이중 연결 리스트의 가장 앞 노드 삭제 만약 마지막 노드를 삭제하는 경우에는 삭제할 노드의 오른쪽 노드가 없으므로, 기존의 4번 작업을 진행하지 않는다.
이중 연결 리스트의 마지막 노드 삭제