[EKOO의 JAVA를 이용한 자료구조:4회] Linked List 구..

강좌를 시작하며

안녕하세요.지난 강좌에서 말씀드렸듯이 이번 강좌에서는 Linked List에 대해서 강좌를 나가게 됩니다. 필자는 JAVA에서 Linked List를 접해보기 전에 이미 C 언어로 Linked List로 접해본 경험이 있기 때문에 이것의 중요성을 느끼고 있구요, 또 그 중요성만큼 활용범위도 높은 것이 바로 이 Linked List입니다.

이것을 이번 강좌에서는 JAVA언어를 이용하여 Linked List를 구현해 보게 될 것입니다. C 언어에서 이미 접해보신 분이라면, 포인터 변수가 없는 JAVA와 C 언어를 비교해 가면서 보시는 것도 강좌를 재밌게 보시는 지름길이 되실수 있을 것이라 보입니다.

참고서적 : Data Structures & Other Objects Using JAVA

Linked List란 뭔가

음.. 그냥 영어 의미 그대로 해석을 하자면 '연결되어 있는 목록' 이라고 할 수 있겠죠? 쉽게 예를 들어 보겠습니다. 제가 집에서 장식품과 사슬을 꿰어서 팔찌를 만들어서 납품하는 아르바이트를 한다고 가정하겠습니다. 그렇다면.. 이 팔찌를 만드는데 필요한 재료에는, 구슬과 구슬사이사이를 연결해주는 끈이나 사슬같은 것이 있으면 되겠지요.

[그림 1]
위같은 재료가 필요하겠죠? Linked List 도 같은 구조입니다. 구슬대신 Node 라고 불리우는 것과 끈 대신에 다음 Node를 가리키고 있는 어떤 '변수'를 사용하게 되죠.

C 언어라면 구조체를 이용하여 Node를 구성하게 되지만, Class로만 이루어져 있는 JAVA에선 하나의 Node를 하나의 클래스를 이용하여 틀을 잡아주면 되는 것입니다.

[그림 2]
위처럼 표현할 수 있습니다. 색깔과 next를 가지고 있는 표를 Node 라고 할 수 있으며, Node 는 구슬의 색깔이나 모양 같은 정보를 가지게 되며, next는 Node와 Node를 연결해주는 끈 역할을 하게 되는 변수입니다. 자세한 구현은 뒤에 나오는 구현부에서 하도록 하죠.

만약에 전화번호부를 짜게 된다면 Node에는 어떠어떠한 것들이 들어가게 될까요? 자신의 핸드폰 전화번호부를 열어보면 쉽게 아실수 있게 됩니다. 이름, 전화번호, 주소, 이메일, 사진 등등이 들어가게 되겠죠. 이렇게 열거한 것들이 Node안에 들어갈 자료들이 되며 하나의 Node는 한 명의 사람이라고 생각할 수 있습니다.

[그림 3]
위의 그림이 실제 전화번호부를 구성하게 될 하나의 Node입니다. 중간의 ... 으로 처리한 부분에는 더 많은 정보가 들어갈 수 있게 되겠죠? 이런 Node안에 해당 자료를 입력하고 그런 Node들을 어떠한 끈 같은 것으로 연결한 것이 바로 링크드 리스트입니다.

[그림 4]
위의 그림은 Node들을 여러개 만들어서 그 Node들을 연결한 모습입니다. 위의 모습이 바로 Node 6개 짜리 Linked List 라고 하는 것이죠. 마치 팔찌를 완성시킨 것과 흡사하게 생겼죠. 프로그램에서는 보이지는 않지만요 ^^;

자세한 구현법은 역시 이 강좌의 뒷 부분에서 코드를 하나하나 보면서 설명하도록 하겠습니다.

Linked List 와 Array의 비교

지난 강좌에서는 Array에 대해서 배우셨죠? 사실... 방금 설명드린 Linked List를 쓰지 않고 2차원 배열등을 이용하여 충분히 전화번호부 정도는 작성을 할 수 있습니다. 하지만... 왜 배열을 쓰지 않고 Linked List를 사용하려는 걸까요? 그 이유에 대해서 약간 짚고 넘어가겠습니다.

구조체를 이용해서 자료들을 나열하는데는, 저번강좌에서 설명한 Array를 사용하는 방법과 이번 강좌에서 다루는 Linked List를 이용한 방법이 있습니다. 사실 Linked List를 처음 다루는 분들은 배열에 비해서 해줘야 할 것도 많고, 머릿속에 바로 떠오르지도 않는 걸 왜 쓰냐고 하실지도 모르겠습니다. 하지만 Linked List 가 Array로 보다 좋은점들이 많기 때문에 많이들 쓰는 것이겠죠?

우선은 메모리사용 측면에서 더 효율적이라고 말할 수 있겠습니다. 만약에 100명의 사람을 저장해야 하는 전화번호부 프로그램이 있다고 생각을 해 보겠습니다. 그러면 Class 인스턴스 Array를 사용한다면 프로그램을 시작할 때부터 인덱스가 100인 클래스 배열을 잡아놓고 프로그램을 돌려야겠죠?

100명의 공간을 다 채워서 쓴다면 상관없겠지만, 10명, 30명만 저장해도 되는데 굳이 100명의 공간을 다 잡아놓을 필요가 있을까요? 쓰지도 않는 공간을 미리 잡아놓는건 매우 쓸데없는 것이죠. 하지만 Linked List를 쓴다면 필요할 때 마다 하나씩 늘여주면 되므로 메모리 낭비는 매우 줄어들게 됩니다.

그 다음으로는 리스트 관리의 편이성입니다. 100명의 자료를 가지고 있는 전화번호부 프로그램이 두 개가 있다고 가정을 해보죠. A프로그램은 이것을 Class Array로 구현을 했고, B프로그램은 Linked List로 구현을 했다고 해봅시다.

100명의 자료는 알파벳 순으로 이미 정렬이 되어 있구요. Bond 라는 사람의 리스트를 삭제해야 하는 경우가 발생했습니다. Linked List로 구현을 했다면 Bond의 Node만 삭제해주고 그뒤와 앞을 연결만 해주면 문제가 없죠? Bond 가 빠지고 난 후의 리스트도 알파벳 순서로 정렬이 되어 있겠죠.

하지만 Array 로 구현을한 A프로그램에서는 Bond 라는 사람이 있는 인덱스의 자료를 초기화 해주고, 하나씩 다 앞으로 당겨줘야 하는 불필요한 과정이 들어가게 됩니다. 리스트의 앞쪽에 있는 사람일수록 옮기는 시간은 더욱 오래 걸리겠죠?