[2기 대구 이현복] Data Structure - List

안녕하세요.

대구 멤버십 21기 이현복 입니다.

Data Structure중 두번째 주제인 List에 대한 이야기 입니다.

자료구조 중에서 배열과 더불어 가장 많이 쓰이는 형태가 List입니다.

리스트는 다음 데이터가 있는 위치를 저장함으로써

데이터가 저장된 위치에 상관 없이 연속된 데이터 처럼 사용할 수 있도록 한 자료구조 입니다.

리스트의 기본적인 연산으로 create, add, del, retrieve, length 가 필요합니다.

create : 새로운 리스트를 생성하는 함수

add : 새로운 노드를 추가하는 함수

del : 해당 노드를 삭제하는 함수

retrieve : 데이터를 참조하여 보여주는 함수

length : 리스트 내의 데이터 갯수를 알려주는 함수

물론 더 많은 함수가 제공된다면 좋겠지만 기본적으로 필요한 함수는 이 정도 입니다.

이러한 리스트를 구성하기 위해서는 흔히 '노드(Node)'라고 불리는 구조체를 사용 합니다.

노드는 데이터를 저장하는 변수와 다음 데이터의 위치를 저장하는 변수로 구성됩니다.

이러한 구조체를 이용하여 연결 리스트를 만들면 다음과 같은 형태로 만들 수 있습니다.

위와 같이 간단히 작성한 코드는 단일 연결 리스트(Singly Linked List)라고 하며

몇가지 문제에 대하여 생각 해 볼 수 있습니다.

1. 노드의 삽입/삭제 코드가 일반화 되지 못합니다.

코드에서 삽입하는 위치가 맨 앞으로 고정했기 때문에 하나의 함수 였지만

다른 특정한 위치에 삽입을 하거나 삭제를 할려고 하면 별도의 함수를 또 만들어야 합니다.

하지만 헤더부분에 데이터가 들어있지 않은 dummy 노드를 만들게 되면

입력되는 형태가 일치되어 코드를 일반화 할 수 있습니다.

2. NULL로 끝나기 때문에Process가 죽을 수 있다.

리스트의 끝이 NULL로 이루어져 있기 때문에 NULL을 참조하여 프로세스가 강제종료 될 수 있습니다.

리스트의 끝 부분을 자신(끝)을 가리키도록 함으로써 NULL이 없는 구조로 만들 수 있습니다.

또한 이런 방법을 사용하면 끝이라는 것을 알기 위해 Tail이라는 변수가 필요하게 됩니다.

3. 프로세스 내에 리스트가 하나만 존재 할 수 있다.

Head를 전역에 선언함으로써 프로그램 내에서 사용가능한 리스트는 하나로 제한됩니다.

함수의 인자값으로 리스트를 넘겨주게되면 인자에 따라 다른 리스트를 사용할 수 있습니다.

4. 리스트 노드의 메모리가 Heap에 의존적이다. 메모리 풀링 기법을 사용 할 수 없다.

메모리를 할당(malloc)/해제(free)하는 코드가 노드를 추가/삭제하는 함수 안에 들어 있기 때문에

메모리 사용을 임의로 제어 할 수가 없습니다.

추가/삭제 하는 함수에서 메모리 관련된 부분을 분리하여 따로 관리하는

가용 노드 리스트(Available Node List)를 이용한 메모리 풀링기법을 사용 할 수 있습니다.

5. Tail이 굳이 있을 필요는 없다.

끝을 알기 위해서 Tail을 사용 하였는데 순환되는 부분을 Tail에만 국한하지 않고

리스트 전체로 변경하게되면 굳이 Tail이 있을 필요는 없습니다.

이러한 형태의 리스트를 환형 연결 리스트(Circular List)라고 합니다.

6. 역순으로 검색 할 수 있는가?

리스트를 사용하다보면 순방향이 아니라 역방향으로 검색을 하고 싶을때가 있습니다.

이런 경우 리스트를 뒤집는 리버스(Reverse) 방법을 사용할 수 있습니다.

리버스를 하게되면 3개의 포인터를 이용하여 순차적으로 순서를 뒤집게 되는데

원본 리스트가 바뀐다는 단점이 있습니다.

또는 처음부터 이런 상황을 고려하여 이중 연결 리스트(Double Linked List)로 구성할 수 있습니다.

7. 리스트가 노드 타입에 의존적이다.

노드를 지금과 같이 만들게 되면 노드에서 지정한 타입만 사용을 할 수 있습니다.

void* 를 이용한다면 데이터 타입에 무관하게 데이터를 넣을 수가 있습니다.

8. 캡슐화가 안되어 있다.

노드에 데이터를 지정하게되면 노드의 구성을 다른 사용자도 알고 있어야 합니다.

하지만 리스트를 구성하는 포인터만을 가지고 데이터 부분을 분리한다면 다른 사용자가 알 필요가 없어집니다.

자료구조 중 두번째 주제인 리스트는 배열과 함께 다른 자료구조의 바탕이 되는 가장 중요한 자료구조입니다.

그렇기때문에 어떤 형식으로든 쓸수 있도록 알아 두면 좋을 것 같습니다.