[자료구조] 배열을 이용한 리스트 구현

배열을 이용한 리스트 구현 - 순차 리스트, 연결 리스트

---

• 순차 리스트 : 배열을 기반으로 구현된 리스트

• 연결 리스트 : 메리의 동적 할당을 기반으로 구현된 리스트

  --> 두 리스트는 ADT(기능)는 동일, 구현방법만 다름.

• 리스트의 특징

  • 저장형태 : 데이터를 나란히 저장한다. (어느 방향으로 저장하든 상관 없다.)

  • 저장 특성 : 중복이 되는 데이터의 저장을 허용.

    --> 배열과 연결을 기반으로 함.

• 배열 기반 리스트의 단점

  • 배열의 길이가 초기에 결정되어야 함. 변경이 불가능

  • 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어남.

• 배열 기반 리스트의 장점

  • 데이터의 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조 가능.

---

리스트 자료구조의 ADT(기능)

• 리스트의 초기화

void ListInit(List *plist);
- 초기화할 리스트의 주소 값을 인자로 전달
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수

• 데이터 저장

void LInsert(List *plist, LData data);
- 리스트에 데이터를 저장하고, 매개변수 data에 전달된 값을 전달.

• 저장된 데이터의 탐색 및 탐색 초기화 : 조회를 처음부터 다시 시작하겠다.

int LFirst(List *plist, LData *pdata);
- 첫번째 데이터가 pdata가 가리키는 메모리에 저장됨.
- 데이터의 참조를 위한 초기화가 진행됨
- 참조 성공시 True, 실패시 False 반환

• 다음 데이터의 참조를 목적으로 호출

int LNext(List *plist, LData *pdata);
- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장됨
- 순차적인 참조를 위해서 반복 호출이 가능
- 참조를 새로 시작하려면 먼저 LFirst 함수 호출
- 참조 성공시 True, 실패시 False 반환

• 바로 이전에 참조(반환)이 이뤄진 데이터의 삭제

LData LRemove(List *plist);
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제
- 삭제된 데이터 반환
- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출 허용 X

• 현재 저장되어 있는 데이터의 수를 반환

int LCount(List *plist);
- 리스트에 저장되어 있는 데이터의 수를 반환

• LFirst와 LNext가 따로 있는 이유

  • LFirst는 배열의 처음부터 확인할 때 쓰는 거고, LNext는 1번, 2번... 순차적으로 확인할 때 사용하는데, 대부분 라이브러리가 이런 구조를 활용함

• ex) LData에 Point 구조체가 들어가는 경우.

  • ArrayList.h 파일과 메인 함수가 포함된 c파일만 수정하면 됨.
  • ArrayList.c 함수 코드를 수정할 필요가 없다.

참조) 윤성우의 열혈 자료구조 (윤성우, 오렌지미디어)