원형 이중 연결리스트

lsh950223·2020년 5월 7일
0

안녕하세요 c++을 공부하고있는 대학생입니다.
이번에는 연결리스트에 대해 정리 해 보았습니다.

연결리스트는 처음에 접근하면 정말 복잡한 문제인 것 같습니다.
그래서 하나하나 천천히 정리 해 보려고 합니다.

시작하기전에, 연결리스트의 장점이 무엇인지 정리 해 보았습니다.

  1. 삽입 , 삭제하기에 용이하다.
  1. 탐색 , 원하는 요소를 반환 할 수 있어 접근하기에 좋다.
  2. 필요 한 만큼의 동적할당 할 수 있다.

연결리스트 하면 보통 배열이랑 많이 엮어서 바라보기도 합니다.
배열은 검색이 연결리스트에 비해 빠르지만, 요소를 삭제 할 수 없습니다. 처음에 배열을 선언 할 때, heap에 선언한 만큼의 공간을 할당하기때문에 메모리 관점에서 필요없는 공간까지 할당하므로 낭비여서 상황에따라서는 연결리스트가 더 좋을 때가 많습니다.

물론 Hash라는 키 값에 따라 데이터를 직접적으로 참조하는 (선형 , 2차, 이중, 체이닝) 자료구조 도 있지만, Hash에 관해서는 추후에 또 정리 해 보도록 하겠습니다.

처음에 노드 와 리스트에 대하여 구조체를 선언합니다.

typedef struct Node {
	struct node *next;
    struct node *prev;
    int data;
}node;

typedef struct List {
	struct node *tail;
    int count;
}List;

그냥 일반적인 struct로 선언해도 되긴하지만, 저는 typedef 로 struct를 선언을 합니다. 컴파일러에 따라 다르지만, 일부 성능이 뒤떨어지는 컴파일러는 타입 선언 때문에 약간의 불편함이 있어서 그냥 typedef로 하는것이 더 좋은 것 같습니다.

그리고 list에 대해서 create 해주는 함수가 하나 필요합니다. 이 함수는 tail node를 시작점으로 해서 기준이 될 친구입니다.

List *Listinit() {
	List *list = (List *)malloc(sizeof(List));
    
    if(list == NULL) {
    	printf("err\n");
    }
    else {
    	list->tail = NULL;
        list->count = 0;
    }
    
    return list;
}

list에 대한 init 함수에 대해 정리 해 보겠습니다.

List *list = (List *)malloc(sizeof(List));

list에 대해 동적할당 한 것입니다.

    if(list == NULL) {
    	printf("err\n");
    }
    else {
    	list->tail = NULL;
        list->count = 0;
    }

list에 대해 동적할당이 성공하면 else문으로 빠져나가고, 초기 tail에는 아무것도 없어야하므로 NULL값을 넣어주고, count 라는 int형 상수를 0으로 초기화 시켜줍니다.

다음으로는 node를 집어넣는 함수에 대해서 설명 해 드리겠습니다.

void addlist(List *list, int count,int data);

List에 대해 포인터 선언 해주었고, count 상수는 노드에 할당된 개수를 의미합니다. 그리고 data는 노드에 들어갈 데이터를 의미합니다.

node *newNode = (node *)malloc(sizeof(node));
newNode->data = data;

새로운 노드를 동적할당으로 할당 해 주고, newNode의 data에 새로 넣을 데이터를 넣어줍니다.

if(list->count == 0) {
	list->tail = newNode;
    newNode->next = newNode;
    newNode->prev = newNode;
}

아직 한개의 노드도 만들어지지 않았다면, 새로 만든 노드는 자기자신이 tail이 되고, 자기 다음과 자기 이전의 노드 역시 자기 자신이 되어야합니다.

else {
	for(int i =0; i<count; i++) {
    	list->tail = list->tail->next;
    }

이 부분은 간단합니다. 노드를 삽입하기 위한 위치로 가기위해서, list->tail 부분이 기준점이므로 옮겨서 삽입하기위해 이동시켜주는 반복문 입니다.

	newNode->next = list->tail->next;
    newNode->prev = list->tail;
    list->tail->next = newNode;
    newNode->next->prev = newNode;
    

이 부분이 제가 생각할때에 가장 어려운부분이라 생각이 됩니다. 처음에 노드와 노드 사이에 들어가는 것이어서, 그림으로 그리자면,

이렇게 그려집니다. newNode가 새로 들어가야하기때문에, 이전에 있던 노드가 가르킨 next 부분을 newNode가 가리켜야합니다.(위의 반복문으로 list->tail->next 를 통해서 이전 노드를 가리킨 상태입니다.) 그러므로

newNode->next = list->tail->next;

가 됩니다.
prev 부분 또한, 이전노드를 가리켜야하므로,

newNode->prev = list->tail;

이렇게 위의 그림과정이 끝이나게 됩니다. 다음으로는 상호 연결을 하기 위해서,

이 과정을 진행해야하는데, 그림을 보면 간단합니다.

list->tail->next = newNode

list->tail 이 삽입 할 이전의 노드인 것은 위의 반복문으로 보여드렸으므로, list->tail->next 부분은 새로 추가할 노드에 연결 해 주고,

newNode->next->prev = newNode;

새로 추가할 노드 다음 노드의 이전은 새로 추가할 노드 자기자신을 가리키면 위의 그림처럼 됩니다.

마지막으로,

if(list->count == count) {
	list->tail = newNode;
}

만약 새로 추가한 노드가 끝 노드가 된다면 이 노드가 tail이 되게 하기위한 조건문 입니다.

list->count = list->count + 1;

count의 개수를 늘려줍니다.

addlist 에 대한 코드입니다.

void addlist(List *list, int count,int data) {
	node *newNode = (node *)malloc(sizeof(node));
	newNode->data = data;
    
    if(list->count == 0) {
	list->tail = newNode;
    newNode->next = newNode;
    newNode->prev = newNode;
    }
    
   	newNode->next = list->tail->next;
    newNode->prev = list->tail;
    list->tail->next = newNode;
    newNode->next->prev = newNode;
    
    if(list->count == count) {
	list->tail = newNode;
    }
    
    list->count = list->count + 1; 
}

다음은 삭제 코드입니다.

void delNode(List *list,int index) {
	node *delNode = list->tail;
	if(list->count == 0) {
    	printf("err\n");
        return;
    }
    else {
    	for(int i = 0; i<index; i++) {
        	list->tail = list->tail->next;
        }
        delNode = list->tail->next;
        list->tail->next = delNode->next;
        delNode->next->prev = list->tail;
        free(delNode);
        
        if(index == list->count - 1) {
        	list->tail = list->tail;
        }
        
        list->count = list->count - 1;
    }
    
    if(list->count > index)
    {
   	for(int i =index; i<list->count; i++) {
    	    list->tail = list->tail->next;
	}
    }
    else {
	for(int i =list->count; i<index; i++) {
			list->tail = list->tail->next;
		}
	}
}

노드삭제는 간단합니다 아까처럼 list->count가 0이라면, 삭제 할 노드가 없으므로 err문을 띄우고, return 해주는식으로 종료를 하며,
else 문에서 for문을 통해 삭제할 노드 앞으로 이동시킨다음

이 그림처럼 만들어주면 됩니다.

delNode = list->tail->next;
list->tail->next = delNode->next;
delNode->next->prev = list->tail;

이 코드를 보면, 아까 for문으로 옮겨준 list->tail 에서 다음 노드를 삭제시키는 것 이기떄문에 , delNode = list->tail->next로 가리킨다음,
list->tail->next 는 delNode가 원래 가리켰던 next를 가리키고,
delNode->next->prev 를 아까 for문에서 옮겨준 list->tail 을 가리키면 위의 그림이 완성이 됩니다. 왜냐하면 아까 newNode가 자기자신을 가리킬때, newNode->next->prev = newNode 라고 한것을 생각하면 이해가 됩니다.

    if(list->count > index)
    {
   		for(int i =index; i<list->count; i++) {
    		list->tail = list->tail->next;
		}
	}
	else {
		for(int i =list->count; i<index; i++) {
			list->tail = list->tail->next;
		}
	}

tail부분을 다시 마지막으로 이동시켜주는 반복문입니다.

마지막으로 print문을 뽑아보겠습니다.

void Print(List *list) {
	int i;
    node *printNode;
    
    if(list->count == 0) {
    	printf("err\n");
        return;
    }
    
    for(i = 0,printNode = list->tail->next; i < list->count; 
    i++ ,printNode = printNode->next) {
            printf("[ %d ] ",printNode->data);
    }
}

print문은 간단합니다. next로 움직여가면서 출력을 해 주면 되기때문입니다.
reverse 출력도 for문만 살짝 바꾸면됩니다.

for(i = list->count , printNode = list->tail; i >0; 
    i--, printNode = printNode->prev) {
        printf("[ %d ] ",printNode->data);
   	}

그럼 마지막으로 풀 코드를 보여드리면서 마무리 해 보겠습니다.

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

typedef struct node {
	struct node *next;
	struct node *prev;
	int data;
}node;

typedef struct list {
	struct node *tail;
	int count;
}List;

List *Listinit() {
	List *list = (List *)malloc(sizeof(List));
    
    if(list == NULL) {
    	printf("err\n");
    }
    else {
    	list->tail = NULL;
        list->count = 0;
    }
    
    return list;
}

void addlist(List *list, int count,int data) {
	node *newNode = (node *)malloc(sizeof(node));
	newNode->data = data;
    
    if(list->count == 0) {
	list->tail = newNode;
    newNode->next = newNode;
    newNode->prev = newNode;
    }
    
   	newNode->next = list->tail->next;
    newNode->prev = list->tail;
    list->tail->next = newNode;
    newNode->next->prev = newNode;
    
    if(list->count == count) {
	list->tail = newNode;
    }
    
    list->count = list->count + 1; 
}

void delNode(List *list,int index) {
	node *delNode = list->tail;
	if(list->count == 0) {
    	printf("err\n");
        return;
    }
    else {
    	for(int i = 0; i<index; i++) {
        	list->tail = list->tail->next;
        }
        delNode = list->tail->next;
        list->tail->next = delNode->next;
        delNode->next->prev = list->tail;
        free(delNode);
        
        if(index == list->count - 1) {
        	list->tail = list->tail;
        }
        
        list->count = list->count - 1;
    }
    if(list->count > index)
    {
   		for(int i =index; i<list->count; i++) {
    		list->tail = list->tail->next;
		}
	}
	else {
		for(int i =list->count; i<index; i++) {
			list->tail = list->tail->next;
		}
	}
}

void Print(List *list) {
	int i;
    node *printNode;
    
    if(list->count == 0) {
    	printf("err\n");
        return;
    }
    
    for(i = 0,printNode = list->tail->next; i < list->count; 
    i++ ,printNode = printNode->next) {
            printf("[ %d ] ",printNode->data);
    }
}

void reversePrint(List *list) {
	int i;
	node *printNode;
	
	if(list->count == 0) {
		printf("none list\n");
		return;
	}
	
	for(i = list->count , printNode = list->tail; i >0; 
    i--, printNode = printNode->prev) {
        printf("[ %d ] ",printNode->data);
   	}
}

int main() {
	List *list = Listinit();
	
	node node;
	int deletePosition;
	int countlist = 0;
	int data=0;
	while(1)
	{
		scanf("%d",&data);
		if(data == -1) break;
		else addlist(list,countlist++,data);
	}
	printf("delete\n");

	while(1) {
		scanf("%d",&deletePosition);
		if(deletePosition == -1) break;
		else delNode(list,deletePosition); countlist--;
	}
	printf("\n\n");
	printf("reverse output\n");
	reversePrint(list);
	
	printf("\n\n");
	printf("output\n");
	Print(list);
	
	return 0;
}

결과입니다. 1부터 12까지 넣어준 후, delete로 9번째요소를 삭제하여 숫자 10이 제거된 모습입니다.

다시 정리차원에서 한번 코드를 짜 보았는데, 역시 자료구조는 그림을 그리면서 생각을 해야하구나 싶었습니다. 기억이 잘 나지않아서 블로그도 보고, 책도 보고 다시 깊게 공부했던거 같습니다.

profile
C++ 공부하고있는 대학생입니다.

0개의 댓글