5. 리스트의 그룹과 공유

그룹화^Grouping

데이터 원소들은 각각 상이한 그룹에 속하며, 각 그룹의 크기는 다양하다. 예를들어, 한 쇼핑몰에서 파는 제품들을 채소, 전자제품, 육류 등의 카테고리에 따라 그룹화할 수 있으며, 각 카테고리에 속한 제품의 수가 상이할 수 있다.

레코드의 리스트 사용

1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현

그룹을 표현하기 위해, elem 및 group 필드로 구성된 레코드의 리스트를 사용할 수 있다. 단순하다는 장점이 있지만, 특정 그룹에 관한 작업을 위해서는 전체 레코드를 순회해야 하는 단점이 있다.

부리스트^sublist들의 리스트 사용

1. 2D 배열을 이용한 구현
2. 연결리스트의 배열을 이용한 구현

그룹을 표현하기 위해, 그룹의 리스트를 만들고, 각 그룹의 리스트에 그룹에 속하는 원소를 넣는 방법이다. 특정 그룹에 관련된 작업을 빠르게 처리할 수 있는 장점이 있다.

2D 배열을 이용하면 비교적 쉽게 구현 가능하지만, 열의 크기가 최대 그룹의 크기를 따르기에 저장공간이 낭비되는 문제가 있다.

연결리스트의 배열을 만들어 기억장소 사용을 최소화하면서도 효율적인 구현이 가능하다. 이때, 헤드 노드와 테일 노드의 위치를 저장하는 1D 배열을 두개 만들어 사용하면 된다.

공유 ^share

데이터 원소들이 상이한 그룹에 의해 공유되는 것. 이때, 각 관련 그룹에 공유 데이터 원소를 복제하는 것은 시간과 저장공간이 낭비되므로 허용하지 않는다.

예를들어, 대학생 A, B가 공통된 과목을 듣는 경우, 그룹 A, B에서 해당 과목의 원소가 공유되는 것이다.

레코드의 리스트 사용

앞서 그룹화에서의 방안과 동일하다.

포인터의 리스트 사용

1. 배열을 이용한 구현
2. 연결리스트를 이용한 구현

원소들을 별도의 메모리에 저장하고, 이들에 대한 참조를 포인터로 수행한다. 단순하고 기억장소 사용을 최소화할 수 있지만, 특정 원소 관련작업의 격리 처리가 불가한 단점이 있다. (한 그룹에 속한 원소에 대한 작업을 처리할 때, 해당 원소가 다른 그룹에도 속하지는 않는지 점검이 불가)

다중리스트 사용

1. 2D 배열 사용
2. 다중 연결리스트를 이용한 구현

원소들의 리스트와 그룹들의 리스트가 상호 교차하는 형태의 다중리스트를 사용하는 방법. 원소와 그룹의 상호 관계를 갖는 교차점 서브리스트가 있어, 특정 원소 및 특정 그룹에 관련한 작업을 처리할 수 있음.

• 구현 방법 1
  행과 열이 각각 원소와 그룹을 나타내는 2차원 부울(boolean) 배열을 이용하여 교차점을 저장.
  약간의 기억장소 낭비가 발생하지만 효율적이다.
• 구현 방법 2
  두 개의 배열을 이용하여 원소 및 그룹의 리스트를 각각 구현하고, 상호 교차하는 원형 헤더 연결리스트를 이용하여 (원소, 그룹) 쌍의 부리스트들을 구현한다. 기억장소 낭비를 최소화할 수 있다.