.png)
안녕하세요. 김용성입니다.
오늘은 어제 말씀드린대로 이중 연결리스트에 대해서 포스팅하도록 하겠습니다.
이중 연결리스트
단순 연결 리스트에서는 구조상 특정 노드의 후속 노드를 찾기 쉽지만 선행 노드를 찾는 것이 매우 어렵습니다.
해당 노드의 구조에는 본인의 데이터와 후속 노드의 주소만 포함되어있기 때문이죠.
앞서 배운 원형리스트라고 할지라도 거의 전체 노드를 거쳐서 돌아와야 합니다. 따라서 양방향으로 자유롭게 데이터를 조회하는 응용 프로그램을 구축할 때 일반적인 연결 리스트 구조는 매우 부적합합니다.
이러한 문제점을 해결하기 위해서 하나의 노드가 선행 노드와 후속노드에 대한 두 개의 링크를 가지는 리스트를 고안하게 되었는데 이것이 바로 이중 연결리스트입니다.
하지만 이런 이중 연결리스트는 하나의 노드가 일반적인 연결리스트보다 많은 요소를 가지고 있는만큼 공간을 많이 차지하고, 코드 자체도 복잡해진다는 단점이 존재하니 잘 생각해서 사용해야 합니다.
이중 연결리스트 노드의 구조는 다음과 같습니다.
.png)
제가 앞서 말씀드린 선행 노드의 주소를 llink라고 표현하고 후속 노드의 주소를 rlink라고 표현하였을 때 이중 연결 리스트는 다음과 같은 관계를 항상 성립합니다.
p=p->llink->rlink=p->rlink->llink
이 관계는 매우 중요하니 반드시 알아두시길 바랍니다.
이번에는 이중 연결리스트 노드의 구조체를 만들어보도록 하겠습니다.
typedef int element;
typedef struct DListNode{
element data;
struct DListNode* llink;
struct DListNode* rlink;
}llink와 rlink의 의미에 대해 이해하셨다면 단순 연결리스트와 완전히 같은 방법으로 정의했다는 것 또한 눈치채실 수 있을겁니다.
이중 연결리스트의 기본적인 정의에 대해 알게되었고, 노드를 만들어보았다면 이번에는 관련 함수를 코드로 구현해보도록 하겠습니다.
이중 연결리스트 함수
구현해 볼 이중 연결리스트의 함수로는 다음과 같은 것들이 있습니다.
- dinsert() : 리스트의 시작 부분에 항목을 삽입하는 함수(이중 연결리스트이므로 d를 붙임)
- ddelete() : 리스트의 중간 부분에 항목을 삽입하는 함수(이중 연결리스트이므로 d를 붙임)
dinsert()
새로운 데이터를 노드 prev의 오른족에 삽입하는 함수인 dinsert()를 먼저 만들어보도록 하겠습니다.
여기서 중요한 팁은 새로 만들어지는 노드의 링크에 먼저 변경 후의 값을 할당해주는 것입니다. 새로 만들어진 노드의 링크는 아무런 정보도 가지고 있지 않기 때문입니다.
void dinsert(DListNode *prev,element data)
{
dListNode *newnode=(DListNode *)malloc(sizeof(DListNode));
newnode->data=data;
newnode->llink=prev;
newnode->rlink=prev->rlink; // 1
prev->rlink->llink=newnode; // 2
prev->rlink=newnode; // 3
}제가 주석으로 숫자를 넣어놓았는데요.
설명하자면 다음과 같습니다.
1, 여기까지 newnode의 data 및 link값들 할당.
2, 기존 선행 노드의 후속 노드의 선행 노드를 newnode로 할당
3, 기존 선행 노드의 후속 노드를 newnode로 할당
말장난 같아서 조금 어렵게 느껴질 수 있는데, 차근차근 생각해보면 쉽게 느껴집니다.
선행 노드의 후속노드의 선행 노드가 원래 선행노드였는데, 지금은 새로 리스트안에 들어온 newnode로 변경되게 되는 것이죠.
마찬가지로 선행 노드의 후속 노드는 newnode가 들어오게 됨으로 후속 노드의 선행노드가 newnode가 되는 것입니다.
.png)
그림으로 설명한다고 만들어보았는데 사실 좀 마음에 들지 않네요 ㅠㅠ 참고 부탁드립니다.
ddelete()
이번에는 이중 연결리스트에서의 삭제함수를 만들어보도록 하겠습니다.
void ddelete(DListNode* head,DListNode* removed)
{
if(removed==head) return;
removed->llink->rlink=removed->rlink;
removed->llink->rlink=removed->rlink;
free(removed);
}위에 dinsert() 함수를 이해하셨다면 이 부분은 다소 쉽게 느껴지실거라 생각하기에 간단한 설명만 덧붙이도록 하게겠습니다.
removed라는 노드는 삭제될 노드이고 삭제될 노드의 선행 노드의 후속노드를 기존 removed의 후속노드로 변경해줍니다.
마찬가지로 removed 노드의 후속노드의 선행노드를 기존 removed의 선행노드로 변경해주면 되는 것이죠.
이중 연결리스트 구현
위에 기재한 dinsert(),ddelete() 함수 외에도 init, print_dlist 등이 존재하지만, 이는 앞선 연결 리스트 포스팅에서 했던 것과 매우 유사하므로 넘어가고 바로 전체 코드를 구현해보도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct DListNode{
element data;
struct DListNode* llink;
struct DListNode* rlink;
} DListNode;
void init(DListNode *phead){
phead->llink=phead;
phead->rlink=phead;
}
void print_list(DListNode* head)
{
DListNode* p;
for (p=phead->rlink;p!=phead;p=p->rlink){
print("<-||%d||->",p->data);
}
print("\n");
}
void dinsert(DListNode *prev,element data)
{
dListNode *newnode=(DListNode *)malloc(sizeof(DListNode));
newnode->data=data;
newnode->llink=prev;
newnode->rlink=prev->rlink;
prev->rlink->llink=newnode;
prev->rlink=newnode;
}
void ddelete(DListNode* head,DListNode* removed)
{
if(removed==head) return;
removed->llink->rlink=removed->rlink;
removed->llink->rlink=removed->rlink;
free(removed);
}
int main() {
DListNode* head=(DListNode *)malloc(sizeof(DListNode));
init(head);
printf("추가 단계\n");
for(int i=0;i<5;i++){
dinsert(head,i);
print_dlist(head);
}
printf("삭제 단계\n");
for(int i=0;i<5;i++){
print_dlist(head);
ddelete(head,head->rlink);
}
free(head);
return 0;
}실행 결과는 다음과 같습니다.
추가 단계
<-||0||->
<-||1||-> <-||0||->
<-||2||-> <-||1||-> <-||0||->
<-||3||-> <-||2||-> <-||1||-> <-||0||->
<-||4||-> <-||3||-> <-||2||-> <-||1||-> <-||0||->
삭제 단계
<-||4||-> <-||3||-> <-||2||-> <-||1||-> <-||0||->
<-||3||-> <-||2||-> <-||1||-> <-||0||->
<-||2||-> <-||1||-> <-||0||->
<-||1||-> <-||0||->
<-||0||->
맨 마지막에 삽입된 노드부터 삭제되었다는 점을 확인하시면 좋을 것 같습니다.
마무리
다음 포스팅은 아마 트리가 될 것 같습니다.
저는 개인적으로 트리가 정말 재미있더군요. 잘 준비해서 좋은 포스팅을 해보도록 하겠습니다.
읽어주셔서 감사합니다:)
