List 자료구조
📝 List 자료구조 목차
- List 자료구조의 이해
- 배열기반 리스트: Array List | 소스 코드
- 연결 리스트: Linked List | 소스 코드
- 원형 연결 리스트: Circular Linked List | 소스 코드
- 양방향 연결 리스트: Double Linked List | 소스 코드
배열 기반 리스트
- 배열 기반 리스트의 단점
- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
- 배열 기반 리스트의 장점
- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.
- 배열 기반 리스트의 오해
- 보통 리스트라고 하면 연결 리스트만을 떠올리고, 배열 기반 리스트는 불필요하다는 오해가 있다.
- 배열 리스트가 가진 장점은 연결 리스트가 가질 수 없는 장점인 만큼, 충분히 가치가 있는 자료구조이고, 배열 기반 리스트는 실제 실무에서도 사용된다.
배열 기반 리스트 구현 소스코드
- 소스코드에서 리스트의 삽입, 탐색, 삭제 과정을 잘 살펴보자.
다양한 종류의 데이터와 다양한 종류의 리스트를 지원하기 위한 typedef
- C언어에서는 코드 구조화 및 재사용성 향상을 위해
typedef기능을 활용한다. - 지금은
int데이터를 지원하지만,typedef의 선언만 바꾸면 다른 데이터를 지원할 수도 있다.
typedef int LData; // 현재 코드는 int형 데이터만 지원한다.int형 뿐만 아니라float이나char등 기본타입은 물론 이고, 구조체 변수의 주소값도 리스트의 데이터로도 사용할 수 있다.
typedef float LData;ArrayList에도typedef를 사용하면 사용자 코드의 수정 없이도 다른 자료구조의List로 쉽게 대체할 수도 있다.
typedef ArrayList List; // ArrayList를 사용하는 List
typedef LinkedList List; // LinkedList를 사용하는 List배열기반 리스트 응용
리스트에 구조체 변수 저장하기
- 실제로 리스트에서는 각종 데이터 뿐만 아니라 구조체 변수의 주소값을 저장하여 더욱 활용도를 높일 수 있다. (C++에서는 클래스의 주소값도 저장된다)
- 이번 예제에서는 Point 구조체를 데이터로 저장해본다.
ArrayList.h
#include "Point.h" // Point.h 추가
#define TRUE 1
#define FALSE 0
/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef Point * LData; //int -> Point *로 변경ArrayList.h파일에 두줄만 수정하면 Point 구조체를 리스트의 데이터로 사용가능하다.
PointListMain.c
int main()
{
...
if (LFirst(&list, &ppos))
{
if (PointComp(ppos, &comPos) == 0 || PointComp(ppos, &comPos) == 1)
{
ppos = LRemove(&list);
free(ppos);
}
while (LNext(&list, &ppos))
{
if (PointComp(ppos, &comPos) == 0 || PointComp(ppos, &comPos) == 1)
{
ppos = LRemove(&list);
free(ppos);
}
}
}
...
}- 데이터를 삭제하는 부분을 살펴보면,
main()함수에서 사용자가 직접 메모리 해제를 하는 것을 볼 수 있다. - 일반적인 리스트는 메모리의 해제까지 책임 지지 않는다. 해제해야할 메모리의 주소값을 반환하여 사용자로 하여금 메모리를 해제하도록 하는 것이 더 일반적인 방식이다.
- 이를 위해서
LRemove함수는 삭제된 데이터를 반환하도록 디자인된 것이다.
