[리스트] 리스트의 이해와 종류

[리스트] 리스트의 이해와 종류

리스트 자료구조

- 데이터를 나란히 저장하며 중복된 데이터의 저장이 가능한 자료구조

- 스택, 큐, 덱과 같은 선형 자료구조

- 구현 방법에 따라 배열 리스트와 연결 리스트로 나뉨

리스트 자료구조의 종류

- Array List : 배열을 기반으로 구현한 리스트

- Linked List : 메모리 동적 할당을 기반으로 구현한 리스트

Linked List는 다른 노드를 가리키는 포인터 사용에 따라 종류가 세분화된다.

리스트 자료구조의 ADT

ADT는 배열 기반인지 연결 기반인지에 상관없이 리스트의 특성에 따라 정의되어야 한다. 

필요에 따라 추가 되거나 삭제될 수 있다.

void ListInit(List *plist);
// 초기화할 리스트의 주소 값을 인자로 전달
// 리스트 생성 후 제일 먼저 호출 되어야 한다.
// C++, Java의 경우 생성자를 이용, 인스턴스 생성시 자동으로 초기화되도록 사용할 수 있다.
 
void LInsert(List *plist, LData data);
// 리스트에 데이터를 저장
// 매개변수 data에 전달된 값을 리스트에 저장
 
int LFirst(List *plist, LData *pdata);
// 첫 번째 데이터를 pdata에 저장한다.
// 데이터 참조를 위한 초기화
// 성공시 TRUE(1), 실패시 FALSE(0) 반환
 
int LNext(List *plist, LData *pdata);
// 현재 참조된 데이터의 다음데이터를 pdata에 저장한다.
// 순차적인 참조를 위해 반복 호출이 가능
// LFirst 함수 호출을 통해 초기화를 한 후 사용
// 성공시 TRUE(1), 실패시 FALSE(0) 반환
 
LData LRemove(List *plist);
// 현재 참조 위치의 데이터를 삭제한다.
// 삭제된 데이터는 확인을 위해 반환한다.
 
int LCount(List *plist);
// 리스트에 저장되어 있는 데이터의 수를 반환

ADT는 절대적인 것이 아니다. 함수 이름, 매개변수, 기능 등 모두 구현자의 목적에 따라 변할 수 있다.

정리

리스트에 대해서 알아보았고 ADT를 정의해 보았다. 다음 포스팅에서는 정의된 ADT를 가지고 리스트를 구현하고 사용해 보도록 하겠다.