4. 메모리 최적화 이중 연결 리스트 알고리즘

1. 개요

 메모리 최적화 이중 연결 리스트의 아이디어는 충격적이다. 이를 작성하는 이유는 내게 너무나 생각의 폭을 한번 더

넓히게 만들어준 알고리즘이기 때문이다. 그리고 그 아이디어는 무척 간단하다.

 일반적인 이중 연결 리스트의 자료구조다.

 struct Node{

int data;

struct Node* prev; //이전 포인터

struct Node* next; //다음 포인터

 }

 위 자료구조는 당연하다.

 하지만 메모리 최적화 이중 연결 리스트는 위의 자료구조에서 2개의 포인터를 하나로 압축했다.

 메모리 최적화 이중 연결 리스트 자료구조다.

 struct Node{

int data;

struct Node* ptrdiff; //pointer difference의 약자

 }

 어떻게 이게 가능할까? 해답은 XOR 연산에 있다.

2. 풀이

 먼저 이 알고리즘을 위해 알아야 할 XOR 연산의 속성이다.

 (1) X XOR X = 0 (같으면 0이다.)

 (2) X XOR 0 = X (다르면 자기 자신이다.)

 (3) X XOR Y = Y XOR X (대칭이 성립한다.)

 (4) ( X XOR Y ) XOR Z = X XOR ( Y XOR Z ) (교환 법칙이 성립한다.)

 ptrdiff 포인터 변수에는 prev 포인터와 next 포인터의 XOR 연산의 결과이다.

 

 만약 A -> B -> C -> D -> NULL 이라는 리스트가 있고, 현재 위치가 B라면 

 B가진 ptrdiff의 값은 A의 주소와 C의 주소의 XOR 연산 값이다.

 ptrdiff = A XOR C 일 때, 

A 노드로 가기 위해서는 

( A XOR C ) XOR C => A XOR ( C XOR C ) => A XOR 0 => A 노드의 주소가 나타난다.

C 노드로 가기 위해서는 

( A XOR C ) XOR A => ( A XOR A ) XOR C => 0 XOR C => C 노드의 주소가 나타난다.

3. 결론

 정말 대단한 아이디어다. 그런데 ... 그런데 !! 이 포스트를 작성하다보니 하나 이해 안되는 부분이 있다. 이 자료구조에서 

알고있는 ptrdiff는 A XOR C 인데 이것과 연산하는 A의 주소와 C의 주소는 어떻게 알지????

 스승님!!???????

 이해가 안된다. 찾아봐도 안된다. 하지만 이 부분에 대한 이해는 다시 한 번 찾아보기로 하고 일단 넘긴다. 그러나 

중요한 것은 스승님께 쓰여있는 말이다.

 '최근에 삽입, 탐색, 그리고 삭제 동작을 가진 이중 연결 리스트 추상 자료형 대체 구현이 학술지에 제시됐다.'

라는 구절이다. 

 이 말은 스승님께서는 항상 학술지를 쳐다보며 새로운 알고리즘이 등장했는지 꾸준히 찾아보신다는 것이다.

이런 습관이 세계적인 개발자로 거듭나게 되는 방법인가보다. 그리고 영어가 왜 중요한지 알려주는 일이기도

하다. 

 이 글을 작성한 이유는 아직 명확하진 않더라도 이런 기법도 있다는 것과 스승님과 같은 습관을 그리고 

프로그래머로서의 자세를 배워서 이를 쓰기 위해서다. 계속 사고의 한계를 늘려가자!!