[LinkedList] C로 짜는 LinkedLIst (algospot HELLOWORLD)

다양한 알고리즘 문제가 있는 algospot의 HELLOWORLD문제(https://algospot.com/judge/problem/read/HELLOWORLD)를 풀기위해 C언어에서 Linked list를 구현해 보았다.

우선 Linked list란 말 그대로 연결된 리스트로 말보단 그림으로 보는게 더 직관적으로 이해될 것이다.

보통 한 노드에는 원하는 자료형으로 선언된 데이터와 다음 노드를 가리키는 노드로 구성되어있다. 그리고 제일 앞의 노드를 가리키는 head란 노드도 선언해준다. 이런식으로 새로운 값을 추가할 때 노드끼리 연결만 지어준다면 크기 배열과는 달리 비교적 제한없이 생성할 수 있다. 

algospot의 문제를 보면 이름들을 입력받고 Hello, 이름!으로 출력해주는데 list에 입력받은 이름들을 담았다가 출력 시 다 뱉어내도록 해보자.

내가 계획한 linked list는 이런 형태이다.

head 노드가 맨 앞의 노드를 가리키는 것이 아니라 현재 새로 들어온 노드, 즉 제일 마지막의 노드를 가리키게 되는 기준과 같은 역할을 한다. 그리고 맨 뒤 노드의 다음노드가 맨 앞의 노드를 가리킴으로써 뒤와 앞이 연결되도록 한다.

linked list는 가리킴으로 서로 연결되므로 포인터의 사용이 중요하다. 따라서 node 구조체를 선언하고(typedef struct) node 구조체를 사용할 때 node *example; 이런식으로 선언해 노드들을 끌어다 쓴다.

앞에서 배열과는 달리 비교적 제한없이 생성할 수 있다고 했는데 연결지어서 생성되는 node 공간을 malloc으로 동적할당해주기 때문이다.

malloc이란 힙 영역에 메모리를 할당하는 함수인데 메모리 구조를 보면

 여기서 malloc으로 메모리를 할당하면 HEAP영역에 할당이 된다. malloc 함수는 (void *)malloc(size_t size)로 선언하면 사용할 수 있는데 보다싶이 리턴이 void 이므로 사용하고자 하는 자료형으로 선언해줘야한다. malloc으로 신나게 할당만 시켜주면 메모리에 사용할 공간이 부족해질 수 있다. 따라서 malloc을 시켰으면 free를 해줘야한다. free는 동적할당된 공간을 풀어주는 함수이다. 

Linked List를 구현하면서 문제를 푼 코드 https://github.com/chojpsh1/linkedlist/blob/master/helloworld.c