안녕하세요 c++을 공부하고있는 대학생입니다.
이번에는 연결리스트에 대해 정리 해 보았습니다.
연결리스트는 처음에 접근하면 정말 복잡한 문제인 것 같습니다.
그래서 하나하나 천천히 정리 해 보려고 합니다.
시작하기전에, 연결리스트의 장점이 무엇인지 정리 해 보았습니다.
- 삽입 , 삭제하기에 용이하다.
- 탐색 , 원하는 요소를 반환 할 수 있어 접근하기에 좋다.
- 필요 한 만큼의 동적할당 할 수 있다.
연결리스트 하면 보통 배열이랑 많이 엮어서 바라보기도 합니다.
배열은 검색이 연결리스트에 비해 빠르지만, 요소를 삭제 할 수 없습니다. 처음에 배열을 선언 할 때, 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 = newNodelist->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이 제거된 모습입니다.
다시 정리차원에서 한번 코드를 짜 보았는데, 역시 자료구조는 그림을 그리면서 생각을 해야하구나 싶었습니다. 기억이 잘 나지않아서 블로그도 보고, 책도 보고 다시 깊게 공부했던거 같습니다.
