[펌_자바를 이용한 자료구조] 연결 리스트(Linked List)

LONG 2. List의 중간에 있는 Node를 지울때,

1번째 단계

2번째 단계

3번째 단계
3. List의 마지막 Node를 지울때,

1번째 단계

2번째 단계

3번째 단계
3번째 단계에서 혼자 떨어지게된 248을 가지는 Node는 Garbage Collector가 알아서 삭제를 해주게 되죠. 어차피 저 리스트에서는 더 이상 사용하지 못하게 됩니다.

실제 작성된 코드를 보도록 하겠습니다.

public static void remove(int target) {    Integer_node point;    Integer_node prev_point;    int remove_result = 0;    // 찾아서 지우면 1, 못찾았으면 0 세팅    point = head;    prev_point = point;    do    {     if(prev_point == point) // 지워야할 Node가 리스트의 맨 처음이라면,        {             head = point.Next;            point.Next = null;        }        else        {              prev_point.Next = point.Next;              point.Next = null;          }      // 삭제를 했으므로 사이즈를 하나 줄여주고      // remove_result 를 세팅 해준다.      bag_size--;      remove_result = 1;    }    // prev_point는 원래 point가 가리키던 Node를 가리키고    // point는 다음 Node를 가리키게 됩니다.    prev_point = point;    point = point.Next; }  while(point != null);  switch(remove_result)  {    case 1:      System.out.println("'" + target + "'" + "을(를) 리스트에서 삭제 하였습니다.");      break;    case 0:       System.out.println("'" + target + "'" + "을(를) 리스트에서 찾지 못했습니다.");      break;  } }

가장 복잡한 remove 함수를 다 짰군요. 이제는 모든내욜을 보여주는 print_bag()함수와. Bag을 초기화 해주는 init_bag()함수만 작성하면 되겠죠. remove에 비해서는 쉬우니 한번에 설명하도록 하겠습니다.

public static void print_bag() {     Integer_node point;      point = head;     System.out.println("Bag's Size : " + bag_size);     System.out.println();     System.out.println();     do     {       System.out.println("Node Number : " + point.Number);       point = point.Next;     }     while(point != null);     System.out.println();     System.out.println(); }

public static void init_bag() {     head = null;     tail = null;     bag_size = 0; }

강좌를 마치며...

이제서야 Linked List강좌가 끝났네요. 이제 이것을 토대로 앞으로 설명드릴 트리, B-트리 등등이 나올텐데요... 이번 강좌를 제대로 이해하지 못하셨다면, 앞으로 나올 강좌 내용을 이해하시기 어려울 듯 보입니다. 눈으로만 보지 마시고, 직접 코딩을 해서 이해하는게 가장 좋은 방법 같습니다. 다음강좌때 뵙도록 하죠! ^^

ARTICLE

강좌를 시작하며

안녕하세요. 지난 강좌에서 말씀드렸듯이 이번 강좌에서는 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 라는 사람이 있는 인덱스의 자료를 초기화 해주고, 하나씩 다 앞으로 당겨줘야 하는 불필요한 과정이 들어가게 됩니다. 리스트의 앞쪽에 있는 사람일수록 옮기는 시간은 더욱 오래 걸리겠죠?

 

=============================================================================================

 

Linked List로 Bag 만들어 보기

지난 강좌에서는 Array를 이용하여 숫자들이 들어가는 Bag을 만들었죠. 이번엔 그와 유사한 기능을 가진 Bag를 Linked List로 구현해 보도록 하겠습니다. 함수 목록은 지난번에 같이 고민해 봤으니깐 바로 코드 설명들로 들어가도록 하겠습니다. 일단 숫자들이 들어가는 Bag을 구현하기 위해서 Class를 이용하여 Node의 뼈대를 구성해 주어야 하겠지요?

class Integer_node { }

위 코드처럼 만들면 Node의 뼈대를 가지는 클래스가 하나 선언이 되는 것입니다. 그에 들어가는 변수들은 숫자가 들어가겠구요, 배열과는 조금 다르게 전에 보신 끈 역할을 하는 Next라는 다음 Node를 가리키는 변수가 필요하게 됩니다.

private int Number; private Integer_node Next; private static int bag_size = 0; private static Integer_node head = null; private static Integer_node tail = null;

위의 세가지 변수는 이해가 가시겠죠? 밑에 있는 head와 tail 이라는 변수는 Linked List를 처음 접하신 분이라면 생소할지 모르겠군요. head와 tail이라는 두가지 변수를 가지고 Linked List를 맘대로 조작하실 수 있습니다. head는 언제나 List의 맨 처음 Node를 가리키게 되구요, tail은 언제나 List의 맨 끝 Node를 가리키게 됩니다.

[그림 1]

[그림 1] 에서와 같이 어느 Linked List 이건간에 head와 tail 이라는 변수가 존재하는건 보통입니다. 사실 tail은 없어도 되죠. 하지만 head는 꼭 있어야만 하며, head 값을 잘못 조작하여 원래의 값을 잃어 버리게 된다면 이미 구성해놓은 리스트들을 다 놓쳐 버리게 되죠. 다 완성된 팔찌를 손으로 들고 있다가 놓쳐서 하수구로 빠트린 격이랄까요. 하지만 팔찌가 빠지더라도 맨 처음만 잡고 있다면야 다시 꺼낼수야 있겠죠. head를 이용하여 하나하나 Node들을 접근할 수 있게 됩니다. 밑에서 계속 설명되는 print_bag 함수나 remove 함수를 잘 살펴 보신다면 충분히 이해가 되실 겁니다. 이제 함수를 하나하나 작성해 나가보죠. 이번에는 생성자에 아무코드도 넣어줄 필요가 없습니다.

// 생성자. Integer_node() { {

그 다음으로 간단한 add 함수를 짜보겠습니다.

// 생성자. public static void add(int element) {     Integer_node temp = new Integer_node();     // 리스트가 맨 처음 구성되어질 경우, 즉 노드가 하나도 없음.     if(bag_size == 0)     {      temp.Number = element;      temp.Next = null;      head = temp;      tail = temp;    }     else     // 리스트가 이미 구성되어져서, 노드를 추가해주는 경우    {       temp.Number = element;       temp.Next = null;       tail.Next = temp;       tail = temp;   }     // add를 했으니 size를 증가 시켜 주어야 겠죠?     bag_size++; }

add에는 두가지의 경우가 있습니다. List를 처음으로 구성하는 경우와, 이미 구성되어 있는 List에 Node 만을 추가해주는 경우입니다. 주석으로 달아놓았으니 참고 바랍니다. 그 다음으로 remove 함수를 한번 보죠. remove 함수 역시 두가지의 경우가 있습니다. 중요하므로 그림부터 일단 보도록 하겠습니다.

[그림 2]

[그림 2] 처럼 리스트가 구성이 되어 있다고 가정합시다. 첫 번째 상황은 리스트의 맨 처음 Node를 지워야 하는 경우이며, 두 번째 상황은 리스트의 중간 Node를 지우는 경우가 됩니다. (햇갈리므로 손으로 짚어가면서 차근차근히 읽어주세요.) 1. List의 처음 Node를 지울때.    - head를 처음 Node의 다음 Node로 옮겨줍니다. 2. List의 중간에 있는 Node를 지울때    - point가 지워야 할 Node를 가리키도록 합니다(prev_point는 언제나 point가 가 리키는 Node의 직전 Node를 가리키고 있죠.)    - prev_point가 가리키는 Node의 Next가 point가 가리키는 Node의 다음 Node를 가리키도록 세팅합니다. 3. List의 마지막에 있는 Node를 지울때    - point가 리스트의 맨 마지막을 가리키게 됩니다(prev_point는 언제나 point가 가 리키는 Node의 직전 Node를 가리키고 있죠.)    - tail을 prev_point가 가리키는 Node를 가리키도록 세팅해줍니다.    - tail의 Next를 null로 세팅해줍니다. 1번의 상황은 쉬운 상황이기에 금새 이해가 가실지도 모르겠지만 2번상황은 좀 햇갈리죠. 1번과 2번 상황을 밑의 그림 에서 차례차례 설명드리겠습니다. 참고하세요. 1. List의 처음 Node를 지울때.

1번째 단계 2번째 단계

2개의 단계만 거쳐주면 10을 가지고 있던 처음 Node를 접근할 수가 없게 되어 자동적으로 메모리에서 사라지게 됩니다. 2번째 단계 부터는 다음시간에 설명하도록 하겠습니다.