연결 리스트 (Linked List) - 메모리의 동적 할당

* 열혈강의 자료구조 책 + 인터넷 + a

연결 리스트란? (메모리의 동적 할당)

메모리의 동적 할당, 즉 malloc와 free를 이용한 연결 리스트의 핵심 중 하나는 바로 아래 코드입니다

#include<iostream> using namespace std; typedef struct _Node{ int data; struct _Node *next; } Node;

Node 구조체입니다.

여기서 Node란, data, 즉 어떤 값을 가지고 있으며, 동시에 Node형 구조체 변수의 주소 값을 저장할 수 있는 포인터 변수를 포함합니다. (책에서는 바구니에 비유)

더 단순하게 이해해보자면 Node의 값은 data, 그리고 다음 Node의 주소는 next에 있다. 즉 data라는 값을 가진 노드 하나는 next 노드를 가리킨다. 라고 생각할 수 있습니다. 아래 그림을 보시면 단번에 이해가 가능하실 거에요

이러한 next 노드의 연속으로 노드 구조체 변수들을 연결하는 것이 가능하며 연결 리스트가 생성됩니다.

typedef struct _List{ Node *head; Node *tail; Node *current; int NumOfData; } List;

위 코드는 연결 리스트를 관리하는데 있어 필요한 (연결 리스트)구조체입니다.

노드 구조체들을 변수로 가지며 각각 

head는 연결 리스트의 시작 노드를,  

tail은 연결 리스트의 끝 노드를,

current는 현재 노드를 가리킵니다.

연결 리스트 초기화

void Initialize(List *list){ list->head = NULL; list->tail = NULL; list->current = NULL; list->NumOfData = 0; }

연결 리스트가 가리키는 값 head, tail, current를 각각 초기화합니다. (리스트를 처음 생성했을 땐 아무 노드도 없는 상태이므로 모든 변수들이 NULL을 가리킵니다. + 데이터의 갯수가 0)

데이터 출력

void Print(List *list){ list->current = list->head; cout << "-------*리스트를 출력합니다*-------" << endl; while (list->current!= NULL){ cout << list->current->data<<" "; list->current = list->current->next; } cout << endl; }

연결 리스트를 순서대로 출력합니다.

헤드를 current로 지정하여 헤드부터 tail까지 출력하며, current노드가 없으면, 즉 tail까지 출력이 완료되면 반복문을 빠져나옵니다.

데이터 삽입

데이터 삽입이란 어떤 노드에 데이터를 넣고 이 노드를 연결 리스트 속에 집어넣는 것을 의미합니다.

그림처럼 굉장히 간단합니다. 코드를 살펴보기 전 이 그림만 봐도 직관적으로 이해가 가능하실 거에요

그럼 세부적으로 설명해보도록 하겠습니다

새로운 리스트를 처음 생성했을 때, 위에서 나온 것처럼 모든 구조체 변수들은 NULL포인터입니다.

여기에 노드 하나를 삽입한다면..?

노드가 하나뿐이므로 머리=꼬리=뉴노드입니다. 뉴노드->next 노드가 없으므로 NULL을 가리킵니다. (위 그림에서는 화살표 없음=NULL)

이 상태에서 새로운 노드를 추가해보겠습니다

head는 첫 노드 그대로지만 tail은 뉴노드를 가리킵니다. 

위 그림대로라면 뉴노드->next는 NULL, tail->next도 NULL이 되겠군요

노드를 계속 추가한 모습입니다.

이 그림 그대로 코드를 구현해보겠습니다.

1 새 노드를 연결 리스트의 머리에 추가할 경우

void InsertHead(List *list, int data){ Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = NULL; if (list->head == NULL) list->tail = newnode; else newnode->next = list->head; list->head = newnode; (list->NumOfData)++; }

2 새 노드를 연결 리스트의 꼬리에 추가할 경우

void InsertTail(List *list, int data){ Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = NULL; if (list->head == NULL) list->head = newnode; else list->tail->next = newnode; (list->NumOfData)++; list->tail = newnode; }

3 새 노드를 특정 번째 노드로 추가할 경우

void InsertIn(List *list, int data, int where){ if (where > list->NumOfData + 1){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 해당 위치에 노드를 추가할 수 없습니다." << endl; return; } Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; newnode->next = NULL; if (where == 1){ if (list->NumOfData == 0){ list->tail = newnode; } else{ newnode->next = list->head; } list->head = newnode; } else{ list->current = list->head; while (where > 2){ list->current = list->current->next; where--; } newnode->next = list->current->next; list->current->next = newnode; } (list->NumOfData)++; }

제가 구현한 것은 몇 번째 노드(where)로 추가할 것인가, 를 중점으로 하였습니다. 

추가하고자 하는 위치가 리스트 내 데이터의 갯수를 넘어갈 때(예를 들어 리스트 길이는 2인데 4번째에 넣고자 할 때)에는 에러 메세지를 띄웁니다.

0 이하의 음수를 입력할 때의 예외처리는 따로 해주지 않았네요..

+) 코드들을 테스트한 메인 함수와 결과

int main(){ List *LList = (List*)malloc(sizeof(List)); List *LList2 = (List*)malloc(sizeof(List)); List *LList3 = (List*)malloc(sizeof(List)); Initialize(LList); Initialize(LList2); Initialize(LList3); InsertHead(LList, 1); InsertHead(LList, 2); InsertHead(LList, 3); Print(LList); InsertTail(LList2, 1); InsertTail(LList2, 2); InsertTail(LList2, 3); Print(LList2); InsertIn(LList3, 1, 1); InsertIn(LList3, 2, 1); InsertIn(LList3, 3, 2); InsertIn(LList3, 3, 5); InsertIn(LList3, 4, 4); Print(LList3); return 0; }

데이터 삭제

마찬가지로 어떤 데이터를 가진 노드를 삭제하는 것을 의미합니다.

여기서는 데이터 삽입과 다르게 더미노드를 이용했습니다. 

1 연결 리스트의 머리에서 노드 삭제

void DeleteHead(List *list){ if (list->NumOfData == 0){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 삭제할 노드가 없습니다" << endl; return; } Node *Dummy = (Node*)malloc(sizeof(Node)); Node *DummyNext = (Node*)malloc(sizeof(Node)); Dummy = list->head; DummyNext = list->head->next; free(Dummy); list->head = DummyNext; (list->NumOfData)--; }

2 연결 리스트의 꼬리에서 노드 삭제

void DeleteTail(List *list){ if (list->NumOfData == 0){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 삭제할 노드가 없습니다" << endl; return; } int Data = list->NumOfData; list->current = list->head; while (Data > 2){ list->current = list->current->next; Data--; } Node *Dummy = (Node*)malloc(sizeof(Node)); Node *DummyNext = (Node*)malloc(sizeof(Node)); Dummy = list->current; DummyNext = list->current->next; free(DummyNext); list->tail = Dummy; list->tail->next = NULL; (list->NumOfData)--; }

(꼬리에서의 노드 삭제는 제가 그냥 한번 해본 거라.. 실제적인 효율은 별로 좋지 못할 것 같습니다.)

3 특정 번째 노드 삭제

void DeleteAt(List *list, int where){ if (where > list->NumOfData){ cout << "EEERRRRRRRROOOOORRRRRRRR :: 해당 위치에 삭제할 노드가 없습니다." << endl; return; } if (where == 1){ DeleteHead(list); return; } else if (where == list->NumOfData){ DeleteTail(list); return; } list->current = list->head; while (where > 2){ list->current = list->current->next; where--; } Node *Dummy = (Node*)malloc(sizeof(Node)); Node *DummyNext = (Node*)malloc(sizeof(Node)); Dummy = list->current; DummyNext = list->current->next; list->current->next = DummyNext->next; free(DummyNext); (list->NumOfData)--; }

데이터 삽입과 마찬가지로 몇 번째 노드(where)를 삭제할 것인가, 를 중점으로 하였습니다. 

삭제하고자 하는 위치가 리스트 내 데이터의 갯수를 넘어갈 때(예를 들어 리스트 길이는 2인데 4번째 노드를 삭제하고자 할 때)에는 에러 메세지를 띄웁니다.

여기도 마찬가지로 무조건 자연수만 입력한다는 가정 하에 만든 코드입ㄴㅣ다ㅠ

그리고 데이터 삽입과는 다르게.. where이 1 이거나 리스트 내 데이터의 갯수와 같을 경우엔 각각 DeleteHead, DeleteTail 함수를 호출하였습니다.

+) 코드들을 테스트한 메인 함수와 결과

int main(){ List *LList = (List*)malloc(sizeof(List)); List *LList2 = (List*)malloc(sizeof(List)); List *LList3 = (List*)malloc(sizeof(List)); Initialize(LList); Initialize(LList2); Initialize(LList3); InsertTail(LList, 1); InsertTail(LList, 2); InsertTail(LList, 3); InsertTail(LList, 4); InsertTail(LList, 5); Print(LList); DeleteHead(LList); DeleteHead(LList); Print(LList); cout << endl; InsertTail(LList2, 1); InsertTail(LList2, 2); InsertTail(LList2, 3); InsertTail(LList2, 4); InsertTail(LList2, 5); Print(LList2); DeleteTail(LList2); DeleteTail(LList2); Print(LList2); cout << endl; InsertTail(LList3, 1); InsertTail(LList3, 2); InsertTail(LList3, 3); InsertTail(LList3, 4); InsertTail(LList3, 5); Print(LList3); DeleteAt(LList3,6); DeleteAt(LList3,1); DeleteAt(LList3,3); Print(LList3); return 0; }

--------------------------------------------------------------------------------------------------------------------------------------------------------------

응용하면 입력받은 값으로 리스트를 만드는 것도 가능합니다.

많이 부족하기에 참고용으로 봐주시면 + 틀린 부분이 있다면 고쳐주시면 감사드리겠습니다 

읽어주셔서 감사합니다.