[자료구조] 이중연결리스트

목차

이번 과제는 하나의 링크를 사용하고도 양방향으로 이동할 수 있는 방법에 관한 것이다.
이 방식을 두 방법이 있는데, 이번 과제는 XOR를 사용하여 이동한다.
이 방법은 (a⊕b)⊕a = b, (a⊕b)⊕b = a라는 원리를 이용합니다.
각 노드의 링크는 양쪽 노드의 주소를 XOR하여 저장하고,
두 pointer 변수 pLeft와 pRIght를 사용하여 양방향으로 이동하면서 데이터를 처리한다.

본문내용

#include < stdio.h>
#include < stdlib.h>

#define XOR2(x, y) (Node *)((int)x ^ (int)y)
#define XOR3(x, y, z) (Node *)((unsigned int)x ^ (unsigned int)y ^ (unsigned int)z)

typedef struct node {
int cData;
struct node *link;
} Node, *NodePtr;

char *sCmnds[] = { // 명령어들 입니다.
"I 184", // 오른쪽 앞에 184를 가진 노드를 삽입
"R ", // 오른쪽으로 한번 이동
"I 194", // 오른쪽 앞에 194를 가진 노드를 삽입
"I 189", // 오른쪽 앞에 189를 가진 노드를 삽입
"R ", // 오른쪽으로 한번 이동
"I 192",
"M -2 ", // 왼쪽으로 2번 이동
"I 180",
"M 5 ", // 오른쪽으로 5번 이동

참고 자료

없음