티스토리 뷰
이중 원형 연결 리스트
원형 이중 연결 리스트란 각 노드가 두 개의 포인터를 가지며, next 포인터는 리스트에서 다음 노드를 가리키고, prev 포인터는 리스트에서 이전 노드를 가리키는 이중 연결리스트를 기반으로 한다.
여기에 추가해서,
마지막 노드의 next 포인터가 NULL을 가리키는게 아니라
(head포인터가 가리키는) 첫 번째 노드를 가리키며,
첫 번째 노드의 prev 포인터는 마지막 노드를 가리킴으로써 원형 구조를 만듭니다.(무한 싸이클 느낌ㅋㅋ)
이중 원형 연결 리스트의 장점
1. 노드를 삽입하거나 삭제하는 등의 작업이 리스트의 크기와 관계없이 상수 시간 O(1)으로 수행가능
why? 인접한 노드의 포인터만 업데이트해주면 됨
2. 데이터 정렬(sort) 가능
이중원형 연결리스트는 개인적으로 연결리스트를 공부하면서 가장 까다롭다고 느낀 리스트다.
이전까지의 단일, 원형, 이중연결리스트를 이해한 상태에서 공부하는걸 추천한다.
신경써야할 예외적인 사항도 몇가지 존재하지만, 정말 말그대로 이중+원형에서 각각 주의할점만 잘지키면 된다.
리스트를 마지막으로 다루며 정리하는 느낌으로 직접 만들어 보았다.
노드와 리스트를 구성하는 방식은 지금까지 포스팅했던것과 동일한 방식이다.
윤성우님의 자료구조 교재를 기반으로 만들었다.
노드와 리스트에 필요한 포인터를 정의하는 방식은 동일하며
typedef struct _node{
int data;
struct _node * prev; //다음 노드의 주소
struct _node * next; //이전 노드의 주소
}Node;
typedef struct _dbLinkedList{
Node * head; //첫번째 노드 주소 저장
Node * cur; //순회용 포인터
int numOfData; //노드 총 개수
}DbLinkedList;
typedef DbLinkedList List;
함수를 12개로 나누어 분류했다.
리스트 생성 함수 1개
삽입은 3개 - 맨앞/맨뒤/N번째
삭제는 4개 - 맨앞/맨뒤/N번째/전체
(오름차순) 정렬 함수 1개
조회는 2개 - 순행/역순
총노드의 개수를 구하는 함수 1개
총 12개의 ADT를 정의하여 구현하였다.
void ListInit(List * plist); //리스트 생성
void InsertFront(List * plist, int data); //맨앞삽입
void InsertRear(List * plist, int data); //맨끝삽입
void InsertFrontNth(List * plist, int index, int data); //N번째 삽입
void DeleteFront(List * plist);//맨앞 데이터 삭제
void DeleteRear(List * plist); //맨뒤 데이터 삭제
void DeleteFrontNth(List * plist, int index); //N번째 데이터 삭제
void DeleteAll(List * plist); //모든 데이터 삭제
void Display(List * plist); //순회
void DisplayReverse(List * plist); //역순 순회
int GetNodeCount(List * plist); //총 노드 개수
void sort(List * plist); //정렬 함수
이전의 리스트까지의 이해가 잘되었다면 함께 구현해봐도 좋을 것 같다.
C언어로 이중 원형 연결 리스트까지 다루는 블로그는 많지 않다고 생각해
Sanfoundry에서 구현한걸 참조해 만들어 보았다.
아래코드는 최선의 코드는 아니지만 한번 만들어보면
리스트를 더 잘 이해할 수 있게 되고, 보다 자유롭게 다룰 수 있게 된다고 생각한다.
아래의 모델은 이중 원형 연결리스트에서 맨앞에 노드를 삽입하는 방법이다
아래처럼 그림을 그려서 보면
구현이 까다로웠던 N번째삽입과 N번째 삭제 함수도 구현 가능하다.
간과하면 안될것은 이중 연결리스트가 기반인건 맞지만
맨 마지막 노드의 next는 맨처음노드의 주소가 들어가야 한다는 점,
맨 처음 노드의 prev는 맨마지막 노드의 주소가 들어가야 한다는 점이다(원형 연결리스트 특징)
sanfoundry의 모델이 좋아보여 가져왔다.
N번째 삽입과 삭제도 위 링크에는 아래처럼 그림으로 표현되어있다
직접 그려봐도 모르겠다면 확인해보는게 실력 향상에 도움이 될듯하다...
기본 ADT
#ifndef DoubleLinkedList_h
#define DoubleLinkedList_h
#define TRUE 1
#define FALSE 0
typedef struct _node{
int data;
struct _node * prev; //다음 노드의 주소
struct _node * next; //이전 노드의 주소
}Node;
typedef struct _dbLinkedList{
Node * head; //첫번째 노드 주소 저장
Node * cur; //순회용 포인터
int numOfData; //노드 총 개수
}DbLinkedList;
typedef DbLinkedList List;
void ListInit(List * plist); //리스트 생성
void InsertFront(List * plist, int data); //맨앞삽입
void InsertRear(List * plist, int data); //맨끝삽입
void InsertFrontNth(List * plist, int index, int data); //N번째 삽입
void DeleteFront(List * plist);//맨앞 데이터 삭제
void DeleteRear(List * plist); //맨뒤 데이터 삭제
void DeleteFrontNth(List * plist, int index); //N번째 데이터 삭제
void DeleteAll(List * plist); //모든 데이터 삭제
void Display(List * plist); //순회
void DisplayReverse(List * plist); //역순 순회
int GetNodeCount(List * plist); //총 노드 개수
#endif각 함수 구현
#include <stdio.h>
#include <stdlib.h>
#include "DoublyCircularLinkedList.h"
//리스트 생성
void ListInit(List * plist){
plist -> head = NULL;
plist -> cur = NULL;
plist -> numOfData = 0;
}
//맨앞 삽입
void InsertFront(List * plist, int data){
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
newNode -> prev = NULL;
newNode -> next = NULL;
//1. 첫 노드일 경우
if(plist -> head == NULL){
//원형연결리스트의 첫 노드 삽입시 생각하기
newNode -> prev = newNode;
newNode -> next = newNode;
plist -> head = newNode;
(plist -> numOfData)++;
return;
}
//2. 첫 노드가 아닐경우
//첫번째 위치한 노드를 삽입하는거니까 맨뒤 노드와의 연결을 다시하기
plist -> head -> prev -> next = newNode; //맨마지막 노드를 newNode와 연결
newNode -> prev = plist -> head -> prev; //newNode와 맨 마지막 노드 연결
newNode -> next = plist -> head; //newNode와 기존의 맨처음 노드 연결
plist -> head -> prev = newNode; //기존의 맨처음 노드와 newNode 연결
plist -> head = newNode; //head 위치 변경
(plist -> numOfData)++;
}
//맨뒤 삽입
void InsertRear(List * plist, int data){
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
newNode -> prev = NULL;
newNode -> next = NULL;
//1. 첫 노드일 경우
if(plist -> head == NULL){
//원형연결리스트의 첫 노드 삽입시 생각하기
newNode -> prev = newNode;
newNode -> next = newNode;
plist -> head = newNode;
(plist -> numOfData)++;
return;
}
//2. 첫 노드가 아닐경우
//맨뒤에 노드를 삽입하는거니까 맨처음 노드와의 연결을 다시하기
newNode -> prev = plist -> head -> prev;
newNode -> next = plist -> head;
plist -> head -> prev -> next = newNode;
plist -> head -> prev = newNode;
(plist -> numOfData)++;
}
//N번째 삽입시
void InsertFrontNth(List * plist, int index, int data){
//1. 첫번째에 삽입하는 경우
if(index == 1)
InsertFront(plist, data);
//2. 마지막에 삽입하는 경우
else if(index == GetNodeCount(plist) + 1)
InsertRear(plist, data);
//3.생성한 노드가 없는데 2번째 이상의 자리에 삽입하고 싶을때
else if(plist -> head == NULL && index > 1){
printf("구성된 노드가 없습니다(잘못된 접근).\n");
return;
}
//4.노드는 생성되어 있으나, 기존 노드 개수를 초과하는 자리에 넣고 싶을때(기존의 노드로 구성된 리스트와 삽입할 노드사이에 공백이 생김)
else if(plist -> head != NULL && index > GetNodeCount(plist) + 1){
printf("index가 노드 개수를 초과합니다(잘못된 접근).\n");
return;
}
else{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
newNode -> prev = NULL;
newNode -> next = NULL;
plist -> cur = plist -> head;
Node * before = NULL;
int i = 1;
while(++i <= index){
before = plist -> cur;
plist -> cur = plist -> cur -> next;
}
//1 2 3
//자리를 찾았으니
before -> next = newNode; //그 이전 노드와 newNode
newNode -> prev = before; //newNode와 그 이전노드
newNode -> next = plist -> cur; //newNode와 그 다음노드
plist -> cur -> prev = newNode; //그 다음노드와 newNode
(plist -> numOfData)++;
}
}
//맨앞의 노드 삭제
void DeleteFront(List * plist){
if(plist -> head == NULL){
printf("구성된 노드가 없습니다.\n");
return;
}
if(plist -> head -> next == NULL){
free(plist -> head);
printf("1개 남은 노드 삭제!\n");
(plist -> numOfData)--;
return;
}
Node * delNode = plist -> head;
plist -> head -> prev -> next = plist -> head -> next; //맨 마지막과 삭제할 맨앞의 다음 노드
plist -> head -> next -> prev = plist -> head -> prev; //삭제할 맨앞의 다음 노드와 마지막 노드
plist -> head = plist -> head -> next;
int removeData = delNode -> data;
printf("%d 삭제\n", removeData);
free(delNode);
(plist -> numOfData)--;
delNode = NULL;
}
//맨뒤의 노드 삭제
void DeleteRear(List * plist){
if(plist -> head == NULL){
printf("구성된 노드가 없습니다.\n");
return;
}
if(plist -> head -> next == NULL){
free(plist -> head);
printf("1개 남은 노드 삭제!\n");
(plist -> numOfData)--;
return;
}
Node * delNode = plist -> head -> prev; //마지막 노드 설정
delNode -> prev -> next = plist -> head; //삭제할 마지막 노드의 이전노드와 head노드 연결
plist -> head -> prev = delNode -> prev; //head노드와 삭제할 마지막 노드의 이전노드 연결
int removeData = delNode -> data;
free(delNode);
printf("%d 노드 삭제\n", removeData);
(plist -> numOfData)--;
delNode = NULL;
}
//N번째 노드 삭제
void DeleteFrontNth(List * plist, int index){
if(plist -> numOfData == 0)
{
printf("구성된 노드가 없습니다.\n");
return;
}
//1. 첫번째 노드 삭제하는 경우
if(index == 1)
DeleteFront(plist);
//2. 마지막노드 삭제하는 경우
// else if(index == GetNodeCount(plist) + 1)
//RemoveRear(plist);
//3. 노드의 개수를 초과하는 인덱스의 노드를 삭제하고싶을때
else if(plist -> head != NULL && index > GetNodeCount(plist) + 1){
printf("선택한 index에 노드는 존재하지 않습니다.\n");
return;
}
else{
int removeData;
Node * delNode = plist -> head;
Node * before = NULL;
int i = 1;
while(i < index){
before = delNode;
delNode = delNode -> next;
i++;
}
before -> next = delNode -> next;
delNode -> prev = before;
removeData = delNode -> data;
free(delNode);
(plist -> numOfData)--;
printf("%d노드 삭제\n", removeData);
delNode = NULL;
}
}
//모든 노드 삭제
void DeleteAll(List * plist){
if(plist -> numOfData == 0)
{
printf("구성된 노드가 없습니다.\n");
return;
}
Node * delNode = plist -> head;
while (plist -> numOfData != 0) {
plist -> head = plist -> head -> next;
printf("%d 노드 삭제\n", delNode -> data);
free(delNode);
(plist -> numOfData)--;
delNode = plist -> head;
}
}
//순행 조회
void Display(List * plist){
if (plist -> numOfData == 0) {
printf("구성된 노드가 없습니다.\n");
return;
}
plist -> cur = plist -> head;
do
{
printf("%d ", plist -> cur ->data);
plist -> cur = plist -> cur -> next;
}while(plist -> cur != plist -> head);
}
//역순 조회
void DisplayReverse(List * plist)
{
if (plist -> numOfData == 0) {
printf("구성된 노드가 없습니다.\n");
return;
}
plist -> cur = plist -> head -> prev; //마지막 노드로 지정
do
{
printf("%d ", plist -> cur ->data);
plist -> cur = plist -> cur -> prev;
}while(plist -> cur != plist -> head -> prev);
}
void sort(List * plist)
{
if (plist -> numOfData == 0) {
printf("구성된 노드가 없습니다.\n");
return;
}
int sortingData;
Node * temp1 = plist -> head;
Node * temp2 = plist -> head;
do{
temp2 = temp1->next; //한발 앞서나간다
while(temp2 != plist ->head)
{
if (temp1->data > temp2->data) //앞에 노드가 뒤에노드보다 커?
{
sortingData = temp1->data;
temp1->data = temp2->data;
temp2->data = sortingData;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}while (temp1->next != plist -> head); //제자리로 돌아오기전까지
}
int GetNodeCount(List * plist){
if(plist -> numOfData == 0)
{
printf("노드가 0개입니다\n");
}
return plist -> numOfData;
}
Main 함수
system("cls")와
system("pause)함수는
선택것 선언 하기
#include <stdio.h>
#include <stdlib.h>
#include "DoublyCircularLinkedList.h"
int main(){
List list;
int data, choice,index;
ListInit(&list);
while (1)
{
//system("cls"); //할지 말지는 옵션!
printf("\n\n\n\t\t 이중 원형 연결 리스트(doubly Circular linked list) \n\n\n");
printf("\t\t 1. 노드 맨 앞 삽입\n");
printf("\t\t 2. 노드 맨 뒤 삽입\n");
printf("\t\t 3. 노드 N번째 삽입\n");
printf("\t\t 4. 순행 조회\n");
printf("\t\t 5. 역순 조회\n");
printf("\t\t 6. 맨 앞 노드 삭제\n");
printf("\t\t 7. 맨 뒤 노드 삭제\n");
printf("\t\t 8. N번째 노드 삭제\n");
printf("\t\t 9. 전체 노드 삭제\n");
printf("\t\t10. 총 노드의 개수 구하기\n");
printf("\t\t11. (오름차순)정렬 하기\n");
printf("\t\t 0. 프로그램 종료\n");
printf("\n\n메뉴 선택 : ");
scanf("%d", &choice);
while (getchar() != '\n');
switch (choice)
{
case 1: printf("데이터 입력: ");
scanf("%d", &data);
InsertFront(&list, data);
break;
case 2: printf("데이터 입력: ");
scanf("%d", &data);
InsertRear(&list, data);
break;
case 3: printf("데이터 입력: ");
scanf("%d", &data);
printf("몇번째 삽입 하시겠습니까? : ");
scanf("%d", &index);
InsertFrontNth(&list, index, data);
break;
case 4: Display(&list);
break;
case 5: DisplayReverse(&list);
break;
case 6: DeleteFront(&list);
break;
case 7: DeleteRear(&list);
break;
case 8: printf("몇번째 데이터를 삭제하시겠습니까? ");
scanf("%d", &index);
DeleteFrontNth(&list, index);
break;
case 9 : DeleteAll(&list);
break;
case 10: printf("총 노드 개수: %d\n", GetNodeCount(&list));
break;
case 11: printf("정렬하였습니다.\n");
sort(&list);
break;
case 0: printf("프로그램을 종료합니다.\n");
exit(-1);
}
//system("pause"); //결과 확인(할지 말지는 옵션!)
}
return 0;
}
반응형
'TIL [자료구조&알고리즘]' 카테고리의 다른 글
| 원형 연결 리스트(CircleLinkedList) (0) | 2023.03.06 |
|---|---|
| 4. 더미노드 있는 연결 리스트(DummyLinkedList) (0) | 2023.03.05 |
| 3. 단일 연결 리스트(SingleLinkedList) (0) | 2023.03.05 |
| 2. 배열 리스트(ArrayList) (0) | 2023.03.02 |
| 1. 알고리즘 성능 분석 수단(Time Complexity, Big O) (0) | 2023.02.28 |
댓글