이번 시간에는 리스트 ADT를 확장해서 그룹과 공유라는 개념을 알아봅시다. 이 개념이 다른책에는 없고 제가 듣는 강의에서만 나오는거 같은데.....그래서 간단하게 정리하는 식으로 쓰게 되었네요 ㅋㅋ
우선 그룹의 개념부터 살펴보자면
데이터 원소들이 각각 다른 그룹에 속한다는 뜻으로 받아들일 수 있습니다.
예를 들면
쇼핑몰의 상품들
1. Maker X : x1
2. Maker Y : none
3. Maker Z : z1, z2
대학의 강좌들
1. Prof. Kook : DS
2. Prof. Park : (no lecture)
3. Prof. Shin : DB, C lang
이러한 예를 들 수 있습니다.
이런 그룹의 설계 방안을 살펴보자
A. 레코드의 리스트 사용 :
1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현
B. 부리스트들의 리스트 사용
1. 2D배열을 이용한 구현
2. 연결리스트의 배열을 이용한 구현
이러한 구현 방안들이 있습니다.
먼저 설계방안 A부터 살펴보면,
1. 그룹을 표현하기 위해서 elem 및 group 필드로 구성된 레코드의 리스트를 사용한다는 것입니다.
2. 장점으로 "단순"하다는 것이 있고
3. 단점으로는 특정그룹에 대한 작업을 위해서는 전체 레코드를 순회해야만 한다.
설계방안 A를 배열로 구현하려면
리스트를 elem 및 group 필드로 구성된 레코드의 1D 배열을 이용해 구현할 수 있습니다.
장점으로는 기억장소 낭비가 없다는 것입니다.
연결 리스트로 구현하려면
리스트를 elem 및 group 필드로 구성된 레코드 노드의 "이중 연결 리스트"를 이용해 구현할 수 있습니다.
장점으로는 기억장소 사용을 최소화할 수 있다는 것입니다.
이제 설계방안 B를 살펴보자면
1. 그룹을 표현하기 위해서 그룹의 리스트를 사용하고 각 그룹은 다시 원소들의 부리 스트로 구성됩니다.
2. 장점으로는 특정그룹 관련 작업을 격리 처리할 수 있습니다.
이 설계방안 B를 2D배열로 구현하면 기억 장소 낭비의 우려가 생길 수도 있습니다.
그리고 연결리스트의 배열로 구현하게 되면 이런 기억 장소 사용을 최소화할 수 있습니다.
여기까지 리스트를 통한 그룹의 개념을 알아보았습니다.
그러면 리스트의 공유란 무엇일까요?
데이터원소들이 다른 그룹들에 의해서 공유될 때를 말합니다.
그리고 각 그룹에게 공유되는 데이터 원소를 복제하는 것은 낭비이므로 허용하지 않습니다.
이러한 공유의 설계방안은 크게 3가지가 있습니다.
A. 레코드의 리스트 사용
1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현
B. 포인터의 리스트 사용
1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현
C. 다중리스트 사용
1. 2D 배열 사용
2. 다중 연결리스트를 이용한 구현
이렇게 여러가지의 구현 방법이 있습니다.
좀 더 자세히 살펴봅시다.
A. 레코드의 리스트 사용
앞서 그룹화에서의 방안과 동일하다.
B. 포인터의 리스트 사용
원소들을 별도의 메모리에 저장하고, 이들에 대한 참조를 포인터로 수행한다.
장점 : 단순, 기억장소 사용을 최소화
단점 : 특정 원소 관련 작업의 격리 처리 불가(한 그룹에 속한 원소에 대한 작업을 처리할 때, 해당 원소가 다른 그룹에도 속하지는 않는지 점검이 불가)
두 가지 구현 : 배열을 이용한 구현, 연결리스트를 이용한 구현
C. 다중리스트 사용
2D 배열 사용
다중 연결리스트를 이용한 구현
원소들의 리스트와 그룹들의 리스트가 상호 교차하는 형태의 다중 리스트를 사용하는 방법.
장점 : 특정 원소 및 특정 그룹에 관련한 작업을 격리 처리할 수 있음.
구현 방법 1
행과 열이 각각 원소와 그룹을 나타내는 2차원 부울(boolean) 배열을 이용하여 교차점을 저장.
단점 : 약간의 기억장소 낭비가 발생하지만 효율적이다.
구현 방법 2 -> 초기화, 원소 순회, 그룹 순회, 삽입, 삭제
두 개의 배열을 이용하여 원소 및 그룹의 리스트를 각각 구현하고, 상호 교차하는 원형 헤더 연결 리스트를 이용하여 (원소, 그룹) 쌍의 부리스트들을 구현한다. 기억장소 낭비를 최소화할 수 있다.
