C로 만든 Linked List 레포트

목차

없음

본문내용

자료구조 시간에 배우게 되는 Linked List에 대해서 어렵게 생각하시는 분들 위해 소스코드와 이에 대한 설명을 해드리겠습니다.
C의 제어문이나 포인터, 구조체 등 기본적인 문법과 Linked List에 대한 기본 틀을 알고 있다고 가정하고 설명 드리겠습니다.

(4 ~ 8 line) : 구조체입니다. 이 구조체 안에는 노드의 실질적인 값인 data와 다음 노드를 가리킬 포인터가 있습니다. next포인터가 ‘다음 노드를 가리킨다.’는 사실과 포인터 안에 ‘다음 노드의 주소를 저장한다.’는 사실을 모두 떠올리시면 리스트 구조를 이해하는데 도움이 되실 겁니다.

(10 ~ 14 line) : 리스트를 구현한 구조체입니다. 현재 노드의 수를 저장하는 currentElementCount변수와 헤더노드를 가지고 있습니다.
현재 노드의 개수는 이후 ‘노드삽입’에서 삽입할 위치가 적절한지를 검사하기 위해서 필요합니다. 검사를 하지 않는 linked list를 만들 경우 없어도 무방합니다. 여기서 주의 생각해 볼 것이 이 리스트는 헤더 노드를 설정했다는 점입니다. 수업시간에 배운 방법은 아마 헤더 포인터를 설정하여 구연한 linked list일 겁니다. 그 방법으로 구현한 리스트는 아래와 같은 모습입니다.

그리고 위의 코드를 구현(header node를 통한 구현)한 것은 다음과 같습니다.
LinkedList구조체 안에 '헤더노드‘가 있는 모습입니다. ‘헤더노드’는 데이터 저장을 위한 노드가 아니라 노드의 추가와 삭제의 구현을 간편하게 하기 위한 노드입니다. 헤드 포인터로 구현할 시에는 노드 추가 시, 첫 노드인지 아닌지를 구분해서 코딩해야 하지만 헤더노드 형식으로 구현하게 되면 구분하지 않고 코딩이 가능합니다. 그 이유는 추가, 삭제 할 때 이전 노드를 사용하는데, 헤더포인터로 구현할시 첫 노드의 이전 노드가 없으므로 첫 노드를 추가할 경우를 따로 생각해 주어야 하기 때문입니다.

참고 자료

‘열혈강의 자료구조<이상진>_프리렉’의 ‘연결 리스트’