참고 링크 :

[자료구조] 배열 리스트(Array List)

선형 & 비선형 자료구조

• 선형 자료구조(Linear Data Struct)는 데이터가 순차적인 형태로 저장되는 것을 의미합니다. 아래 그림을 보면 A, B, C, D 자료가 순차적으로 저장된 것을 볼 수 있습니다.(물리적 x, 논리적 o)

• 비선형 자료구조(Non-Linear Data Struct)는 데이터가 비순차적인 형태로 저장됩니다. 대표적으로 트리(Tree)와 그래프(Graph)가 있습니다. 선형 자료구조와는 반대로 자료의 저장 형태가 다릅니다.

리스트(List)

• 리스트는 선형 자료구조를 대표하는 자료구조입니다. 따라서 데이터의 저장 형태가 앞서 설명한 선형 자료구조와 동일한 형태입니다.
• 리스트는 구현 방식에 따라서 배열 리스트(Array List)와 연결 리스트(Linked List)로 구분합니다. 배열 리스트는 C 언어에서 제공하는 배열을 사용합니다. 반대로 연결 리스트는 포인터를 사용하여 자료가 서로 연결된 것처럼 구성합니다.
  • 연결 리스트는 연결 구조에 따라 다양한 형태를 갖고 있습니다. 한쪽 방향으로만 연결되어 있는 연결 리스트와 양쪽 방향으로 연결되어 있는 더블 연결 리스트(Double Linked List), 원형 형태로 연결된 원형 연결 리스트(Circular Linked List)가 있습니다.

리스트의 추상 자료형

• 추상 자료형(Abstract Data Type)은 기능의 구체적인 구현 방법을 명세하지 않고 기능의 형태나 동작을 대략적으로 나타낸 것을 의미합니다. 자료구조를 공부할 때 자료구조를 직접 구현하는 것보다 해당 자료구조의 의미와 동작을 이해하는 것이 더 중요합니다. C++의 vector나 map 같은 자료구조를 사용할 때 해당 자료구조의 구현을 공부하진 않는 것과 같습니다.
• 추상 자료형과 비슷한(동일한) 개념은 객체지향 프로그래밍에서 정보 은닉(Information Hiding) 개념입니다. 외부(사용자)에게 구체적인 구현 방법과 자료구조 또는 객체를 사용함에 있어서 불필요한 정보를 제공하지 않습니다. 따라서 추상 자료형은 철저히 자료구조를 사용하는 사람의 입장에서 정의가 되어야 합니다.
• 그렇다면 리스트의 추상 자료형은 어떻게 정의할 수 있을까요? 일반적으로 리스트를 사용함에 있어서 필수적인 정보만을 작성합니다. 리스트를 활용하여 다른 기능을 수행하도록 하는 것은 리스트를 사용하는 사람의 몫으로 남겨두는 것이 원칙입니다.
• 리스트의 필수적인 요소는 초기화(Initialize), 데이터 삽입(추가), 데이터 조회, 데이터 삭제, 리스트 삭제가 있을 것입니다. 만약 필요에 따라 다른 것이 추가되어야 한다면 얼마든지 추가해도 괜찮습니다.

*// 리스트의 추상 자료형
// 리스트 초기화*
void initList(List* plist);

*// 데이터 삽입(추가)*
void insertList(List* plist, ListData data);

*// 데이터 조회(첫 번째)*
void getFirstListData(List* plist, ListData* pdata);

*// 데이터 조회(두 번째 이후)*
void getNextListData(List* plist, ListData* data);

*// 데이터 삭제*
ListData removeListData(List* plist);

*// 추가적인 함수*
int getListLength(List* plist);

• 리스트의 추상 자료형을 정의하였으니, 이제 리스트의 구현을 확인해볼까요?

배열 리스트의 구현

• 배열 리스트는 배열을 활용한 리스트입니다. 참고로 배열 또한 자료구조의 한 종류입니다. 이처럼 어떤 자료구조를 사용하여 다른 자료구조를 구성하는 것은 매우 자연스러운 일입니다.