배열 커서로 연결 리스트 만들기

지난 글 : [알고리즘/Do it 알고리즘] - 포인터로 연결 리스트 만들기

 

배열 커서로 연결 리스트 만들기

이전 글에서 배운 포인터를 이용한 연결 리스트는 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'는 장점이 있지만 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 확보하고 해제하는 과정이 필요하다. 메모리 영역을 확보하고 해제하는 데 드는 비용은 절대 무시할 수 없다. 프로그램 실행 중 수가 크게 바뀌지 않는 경우, 또는 데이터 수의 최댓값을 미리 알 수 있는 경우 배열을 사용해 연결 리스트를 만들면 효율적으로 운용할 수 있다. 

 

여기서 다음 노드를 가리키는 뒤쪽 포인터는 다음 노드에 대한 포인터가 아니라 당므 노드가 들어 있는 배열 요소의 인덱스다. 이 인덱스 포인터를 커서(cursor)라 한다. 꼬리 노드의 커서는 배열의 인덱스가 될 수 없는 값인 -1로 한다. 머리 노드를 나타내는 head도 커서이기에 머리 노드가 들어 있는 곳인 인덱스값이 head값이 된다. 이와 같은 방법을 사용하면 노드를 삽입하거나 삭제할 때 요소를 옮길 필요가 없다. 

 

아래는 이런 방식으로 구현한 프로그램이다.

배열의 비어 있는 요소 처리하기

위에 작성한 프로그램의 각 메서드는 이전 글에서 구현한 프로그램의 메서드와 일대일로 대응한다. 두 프로그램 사이에서 가장 다른 부분인 '삭제한 노드 관리'에 대해 더 자세히 알아보자.

 

a)

head
 ↓
 A(1) → B(3) → C(0) → D(2)	//() 안의 숫자는 인덱스를 뜻함.

오른쪽은 숫자는 커서

 

b)

head
 ↓
 E(4) → A(1) → B(3) → C(0) → D(2)	//노드 E를 삽입

 

c)

head
 ↓
 E(4) → A(1) → C(0) → D(2)	//노드 B를 삭제

해석

a) 연결 리스트에 4개의 노드가 A  → B → C → D 순으로 나열되어 있다.

 

b) 연결 리스트의 머리에 노드 E를 삽입한 후의 상태다. 인덱스가 4인 위치에 노드 E가 들어 있다. 삽입한 노드는 배열 안에서 가장 꼬리 쪽에 있는 인덱스 위치에 들어가 있지만 연결 리스트의 꼬리에 추가한 것은 아니다. 당연히 배열 안에서의 물리적 위치 관계와 연결 리스트의 논리적 순서 관계가 같은 것은 아니다. 즉, 리스트의 n번째 노드가 배열의 인덱스가 n인 요소에 있는 것은 아니다. 앞으로 리스트 순서와 구별하기 위해 인덱스가 n인 요소에 들어 있는 노드를 'n번째 레코드'라 하자. 예로 b에서 삽입한 노드 E는 4번째 레코드에 있다.

 

c) 머리부터 3번째 노드 B를 삭제한 후의 상태다. 노드를 삭제하면 3번째 레코드가 비어 있는 상태가 된다.

 

그런데 삭제를 여러 번 반복하면 배열 안은 빈 레코드 투성이가 된다. 삭제한 레코드가 하나라면 그 인덱스를 어떤 변수에 넣어 두고 관리함으로써 그 레코드를 쉽게 재사용할 수 있다. 그러나 실제로는 여러 레코드를 삭제하는 경우가 많으므로 그리 단순히 해결되지는 않는다.

 

프리 리스트 살펴보기

이 프로그램에서는 삭제한 여러 레코드를 관리하기 위해 그 순서를 넣어 두는 연결 리스트인 프리 리스트(free list)를 사용한다. 데이터의 순서를 나타내는 연결 리스트와 프리 리스트가 결합되어 있으므로 노드 클래스 Node<E>와 연결 리스트 클래스 ArrayLinkedList<E>에 포인터 버전에는 없는 필드가 추가되어 있다.

 

노드 클래스 Node<E>에 추가된 필드

- dnext : 프리 리스트에서 뒤쪽 포인터(프리 리스트의 다음 노드를 가리키는 커서)이다.

 

연결 리스트 클래스 ArrayLinkedList<E>에 추가된 필드

- deleted : 프리 리스트의 머리 노드를 가리키는 커서다.
- max : 배열에서 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호다.

 

a)

head
 ↓
 A(2) → B(6) → C(0) → D(7) → E(4)
 
deleted
   → 3 → 1 → 5		//프리 리스트(삭제한 레코드를 관리)

 

b)

head
 ↓
 A(2) → B(6) → C(0) → D(7) → E(4) → F(3)		//노드 F를 삽입
 
deleted
   → 1 → 5

 

c)

head
 ↓
 A(2) → B(6) → C(0) → E(4) → F(3)		//노드 D를 삭제
 
deleted
   → 7 → 1 → 5

 

해석

a) 연결 리스트에 노드 5개가 {A  → B  → C  → D  → E} 순으로 저장돼 있다. max값은 7이며, 8번째 레코드 이후는 아직 사용하지 않은 상태다. 그리고 레코드 1, 3, 5는 이미 삭제를 마친 빈 레코드이고, 프리 리스트는 {3  → 1  → 5}이다. 위 그림에서는 데이터를 저장하는 연결 리스트(배열) 외에 프리 리스트를 위한 공간을 추가해 삭제한 레코드까지 관리하는 연결 리스트를 나타내고 있다. 연결 리스트 클래스 ArrayLinkedList<E>의 필드 deleted값 3은 프리 리스트의 머리 노드 인덱스다.

 

b) 연결 리스트 꼬리에 노드 F를 삽입한 후의 상태다. 노드를 삽입하는 위치는 삽입하기 전([a]) 프리 리스트의 머리 노드인 인덱스 3이다. 노드 F를 3번째 레코드에 저장하고 프리 리스트 {3  → 1  → 5}에서 머리 노드 3을 삭제해 {1  → 5} 상태로 만든다. 이처럼 프리 리스트에 빈 레코드가 등록되어 있는 한 '새 레코드를 얻기 위해 max값을 증가시킨 다음 그 레코드에 데이터를 저장하는 일'은 하지 않는다. 그러므로 max갑은 8이 아니라 7이다.

 

c) 노드 D를 삭제한 다음의 상태다. 삭제한 노드 D의 배열 인덱스가 7이므로 7을 프리 리스트의 머리 노드로 등록한다. 그 결과 프리 리스트는 {7  → 1  → 5}의 상태가 된다.

 

삭제한 레코드를 프리 리스트에 등록하는 메서드는 deleteIndex이고, 노드를 삽입할 때 레코드 번호를 가져오는 메서드는 getInsertIndex이다. 위 b)의 경우 이미 삭제한 레코드가 있으므로 프리 리스트에 등록된 레코드 중 삽입할 레코드를 가져온다. 만약 삭제한 레코드가 없어 프리 리스트가 비어 있다면 max를 증가시켜 배열 꼬리 쪽의 아직 사용하지 않은 새 레코드를 사용한다.

 

배열 커서로 연결 리스트를 사용하는 프로그램 만들기

 

아직 제대로 된 프로그램도 아닌 위 코드를 구현하며 뿌듯함을 느꼈다. 후에 다른 사람과 협업하며 프로젝트를 진행할 때의 성취감은 어떨지 상상도 되지 않는다.

 

참고 서적 :