03. 배열 리스트 (Array List)
03-1. 추상 자료형 : Abstract Data Type
'구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'을 가리켜 추상자료형(ADT)라 한다.
예를들어 지갑에 동전을 넣고 빼는 과정을 자세히 설명하면 다음과 같다.
지갑을 들어 지퍼를 열고 동전을 안에 넣고 지퍼를 다시 닫는다.
지갑을 들어 지퍼를 열고 동전을 집고 동전을 빼고 지퍼를 다시 닫는다.
이를 추상자료형으로 나타내면 다음과 같이 나타낼 수 있다.
동전의 삽입 / 동전의 추출
03-2. 배열을 이용한 리스트의 구현
리스트 자료구조는 구현방법에 따라 크게 두가지로 나뉜다.
- 순차 리스트 : 배열을 기반으로 구현된 리스트
- 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트
리스트 자료구조의 특성은 다음과 같다
- 리스트 자료구조는 데이터를 나란히 저장한다. 이때 중복된 데이터의 저장도 허용한다.
이러한 특성을 기반으로 리스트의 ADT를 다음과 같이 정의할 수 있다.
void ListInit(List * plist);
-초기화할 리스트의 주소 값을 인자로 전달한다.
-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
void LInsert(List * plist, LData data);
-리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
int LFirst(Lsit * plist, LData * pdata);
-첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
-데이터의 참조를 위한 초기화가 진행된다.
-참조 성공 시 TRUE(1), 실패 시 FALSE(0)반환
int LNext(List * plist, LData * pdata);
-참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
-순차적인 참조를 위해서 반복 호출이 가능하다.
-참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
-참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
LData LRemove(List * plist);
-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
-삭제된 데이터는 반환된다.
-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
int LCount(List * plist);
-리스트에 저장되어 있는 데이터의 수를 반환한다.
배열 기반 리스트의 장점
- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.
배열 기반 리스트의 단점
- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
'자료구조, 알고리즘' 카테고리의 다른 글
[자료구조] 스택 (Stack) (0) | 2022.04.01 |
---|---|
[자료구조] 원형 연결 리스트 (Circular Linked List) (0) | 2022.03.04 |
[자료구조] 연결 리스트(Linked List) (0) | 2022.03.01 |
[자료구조] 재귀(Recursion) (0) | 2022.02.18 |
[자료구조] 자료구조와 알고리즘의 이해 (0) | 2022.02.17 |