연결 리스트 ADT

이번 포스팅에서는 연결리스트의 추상자료형에 대해서 알아보도록 하겠습니다.

ADT를 다루면서 오늘은 Public Function, Private Function, API의 개념을 간단하게 알아보겠습니다.

 

---

연결 리스트란 어떤 자료구조인가요?

스택, 큐와 같은 자료구조는 특정한 위치에서 자료에 접근할 수 있고, 특정한 위치에 자료를 입력 및 출력할 수 있습니다.
이와 달리, 연결리스트와 배열은 위의 기능들을 원하는 위치에서 할 수 있습니다. 이와 같이 일반적으로 어떠한 위치에도 item에 접근 추가 삭제가 가능하기 때문에 Generalized list라고 불립니다.

 

배열은 데이터를 추가, 삭제할 때 있어 수행해야 하는 기능의 시간복잡도가 높다는 점, 메모리가 비효율적으로 사용이 된다는 단점이 있습니다. 이러한 단점은 연결리스트로써 해결이 가능합니다.

---

연결 리스트 ADT - 구조와 기능

자료구조의 ADT는 말 그대로 해당 자료구조에는

 

1.어떠한 정보를 담을 수 있으며,

2.저장된 자료들 사이에 어떠한 관계가 있는지,

 

3.저장된 자료들을 사용해 어떠한 기능을 수행할 수 있는지(자료들을 관리하는지)

 

를 명시해 놓은 사용자 관점의 매뉴얼과 같습니다. 지극히 사용자 관점에서 명시된 정보이기 때문에, 개발자 관점에서만 접근이 가능한 Private Function에 대한 정보는 나와 있지 않습니다. 대신 Public Function에 대해서 어떠한 인자 값을 전달받아 어떠한 기능을 수행하는지, 또는 어떠한 자료형의 값을 반환하는지등을 명시해 놓습니다.

---

1. 연결 리스트의 구조

연결리스트는 크게 두 가지의 구조체로써 정의될 수 있습니다.

1. 데이터를 담는 노드 구조체

2. 연결된 노드 구조체를 관리하는 NODE_MGMT구조체

NODE 구조체

NODE 구조체는 기본적으로 자료를 담는 기능을 해야 합니다. 따라서 특정 자료형의 자료를 담거나, 아니면 보다 Generic한 코드를 작성하고 싶다면 void 포인터 문법을 사용하면 되겠습니다.

연결 리스트라는 말에서 알 수 있듯이 이 자료구조의 핵심은 자료들이 서로 연결하는 관계에 있다는 것입니다. 그리고 그러한 연결관계는 NODE 포인터로써 구현이 가능합니다.

 

NODE_MGMT 구조체

 

이러한 연결관계도 결국은 하나의 "시작하는 노드"가 있어야 연결된 모습을 할 수 있습니다. 이 시작하는 노드를 우리는 Head, Root등의 이름으로 부릅니다. 이 head 노드는 저장된 데이터를 찾는 기준점이 되기 때문에 연결리스트를 관리함에 있어서 필수적으로 알고 있어야 하는 정보(속성값)입니다. 

 

또한, 연결리스트를 사용할 때, 특정 데이터가 연결리스트에 저장되어있는지, 저장되어 있다면 어떤 위치에 존재하는지를 알고 싶은 경우가 흔하게 있습니다. 하지만 알다시피 하나의 함수는 하나의 값만을 반환할 수 있습니다.
따라서 우리는 C언어가 제공하는 포인터 문법과 Call- by Reference 기법을 통하여 이 NODE_MGMT의 pos 라는 속성명을 가진 NODE포인터를 통해 간접적으로 얻은 값을 저장할 수 있는 것 입니다.

 

마지막으로 이러한 자료를 관리할 때에는 현재 저장하고 있는 자료의 개수를 기록하는 것이 편리합니다.
따라서 저장된 자료의 개수에 대응하는 속성값을 저장하면 되겠습니다.

---

2. 연결리스트 내의 연산

1. 연결리스트의 생성

연결리스트를 생성한다는 것은 결국 연결리스트를 관리하는 NODE_MGMT 구조체를 하나 새로 만든다는 뜻입니다. 
NODE_MGMT 포인터를 반환하고 입력값이 없는 함수 원형을 가져야 합니다.

 

NODE_MGMT *createList()

2. 연결리스트의 파괴

연결리스트를 생성할 때 있어서 동적할당을 사용합니다. 따라서 이에 대응하여 메모리 해제를 하지 않을 경우, 댕글 포인터가 발생해 프로그램 자체가 작동이 멈춰버릴 수 있습니다. 따라서 동적할당해제를 순서에 알맞게 진행하면 되겠습니다. 파괴할 연결리스트 대상이 명시되어야 하므로 NODE_MGMT 포인터 변수를 전달받으면 되겠습니다.

 

void destroyList(NODE_MGMT *pList)

3. 자료의 검색

검색할 대상이 연결리스트내에 있는지를 연결리스트안을 돌아다니며 찾습니다. 찾던 중 대상을 찾을 경우, True를, 대상을 찾지 못할 경우, False를 반환합니다.

 

bool searchList(NODE_MGMT *pList, NODE **ppPre, NODE **ppLoc)

4. 연결리스트내 탐색

연결리스트의 head노드에서부터 시작해 마지막 노드를 만날 때까지 계속해서 연결된 리스트를 타고 탐색해 나가는 함수입니다. 마지막 노드에 도달해 next 포인터값이 NULL일 경우, head노드로 돌아옵니다.

 

void traverseList(NODE_MGMT *pList)

5. 연결리스트내에 항목 삽입 및 삭제

두 함수 모두 어떠한 연결리스트에 어떠한 위치에 어떠한 값을 삽입 혹은 삭제할 것인지를 명시해야 합니다. 메모리공간에 영향을 끼치지만 반환하는 값은 없는 void형 함수입니다.

 

삽입 및 삭제 함수를 구현할 때 주의할 점이 있습니다. 바로 항목을 삽입하거나 삭제를 함으로써 기존에 있던 연결관계를 해제하고 새롭게 연결관계를 정의해야 한다는 점입니다. next포인터를 통해서 그 관계가 정의가 됩니다.

따라서 찾는 값의 앞에 위치한 노드의 위치를 담을 변수 또한 전달해줘야 알맞게 기능을 수행할 수 있겠습니다.

 

void insertList(NODE_MGMT *pList, NODE *pPre, NODE *pLoc)

void deleteList(NODE_MGMT *pList, NODE *pPre, NODE *pLoc)

 

6. 연결리스트의 상태 확인(저장한 자료 개수, 비어 있는지등)

이는 구조체에 정의된 count 속성값을 활용하면 쉽게 알 수 있습니다. 대상이 되는 NODE_MGMT 포인터변수를 전달해 주면 int형으로 값을 반환하는 형태가 되겠습니다.

 

int numberList(NODE_MGMT *pList)

bool isEmptyList(NODE_MGMT *pList)

---

이번 포스팅에서는 연결리스트의 ADT에 대해서 알아보았습니다. 크게 구조의 측면과 기능의 측면에서 살펴보았습니다. 다음 포스팅에서는 연결리스트를 C언어를 통해서 구현해보는 시간을 가져보겠습니다. 감사합니다.