연결 리스트를 잘 모른다면 필자가 포스팅한 내용을 보고 온다면 이해하기 편하다.
<연결 리스트 포스팅 링크>
원형 연결 리스트란?(What is Circular linked list?)
원형 연결 리스트(circular linked list)는 단순 연결 리스트의 단점을 보완한 리스트이다. 단순 연결 리스트는 한 방향으로 움직이면서 그 끝이 정해져 있기 때문에 리스트를 검색할 때 항상 리스트의 처음부터 접근해야하는 단점이 있다. 또한 리스트가 순환을 요구한다면 더더욱 불리하다. 이를 해결하기 위해 단순 연결리스트의 마지막 노드가 리스트의 처음 노드를 가리키도록 만든 것이 원형 연결 리스트이다. 원형 연결 리스트는 다음과 같은 형태를 가진다.
원형 연결 리스트는 다음과 같은 기본연산을 가지고 있다.
- 리스트 생성
- 노드 삽입
- 노드 삭제
지금부터 설명할 리스트에 대한 기본 연산은 기본적인 개념은 같지만 세세한 부분에서는 필자가 구현하는 코드에 맞추어 설명하기 때문에 이 점 유의하면서 보기 바란다.
리스트 생성
리스트 생성은 1개의 노드를 가지도록 생성해 준다. 이때 생성된 노드의 링크 필드는 자기 자신을 가리킨다.리스트 생성 함수가 반환하는 값은 리스트를 가리키는 포인터이다. 앞으로 이 포스팅에서 리스트를 가리키는 포인터를 리스트 포인터라고 부르겠다.
노드 삽입
노드 삽입은 3가지 방법으로 나누어 설명하겠다.
리스트의 첫번째 자리에 삽입
먼저 새로운 노드를 생성해 준다. 다음, 새로운 노드의 링크필드가 삽입하기 이전 첫번째 노드를 가리키도록 한다. 그리고 삽입한 노드가 첫번째 노드가 될 수 있도록 리스트 포인터가 새로운 노드를 가리키게 한다. 이후 마지막 노드의 링크 필드가 삽입된 노드를 가리킬 수 있도록 해준다. 마지막 노드를 찾는 방법은 처음부터 찾는 방법도 있고 따로 저장하는 방법이 있다. 리스트의 단점은 탐색에 있기 때문에 필자는 후자의 방법을 택했다.
리스트의 마지막 자리에 삽입
마지막 자리의 노드 삽입은 위와 같은 과정을 갖는다. 먼저 새로운 노드를 생성하고 리스트의 마지막 노드의 링크 필드가 새로운 노드를 가리킬 수 있도록 해준다. 그리고 새로운 노드의 링크 필드가 리스트의 처음 노드를 가리키도록 해준다. 필자의 경우 마지막 노드를 따로 저장하기 때문에 마지막 노드를 변경하는 과정도 같이 해준다.
리스트 중간 자리에 삽입
리스트의 중간 자리 삽입은 기존 단순 연결 리스트와 같다. 새로운 노드를 생성한 뒤, 새로운 노드의 링크 필드가 삽입되는 위치 이후의 노드를 가리키고 삽입되는 위치 이전 노드의 링크 필드가 새로운 노드를 가리키게 한다.
노드 삭제
노드의 삭제는 삭제하는 노드에 따라 2가지 방식으로 나눈다. 노드의 첫번째를 삭제하는 경우, 리스트 포인터가 삭제되는 노드의 다음 노드를 가리키게 한다. 그리고 삭제되는 노드의 이전 노드의 링크 필드가 삭제되는 노드의 다음 노드를 가리키게 한다. 그리고 노드를 메모리에서 삭제한다. 중간 노드를 삭제하는 과정은 첫번째 노드 삭제과정중 첫번째 과정만 제외하면 된다.
원형 연결 리스트 구현
구현은 아래 필자의 깃허브에 있으니 참고하길 바란다. 기본적인 원리만 구현을 했기 때문에 실제 사용에는 무리가 있다.참고만 하길 바란다.
GitHub - LimeTree0/Data-Structure
Contribute to LimeTree0/Data-Structure development by creating an account on GitHub.
github.com
'자료구조' 카테고리의 다른 글
| 트리(Tree) (0) | 2022.03.01 |
|---|---|
| 이중 연결 리스트(Doubly Linked List) (0) | 2022.02.25 |
| 단순 연결 리스트(Singly Linked List) (0) | 2022.02.25 |
| 큐(Queue) (0) | 2022.02.25 |
| 스택(Stack) (0) | 2022.02.25 |