이중 연결 리스트 - C언어 구현

오늘은 이중 연결 리스트의 로직을 C언어로 구현해보았습니다.

사실 학교 자료 구조 시간에 작성한 건데,

묵혀두기 아까워서 올립니다.

 

구현한 기능은

초기화

삽입(head 다음) 

삭제(head 다음)

연결리스트 출력

입니다.

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

struct Node //노트 구조체 선언
{
int data; //값 저장
struct Node* rlink; //선행 노드 포인터 선언
struct Node* llink; //후속 노드 포인터 선언
};


struct Node* head; //헤드 노드 선언(head의 rlink, llink 모두 NULL)

 

//노드 초기화
void init() {
head->rlink = head; //함수 초기화
head->llink = head; //함수 초기화
}

//삽입 함수
void insert(struct Node* before, int value) 
{
struct Node* new = (struct Node*)malloc(sizeof(struct Node)); //동적 메모리 할당(new)
new->llink = before; //할당된 노드의 선행 노드 포인터를 선행 노드의 주소로 지정
new->rlink = before->rlink; //할당된 노드의 후속 노드 포인터를 기존 선행 노드의 후속 노드 포인터로 지정
new->data = value; //값 삽입
before->rlink = new; //선행 노드의 후속 노드 포인터를 새로 할당된 노드의 주소로 지정
new->rlink->llink = new; //새로 할당된 노드의 후속 노드 포인터가 가르키는 노드의 선행 노드 포인터를 새로 할당된 노드의 주소로 지정
}

 

//삭제 함수
void delete(struct Node* removed) {
if (removed == head) return; //만약 삭제하려는 노드가 헤드라면 삭제가 불가능하니 Return
head->rlink = removed->rlink; //헤드 노드의 후속 노드 포인터를 지우려는 노드의 후속 노드 포인터로 지정
removed->rlink->llink = removed->llink; //지우려는 노드의 후속 노드 포인터의 선행노드 포인터
free(removed); //할당된 메모리 삭제
}

 

//출력 함수
void print_list() {
struct Node* p; //노드 선언
for (p = head->rlink; p != head; p = p->rlink) //헤드의 후속 노드 포인터로 시작해서 계속해서 값을 출력
{
printf("<- %d -> ", p->data);
}
printf("\n");
}

int main() {
head = (struct Node*)malloc(sizeof(struct Node));
init();
printf("삽입 단계\n");
for (int i = 0; i < 5; i++) {
insert(head,i);
print_list();
}

printf("\n삭제 단계\n");
for (int i = 0; i < 5; i++) {
delete(head->rlink);
print_list();
}
return 0;
}

 

혹시 이중 연결 리스트가 뭔지 모르는 사람을 위해,

이중 연결리스트는 연결리스트의 종류 중 하나로,

헤드 노드와 값을 저장하고 있는 노드들로 이루어집니다.

 

대략적인 노드의 구조는

선행 노드 포인터(rlink) | 값 저장 | 후속 노드 포인터(llink)

와 같은 형식으로 이루어집니다.

만약 10, 20의 값이 이중연결리스트에 들어가있다고 치면,

 

Head의 rlink | Head(얘는 무조건 NULL) | Head의 llink(10의 주소를 가르킴) -> 10의 rlink(Head의 주소 가르킴) | 10 | 10의 llink(20의 주소를 가르킴) -> 20의 rlink | 20 | 20의 llink(Head를 가르킴)

이런식으로 연결리스트 안에서 선행노드, 후속노드의 값을 쉽게 찾을 수 있도록 

만들어낸 것이 바로 이중 연결 리스트입니다.

 

**

이중 연결 리스트의 개념을 알아야 어떤 코드인지 이해가 가능합니다.

(사실 내가 구현 자체를 복잡하게 함)

**

감사합니당