[데이터구조] 원형연결리스트

[데이터구조] 원형연결리스트

데이터구조 조교로써 채점을 하려는데, 채점에 앞서 내가 사전적으로 다시 공부를 해야했다.

알아야 하는 개념은 연결할당시스템 and 원형연결리스트 and 가용공간 리스트

원형연결리스트

# 원형 연결리스트란

선형리스트가 아닌 원형리스트.

사진에서는 단순연결리스트처럼 맨 앞 노드를 가리키게 한 예다.

리스트의 마지막 노드가 링크의 첫번째 노드를 가리키게 되어 순환적인 형태를 띤다.

다음과 같은 특징이 있다.

한 노드에서 다른 모든 노드로의 접근이 가능

노듭의 삽입/삭제 진행시 선행 노드의 포인터가 필요

그리고, 위의 사진을 기준으로 보면 삽입/삭제시 다음과 같은 문제가 일어난다

head가 맨 앞 노드를 가리키고 있다. 삽입시 맨 앞 노드 앞에 삽입해야한다. 맨 뒤 노드까지 탐색해야 한다 => 비효율적이다.

# 개선된 원형 연결리스트

기존 원형 연결리스트에서 head의 위치가 마지막 노드를 가리키도록 바꼈다. 이것이 일반적인 원형 연결리스트 형태이며, 다음과 같은 연결구조를 가진다.

마지막 노드는 헤드 포인터의 head가 가리킴

첫번째 노드는 head의 link가 가리킴

이를 통해, 기존의 노드 삽입/삭제 방법을 보다 편이하게 할 수 있게된다.

## 예시를 통한 노드 삽입/삭제 이해

얘를 봐보자.

기억하자, 이곳은 순환되는 공간이며 표시된 맨 앞의 '10' 이라는 공간은 head의 link로 가리키고 있다.

앞부분 삽입을 한다면

[node의 link] 를 [head의 link] 로 가리키게 함

[head의 link] 를 [ node ]로 가리키게 함

뒷부분 삽입을 한다면

[node의 link] 를 [head의 link] 로 가리키게 함 (앞부분 삽입과 동일) [head의 link] 를 [ node ]로 가리키게 함 (앞부분 삽입과 동일) [head]를 [node]가 되게 함

코드상으로 보아도, head= node; 라는 코드만 추가가 된다.

// 앞에서 할당시키기 ListNode* first(ListNode* head, element data) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); node->data = data; if (head == NULL) { head = node; node->link = head; } else { node->link = head->link; head->link = node; } return head; } // 뒤에서 할당시키기 ListNode* last(ListNode* head, element data) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); node->data = data; if (head == NULL) { head = node ; node->link = head; } else { node->link = head->link; head->link = node; head = node; } return head; }

다음은 가용공간리스트에 대해서 포스팅하기

from http://guti-coding.tistory.com/63 by ccl(A) rewrite - 2021-10-14 20:00:42