다중 연결 리스트 (Multi Linked List)

다중 연결 리스트 (Multi Linked List)

각 노드가 두 개 이상의 링크를 가지며, 데이터를 여러 방식으로 연결하여 다양한 순회 경로를 제공하는 복합 연결 구조

목적: 다중 순서 유지, 다차원 데이터 표현, 복합 관계 모델링

특징: 다중 포인터, 여러 순회 경로, 복합 구조

종류

• •희소 행렬 표현: 각 노드가 행·열 링크를 가짐, 십자 연결 리스트
• •다단계 리스트: 레벨별 링크, Skip List의 기반
• •다중 속성 정렬: 이름순·나이순 등 여러 기준으로 연결

희소 행렬 예시

• •노드 = [row | col | value | right | down]
• •행별 연결 리스트 + 열별 연결 리스트
• •장점: 0이 아닌 원소만 저장, 메모리 효율

일반화된 리스트 (Generalized List)

• •원소가 원자(atom) 또는 리스트(sublist)
• •재귀적 구조, 복잡한 데이터 표현
• •LISP의 기본 자료구조

장점: 유연한 데이터 표현, 다중 관점 순회, 복잡한 관계 모델링

단점: 구현 복잡도, 메모리 오버헤드, 유지보수 어려움

적용사례: 희소 행렬, 다중 인덱스 데이터베이스, 그래프 표현

비교: 다중(복합/다경로) vs 이중(양방향/단경로) vs 단순(단방향)

연관: 희소 행렬, Skip List, 일반화된 리스트, 그래프