Linked List : 연결 리스트
처음으로 나오는 연속하지 않는 자료구조이다.
배열을 설명할 때 나왔던 것처럼, 연속된 메모리를 사용하려면 메모리에 커다란 가용 공간이 있어야 한다.
그렇지만 연결 리스트를 사용하면 그런 제한 조건에서 벗어나게 된다.
그렇다면 연결 리스트는 어떤 방식으로 동작하는 것일까 ?
먼저, 배열과 비교해보자. 배열은 연속된 메모리에 할당되어 있으므로, 각각의 변수에 접근하기가 매우 편했다.
예를 들어 int 변수의 배열이라면, 1번째 변수의 주소에 4를 더하면 2번째 변수의 주소가 되고, 3번째 변수의 주소는 그 주소에 4를 더하면 된다.
무척이나 간단하게 변수들에 접근 할 수 있다는 것이다.
그림1. 불연속 메모리 공간
그림1을 보자면, 우리가 연결 리스트를 사용하는 가장 큰 장점은 불연속한 메모리 공간을 효율적으로 사용하기 위함이다.
그렇다면 위에서 각각의 공간에 접근하려면, 단순히 주소에 일정 숫자를 더하는 것으로는 불가능하다는 것을 알 수 있다.
1에서 2 가는 것은 문제가 없으나, 2에서 4를 가려면 3이라는 장애물이 생긴다 !
이를 해결하기 위한 것이 바로 포인터이다.
각각의 변수들은 내용 뿐만 아니라, 그 다음 변수를 가리키는 포인터를 갖고 있으면 문제가 해결된다 .
따라서 데이터구조들은 변수 뿐만 아니라 다음을 가리키는 포인터까지 갖고 있어야 한다.
그것이 연결 리스트의 최소 단위가 되는 것이다. 이것을 구현하는 방법은 이미 우리가 배웠다.
서로 다른 타입의 변수를 함께 사용하는것, 그렇다 바로 구조체이다.
1 2 3 4 | typedef struct _node { int data; struct _node *next; }Node, *pNode; | cs |
이것이 연결 리스트의 최소 단위, Node이다.
기본적인 node는 위와 같이 데이터와, 다음 노드를 기리키는 포인터로 구성이 되어 있다.
이를 그림으로 시각화한다면 다음과 같다.
그림2. 노드 연결 구조
각각의 노드들은 위의 그림 2와 같이 연결되어 있다.
그림3. 불연속 메모리 공간에서 노드 연결
최초 그림 1에서 문제가 되었던, 불연속 메모리 공간에서도 문제가 없다. Next는 정상적으로 다음 노드를 가리킬 수 있다.
따라서 메모리가 어떻게 정렬이 되어 있는가에 관계 없이 공간이 남아 있다면 얼마든지 데이터를 추가할 수 있다는 장점이 있다.
연결 리스트는 종류도 여러 가지가 존재하는데, 위의 그림 2와 같은 연결리스트를 단순 연결 리스트 (Single Linked List)라고 한다.
왜 단일 인가 하면 노드에 접근할 수 있는 방법이 한가지 뿐이기 때문이다. 즉, Next를 통해서 Head부터 Tail까지 일방향으로만 접근이 가능하다.
우스운 예를 하나 들어보자.
1, 2, 3, 4, 5, 6, 7의 노드가 있다. 내가 접근해야 할 노드는 5번 노드인데, 실수로 6번까지 넘어가버렸다. 그렇지만 5번 노드로 돌아갈 수가 없다.
왜냐하면 6번은 7번의 위치만 알고 있기 때문이다 ! 따라서 5번에 접근하기 위해서는 다시 1번부터 차례대로 지나가야 하는 것이다.
만약에 6번에서 5번을 가리키는 주소가 있었다면..?
위와 같은 상황에서 나온 것이
이중 연결 리스트(Double Linked List)이다. 노드에 Prev 포인터를 추가해서 이전 노드를 가리키게 만든다.
그림4. Double Linked List
이번엔 다음과 같은 예시 상황을 생각해보자.
철수, 영희, 민국, 대한이는 술래잡기를 하고 있다.
우스꽝스럽게도 이 친구들은 술래가 잡은 사람이 술래가 되는 것이 아니라, 차례대로 술래를 맡는다.
순서는 다음과 같다.
철수 -> 영희 -> 대한 -> 민국 .
이러한 상황에서 민국이가 술래를 마치면, 게임이 종료하는 것이 아니라 다시 철수가 술래가 된다. 즉,
철수 -> 영희 -> 대한 -> 민국 -> 철수 -> 영희 ................. 의 순환이 계속된다는 것이다.
이를 연결 리스트로 구현한 것이
원형 연결 리스트 혹은 순환 연결 리스트이다. (Circular Linked List)
구현은 너무나도 간단하다. 마지막 노드의 next에 첫번째 노드를 가리키게 해주면 된다.
그림5. Circular Linked List
위의 그림(하나님은 나에게 미적 재능을 주지 않으신 것이 분명하다.)은 순환 연결리스트를 시각화한 것이다.
위의 내용들은 모두 Node에 관한 내용이었다.
그리고 이러한 Node들을 관리하는 주체가 필요하니, 그것이 바로 Linked List이다.
List라는 구조체를 선언하여 node들의 위치를 파악하고, 관리한다.
그러나 모든 node들의 위치를 알 필요는 없다.
왜냐하면 어떤 종류의 연결리스트이던 간에 처음 노드를 알면 끝의 노드까지 next를 통해 이동할 수 있기 때문이다.
따라서 보통 List라는 구조체를 선언하면, 처음 노드를 가리키는 head 포인터를 갖게 된다.
거기에 더불어 조금 더 편리함을 위하여 node의 갯수나, 마지막 노드를 가리키는 tail 포인터를 추가하기도 한다. 다음과 같이.
1 2 3 4 5 | typedef struct _list { int count; // 노드의 갯수를 저장한다. pNode head; // 첫번째 노드를 가리킨다. pNode tail; // 마지막 노드를 가리킨다. }; | cs |
이것으로 Linked List의 개념부분을 모두 배웠다.
다음 3-2 포스트에서는 직접 코딩을 하면서 몸에 링크드 리스트를 집어 넣도록 하겠다!
<질문> Double Circular Linked List는 어떻게 구현해야 하는가?