List 자료구조
📝 List 자료구조 목차
- List 자료구조의 이해
- 배열기반 리스트: Array List | 소스 코드
- 연결 리스트: Linked List | 소스 코드
- 원형 연결 리스트: Circular Linked List | 소스 코드
- 양방향 연결 리스트: Double Linked List | 소스 코드
리스트 자료구조의 이해
먼저 리스트에 대한 대표적인 오해를 짚을 필요가 있다.
"List는 연결 리스트를 의미한다." (X)
List는 반드시 연결 리스트만을 뜻하지는 않는다. 배열을 기반으로 한 리스트도 리스트의 한 종류에 속한다.
- 순차 리스트: 배열을 기반으로 구현된 리스트
- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트
리스트 자료구조의 공통된 특성
순차 리스트와 연결 리스트는 구현 방법에 따라 구분된다.이 둘의 ADT는 동일 할 수도 있고 상황에 따라 다를 수도 있다.하지만 이 두 리스트 자료구조의 가장 기본적이고도 중요한 특성은 다음과 같다.
- 리스트 자료구조는 데이터를 나란히 저장한다.
- 리스트 자료구조는 중복된 데이터의 저장을 막지 않는다.
리스트 자료구조의 추상자료형(ADT)
데이터가 나란히 저장된다는 특성을 기반으로 제공해야 할 기능은 다음과 같다.
// 초기화할 리스트의 주소 값을 인자로 전달
// 리스트 생성 후 제일 먼저 호출되어야 하는 함수
void ListInit(List* plist);
// 리스트에 데이터를 저장. 매개변수 data에 전달된 값을 저장.
void LInsert(List* plist, LData data);
// 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
// 데이터의 참조를 위한 초기화가 진행된다.
// 참조 성공시 TRUE(1), 실패시 FALSE(0)반환
int LFirst(List* plist, LData* pdata);
// 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
// 순차적인 참조를 위해서 반복 호출이 가능하다.
// 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
// 참조 성공시 TRUE(1), 실패시 FALSE(0) 반환
int LNext(List* plist, LData* pdata);
// LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
// 삭제된 데이터는 반환된다.
// 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
LData LRemove(List* plist);
// 리스트에 저장되어 있는 데이터의 수를 반환한다.
int LCount(List* plist);리스트의 ADT를 사용하는 main 함수 예시
- 리스트의 생성 및 초기화
- 사용자는
List타입의 list 자료구조를 만들 수 있다. - 사용자는
ListInit()함수를 통해서 리스트를 초기화 할 수 있다.
List list; //리스트 선언
...
ListInit(&list); //리스트 초기화- 리스트에 데이터 삽입
- 사용자는
LInsert()함수를 통해서 리스트에 데이터를 삽입할 수 있다.
for (i = 0; i < 10; i++)
LInsert(&list, i); //리스트 삽입- 리스트에서 데이터 탐색
- 사용자는
LFirst()함수를 통해서 리스트의 첫 번째 데이터에 접근 할 수 있다. - 사용자는
LNext()함수를 통해서 리스트의 두 번째 이후의 데이터에 접근 할 수 있다. - 이것이 가능 한 이유는 리스트 내에서 '데이터의 참조위치'를 기록하고 있기 때문이다.
// 리스트에 있는 모든 데이터 출력
if (LFirst(&list, &data)) // 첫 번째 데이터를 변수 data에 저장
{
printf("%d ", data);
while (LNext(&list, &data)) // 두 번째 이후의 데이터를 변수 data에 저장
printf("%d ", data);
}
printf("\n\n");- 리스트에서 데이터 삭제
- 사용자는
LRemove()함수를 통해서 현재 위치의 데이터를 삭제할 수 있다.
// 2의 배수, 3의 배수 삭제
if (LFirst(&list, &data))
{
if ((data % 2 == 0) || (data % 3 == 0))
LRemove(&list);
while (LNext(&list, &data))
{
if ((data % 2 == 0) || (data % 3 == 0))
LRemove(&list);
}
}main()함수에서 사용자가List를 어떻게 사용할 수 있는지 몇 가지 상황을 살펴보자.- 리스트 자료구조의 ADT
- 리스트라는 자료구조는 구현 방법에 따라서 다음의 두가지로 나뉜다.
즉, 리스트라고 해서 반드시 연결 리스트를 의미하는 것은 아니다. - 먼저 리스트에 대한 대표적인 오해를 짚을 필요가 있다.
