[Data Structure] 연결 리스트2(Linked List2)

이번 포스팅에서는 이전에 다뤘던 연결 리스트의 개념을 이용한 리스트인 원형 연결 리스트와 이중 연결 리스트에 대해 얘기해보려 합니다.

 

먼저 원형 연결 리스트입니다. 

원형 리스트는 기존의 단일 연결 리스트에서 마지막 노드가 NULL이 아닌 head가 가리키는 첫 번째 노드를 가리킨다는 것이 차이점입니다.

일반적인 연결 리스트에서는 link가 한 방향으로 흘러가기 때문에 마지막 노드는 무조건 NULL을 가리킵니다. 그러나 원형 연결 리스트에서는 위와 같은 구성을 띄게 함으로써 원형과 같은 형태로 구성합니다.

 

원형 연결 리스트에 있어서 주의할 부분은 딱 하나입니다. head를 가리키는 마지막 노드의 link에 대한 처리입니다. 

만약 insert를 해준다고 할 때, 중간에 값을 삽입하는 것은 기존과 같습니다. 그러나 첫 노드로 삽입할 때나, 마지막 노드로 삽입하는 경우에는 기존과는 코드가 달라집니다. 

 

원형 연결 리스트에서의 삽입 삭제에서 중요한 것은 과연 마지막 노드를 어떻게 찾을 건지입니다. 

왜냐하면 보통의 경우에는 첫 번째 노드부터 뒤로 쭉 검색을 할건데 원형이기 때문에 무한루프처럼 돌 수 있기 때문입니다. 이에 대한 해결은 간단합니다. 

L->head가 link인 노드를 for문을 통해 찾아주면 되겠다는 생각을 했습니다.

 

 insert에 대한 psuedo 코드입니다. 여기서는 temp를 두어 마지막 노드를 찾는 과정을 대체했습니다.

 

---

이중 연결 리스트

이중 연결 리스트는 앞으로의 덱이나 트리에서도 정말 자주 쓰이는 개념입니다.

이중 연결 리스트는 노드들이 서로서로 연결되어 있다는 것이 특징입니다. 즉, 쌍방향으로 연결되어 있습니다.

위와 같이 해주기 위해서는 link를 하나 더 만들어주면 됩니다. 기존에는 오른쪽으로 가는 link 하나만 있었다면 이번에는 이를 llink(left)와 rlink(right)로 나눠서 처리를 해주는 것입니다. 

 

이러한 방식에는 장단점이 있습니다. 

단점부터 말하자면 구현이 복잡할 수 있습니다. link가 하나 더 추가되는 것이기 때문에 기존의 삽입, 삭제에서 하나의 link를 더 고려해야 하기 때문입니다.

장점은 바로 특정 노드를 찾는 과정이 필요가 없어집니다. 앞선 연결 리스트나 원형 연결 리스트에서는 마지막노드나 이전 노드 등을 찾는 과정을 거쳤습니다. 그러나 이중 연결 리스트에서는 이런 것들을 할 필요가 없이 이전이면 llink로 마지막이면 rlink가 NULL인 걸로 찾으면 그만이기 때문입니다. 

 

100의 llink와 300의 rlink는 화살표로 표시는 하지 않았지만 모두 NULL을 가리킵니다. 첫 번째 노드의 rlink가 head를 가리키는 것이 아니니 주의 바랍니다.

 

이중 연결 리스트에서의 삽입, 삭제는 코드를 보면서 하겠습니다.

typedef int element;
typedef struct ListNode {
	element data;
    struct ListNode* llink;
    struct ListNode* rlink;
}listNode;

typedef struct DoubleList {
	listNode* head;
    int length;
}doubleList;

doubleList* initList() {
	L = (doubleList*)malloc(sizeof(doubleList));
    L->head = NULL;
    L->length = 0;
    return L;
}

int getlength(doubleList* L) {
	return L->length;
}

listNode* search(doubleList* L, element x) {
	listNode* newNode = (listNode*)malloc(sizeof(listNode));
    
    if(L->head == NULL)
    	return newNode;
    else {
    	newNode = L->head;
        while(newNode != NULL) {
        	if(newNode->data == x) {
            	return newNode;
            else {
            	newNode = newNode->rlink;
        }
    }
    return newNode;
}

void insert(doubleList* L, listNode* pre, element x) {
	listNode* newNode = (listNode*)malloc(sizeof(listNode));
    newNode->data = x;
    
    if(L->head == NULL) {
		newNode->llink = NULL;
        newNode->rlink = NULL;
        L->head = newNode;
    }
    else if(pre == NULL) {
        newNode->llink = NULL;
        newNode->rlink = L->head;
        L->head->llink = newNode;
        L->head = newNode;
    }
    else {
    	newNode->rlink = pre->rlink;
        newNode->llink = pre;
        pre->rlink = newNode;
        if(newNode->rlink != NULL)
        	newNode->llink->rlink = newNode;
    }
    L->length++;
}

int delete(doubleList* L, listNode* p) {
	
    if(L->head == NULL) return False;
    if(p == NULL) return False;
    
    if(L->head == p->data) {
		L->head = p->rlink;
        p->rlink->llink = NULL;
    }
    else {
        p->llink->rlink = p->rlink;
        if(p->rlink != NULL)
        	p->rlink->llink = pre;
        }
    }
    free(p);
    L->length--;
    return True;
}

위의 코드에서 insert와 delete를 보시면 예외적인 경우를 처리하는 것은 제외하고 밑을 보면 p->llink->rlink처럼 접근이 괴이한 경우가 생깁니다. 그러나 논리적으로 기존의 연결 리스트의 삽입, 삭제를 생각하면 편할 것 같습니다.