[C로 만드는 자료구조]리스트(List) - 동적 연결 리스트

연결 리스트

지난 포스팅에서는 배열을 이용한 리스트를 구현해 보았습니다. 하지만 배열은 크기가 지정이 되어있어서 넣는 양의 한계가 있으며 그렇다고 무한정 늘려서 만들게 되면 또 쓸데없는 메모리 낭비를 할 가능성이 매우 높아집니다. 그래서 만드는 것이 연결 리스트 입니다. 연결 리스트는 여러 개의 작은 공간을 연결하여 하나의 자료구조를 표현하며 또 크기 변경이 유연하며 낭비를 하지 않아 더 효율적으로 메모리를 사용할 수 있습니다.

동적으로 구현된 연결 리스트는 메모리 안에서 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요가 없습니다.

다음으론 연결리스트의 장단점을 알아 보겠습니다.

• 장점
  
  
• 삽입 및 삭제가 용이
• 연속된 메모리 공간이 필요없음
• 크기 제한이 없음(시스템이 허용하는 메모리한해서)
  
  
• 단점
  
  
• 구현이 어렵다.
• 오류가 발생하기 쉽다.
  
  

연결리스트는 다음과 같은 구조를 가지게 됩니다. 각 데이터와 주소를 가진 한 단위를 '노드'라고 부르며 한 노드는 다음과 같은 구조체를 이용하여 구현합니다.

typedef struct ListNode
{
    int VALUE;//값
    struct ListNode *Link;//다음 노드의 주소를 저장
}ListNode;

또 연결리스트는 개별을 구분하기 위하여 head pointer를 가지고 있습니다. 마치 앞에 이름표를 달 고 있는 것과 같은 것입니다. 연결 리스트에서의 Head Pointer에 대해서 알아 보겠습니다.

• Head Pointer 란?
  
  
• 리스트의 첫 번째 노드를 가리키는 포인터 변수
• 특정 노드를 찾아가기 위해서는 헤더로 리스트를 찾은 후 헤더로 부터 차례 차례 순차적으로 찾아 들어 가야함.
• 순차적으로 연결 되어 있기 떄문에 첫 노드만 찾으면 같은 리스트 소속의 모든 데이터에든 찾아 갈 수 있음.

경우에 따라서는 Tail Pointer라 하여 리스트의 마지막 노드를 가리키는 포인터를 사용하기도 합니다.

다음으론 동적 연결 리스트의 종류를 알아보겠습니다.

동적 연결 리스트는 연결 방향과 형태에 따라 4가지로 나눌 수 있습니다.

1. 단순연결 리스트

단순 연결 리스트는 한방향으로 앞에서 뒤로만 연결이 되어있는 리스트를 의미합니다. 가장 마지막 노드의 Link값은 NULL을 가리키고 있습니다.

2. 단순연결 원형 리스트

앞서 봤던 단순 연결 리스트와는 다르게 한방향으로 연결 된것은 같지만 제일 끝 노드에서 NULL로 끝나는 것이 아니라 다시 제일 앞 노드로 돌아와서 원형을 이루는 것이 특징입니다.

3. 이중연결 리스트(위에 있는 노드 구조체와는 조금 다른 구조체를 갖음)

각 노드가 앞 뒤를 가리키고 있어서 이중으로 연결되었다 하여 이중 연결 리스트라고 합니다. 이중 연결 리스트에서는 단순 연결 리스트와 같이 제일 뒤에 NULL이 들어가며 다른 점으론 첫 노드의 이전도 없는 것이므로 NULL이 들어갑니다.

4. 이중연결 원형 리스트(위에 있는 노드 구조체와는 조금 다른 구조체를 갖음)

단순 연결 원형 리스트 처럼 마지막 노드의 다음 노드는 첫 노드가 되고 또한 첫 노드의 이전 노드는 마지막 노드가 되는 구조로 원형을 이루는 것이 특징입니다.

이번에는 순차 리스트와 동적 연결 리스트를 비교해 보겠습니다.

순차 리스트(배열)은 같은 연속된 공간에 데이터 들이 들어가 있음을 확인 할 수 있습니다.

그림상으론 연속적으로 보이게 표현은 해놨지만 동적연결 리스트는 포인터를 이용하여 임의의 위치의 노드들의 순서를 넣어주어 리스트를 구성합니다.

다음 포스팅에는 단순연결리스트를 구현해 보도록 하겠습니다.

같이 보기

2016/01/22 - [Programming/STL] - STL(Standard Template Library) - Container - List

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 이중 원형 연결 리스트

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 단순 원형 연결 리스트

2015/11/06 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(2/2)

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(1/2)

2015/11/02 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 배열