[자료구조] C - 링크드리스트, LInkedList

C언어로 해보는 링크드 리스트

LInked List를 이해학기 위해 좋은 자료를 만들어봤습니다.

링크드 리스트는 기존의 배열을 사용함에 있어서 문제점을 해결하는 것입니다.

아래의 자료처럼 배열은 초기화시에 배열공간을 선언하면 해당하는 공간만 사용이 가능합니다.

그래서 자료가 추가/삭제 되었을 경우 

공간이 모자라거나 남아서 메모리를 낭비/부족하게 되는 경우가 생기게됩니다.

위는 데이터 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}를 추가하고

중간에 6을 삭제하는 데이터 처리를 했더니

배열에서는 공간이 부족하여 11이 못들어가고,

6을 삭제했더니 중간에 한칸이 비어버려서 메모리가 낭비하는 일이 발생합니다.

링크드 리스트를 사용하면 이런 메모리의 낭비를 줄일 수가 있습니다.

공간이 필요하면 그때 메모리를 할당하여 공간을 만들고 만들어진 공간을 기존의 리스트에 추가하면 됩니다.

필요없는 데이터는 삭제하고 중간에 끊기는 리스트를 앞뒤로 이어주면 리스트를 파괴하지 않고도 데이터 수정할 수 있습니다.

상당히 편한 방법입니다.

링크드 리스트를 어떻게 구현할 수 있는지 알아보겠습니다.

링크드 리스트를 사용하기 우해서 알아둬야할 것은 (C 기준으로)

-동적할당(malloc)

-구조체(struct)

-포인터(pointer) 

정도가 되겠습니다.

하나의 구조체(node)에는 필드(데이터)가 3개가 있는데

-data : 리스트안에서 사용하는 값(배열에 넣는 값)

-address_left = L_link : 왼쪽 노드(구조체) 주소 

-address_right = R_link : 오른쪽 노드(구조체) 주소

주소가 입력되는 부분은 주소가 들어가니 실제로 왼쪽 오른쪽 노드(구조체) 를 참조하기 위해서는 포인터로 선언해야합니다.

아래의 주소에서 코드를 확인할 수 있습니다.

https://github.com/geusan/datastructure/blob/master/c_language/01_linkedlist.c

PS.

글을 쓰고나서 든 생각인데 이것은 단일(linear) 링크드 리스트가 아니라 이중(double)링크드 리스트입니다.  

이거 이해하면 C에서 만드는 모든 자료구조는 다 이해할 수 있을 것입니다. 

첫단주부터 서두르지 말고 차근차근 생각해보면 이해할 수 있습니다.