연결 자료구조
연결 자료구조는 각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식의 자료구조를 뜻한다.
연결 자료구조의 원소는 '노드(Node)'라 불리며 원소의 값을 저장하는 '데이터 필드(Data Field)'와 다음 노드의 주소를 저장하는 '링크 필드(Link Field)'로 구성된다.
연결 자료구조가 나온 이유(순차 자료구조와의 비교)
우리가 자료구조를 생각할 때, 각 원소들이 어떻게 배치될 것이라고 머릿속으로 생각하는 것을 논리적 구조라 한다. 그리고 자료구조가 선언되어 실제로 메모리에 할당되어있는 구조를 물리적 구조라 한다.
연결 자료구조와 순차 자료구조는 이러한 특징에서 차이를 가진다.
순차 자료구조
순차 자료구조의 구현 방식은 논리적 구현 방식과 물리적 구현 방식이 같다.
순차 자료구조의 대표적인 예인 배열로 설명을 해보도록 하겠다.
7칸짜리 배열 Num[7]을 선언하였을 때, 우리는 배열의 원소들이 하나의 덩어리로 붙어있다고 생각하게 된다. 그리고 이 배열이 메모리에 할당되었을 때도 한 무리가 되어서 메모리에 붙어서 할당되게 된다.
이러한 구조는 중간의 원소가 삭제되거나 추가될 때, 논리적 구조와 물리적 구조를 맞추기 위해여 원소들을 옮기는 추가 작업이 필요하다.
때문에 원소의 개수가 많거나, 삽입이나 삭제 연산이 많이 필요할 경우 비효율성의 문제를 가지고 있다.
연결 자료구조
연결 자료구조는 논리적 순서와 물리적 순서가 같지 않다.
연결 리스트는 하나의 덩어리로 뭉쳐있는 것처럼 보이지만, 실제로 메모리 위에서는 연속되게 위치해있지 않다.
때문에 원소의 삭제, 삽입이 이루어지더라도 논리적 구조와 물리적 구조를 맞추기 위해 추가 작업을 할 필요가 없다.
이런 특징 덕분에 크기를 유연하게 변경할 수 있고 메모리를 효율적으로 사용할 수 있다.
연결 리스트의 기능
연결 리스트의 주요 기능인 노드의 삽입과 삭제에 대해 그림과 함께 설명하겠다.
사람마다 차이가 있겠지만 나는 맨 앞에 리스트의 시작 노드 head를 따로 만드는 방식으로 기능을 구현했다.
이 외에도 맨 끝에 tail 노드를 만드는 사람도 있고 다양한 방법이 있으니 찾아보는 것도 좋을 거 같다.
노드 삽입
맨 처음에 삽입
newNode를 삽입하기 전에는 head->link가 가리키는 노드는 1의 데이터가 들어있는 노드임을 볼 수 있다.
여기서 newNode를 삽입하고 싶다면
head->link가 newNode를 가리키게 하고, 원래 head->link가 가리키던 노드는 newNode->link가 가리키게 하면 된다.
중간에 삽입
newNode를 삽입하기 전에는 temp->link가 가리키는 노드는 3의 데이터가 들어있는 노드임을 볼 수 있다.
여기서 newNode를 삽입하고 싶다면
temp->link가 newNode를 가리키게 하고, 원래 temp->link가 가리키던 노드는 newNode->link가 가리키게 하면 된다.
마지막에 삽입
newNode를 삽입하기 전에는 temp->link가 가리키는 노드는 NULL임을 볼 수 있다.
여기서 newNode를 삽입하고 싶다면
원래 temp->link가 가리키던 노드를 newNode로 변경하고, newNode->link의 값을 NULL로 만들면 된다.
노드 삭제
맨 처음 노드 삭제
head->link가 가리키는 첫 번째 노드(편의상 deleteNode라 표현)를 삭제하고 싶다면
deleteNode->link가 가리키는 노드를 head->link가 가리키게 하고, deleteNode를 삭제한다.
중간 노드 삭제
세 번째 노드(데이터가 2인 노드)를 삭제하고 싶다면, head부터 탐색을 시작해서 삭제하고자 하는 노드를 temp로 만든다.
temp->link가 가리키는 노드를 current->link가 가리키게 하고, temp 노드를 삭제한다.
마지막 노드 삭제
제일 끝 노드(데이터가 4인 노드)를 삭제하고 싶다면, head부터 탐색을 시작해서 삭제하고자 하는 노드를 temp로 만든다.
원래 temp 노드를 가리키던 current->link를 NULL로 만들고, temp 노드를 삭제한다.
연결 리스트 구현
노드
typedef struct Node {
int data; //데이터 필드
struct Node* link; //링크 필드
};맨 앞에 삽입
void InsertFirstNode(int input, Node* head) { //처음 노드로 삽입
Node* newNode = new Node(); //새로운 노드 선언 및 할당
newNode->data = input; //데이터 입력
newNode->link = head->link; //head->link를 newNode->link가 가리키게 함
head->link = newNode; //head와 새로운 노드 연결
}중간에 삽입
void InsertMiddleNode(int input, int position, Node* head) { //중간에 삽입
int i = 0;
if(position == 1) //첫 노드에 삽입 할 경우
InsertFirstNode(input, head);
else {
Node* temp = head;
Node* newNode = new Node(); //새로운 노드 선언 및 할당
newNode->data = input;
while (i < position - 1) { //i-1번째 노드를 temp로 만듦
i++;
temp = temp->link;
}
newNode->link = temp->link; //temp->linK가 가리키던 노드를 newNode->link가 가리키게 함
temp->link = newNode;
}
}마지막에 삽입
void InsertLastNode(int input, Node* head) { //마지막에 삽입
Node* temp = head;
Node* newNode = new Node(); //새로운 노드 선언 및 할당
newNode->data = input;
newNode->link = nullptr;
while(temp->link != NULL){ //연결 리스트의 끝 노드를 temp로 만듦
temp = temp->link;
}
temp->link = newNode; //노드를 연결리스트 끝에 추가
}첫 노드 삭제
void DeleteFirstNode(Node* head) { //처음 노드 삭제
Node* temp = head->link; //삭제하고자 하는 노드를 temp로 만듦
head->link = temp->link; //temp->link가 가리키는 노드를 head->link가 가리키게 함
delete temp; //temp노드 할당 해제
}중간 노드 삭제
void DeleteMiddleNode(int position, Node* head) { //중간 노드 삭제
int i = 0;
if(position == 1) { //삭제하고자 하는 노드가 첫 번째 노드면
DeleteFirstNode(head);
}
else {
Node* temp = head;
Node* current;
while(i < position) { //삭제하고자 하는 노드를 temp, 그 전 노드를 current로 만듦
current = temp;
temp = temp->link;
i++;
}
current->link = temp->link; //temp->link가 가리키는 노드를 current->link가 가리키게 함
delete temp; //temp 할당 해제
}
}
마지막 노드 삭제
void DeleteLastNode(Node* head) { //마지막 노드 삭제
Node* temp = head;
Node* current;
while(temp->link != nullptr) { //가장 끝 노드를 temp, 그 전 노드를 current로 만듦
current = temp;
temp = temp->link;
}
current->link = nullptr; //current->link의 값을 NULL로 만듦
delete temp; //temp 할당 해제
}연결리스트 출력
void PrintList(Node* head) {
Node* temp = head->link;
while(temp != nullptr) { //연결리스트 끝까지
cout << temp->data << ", ";
temp = temp->link;
}
cout << "\n";
}main()
int main() {
Node* head = new Node(); //head 노드 생성 및 할당
head->link = nullptr;
int menu = 0;
int position = 0;
int input = 0;
while(1) {
cout << "\n메뉴를 선택하시오\n\n";
cout << "1. 맨 앞에 삽입\n2. 중간에 삽입\n3. 끝에 삽입\n"
"4. 맨 앞 노드 삭제\n5. 중간 노드 삭제\n6. 마지막 노드 삭제\n"
"7. 연결리스트 출력\n8. 종료\n\n입력 : ";
cin >> menu;
switch (menu) {
case 1:
cout << "입력할 값을 입력하시오 : ";
cin >> input;
InsertFirstNode(input, head);
break;
case 2:
cout << "입력할 값을 입력하시오 : ";
cin >> input;
cout << "입력할 위치를 입력하시오 : ";
cin >> position;
InsertMiddleNode(input, position, head);
break;
case 3:
cout << "입력할 값을 입력하시오 : ";
cin >> input;
InsertLastNode(input, head);
break;
case 4:
DeleteFirstNode(head);
break;
case 5:
cout << "삭제할 위치를 입력하시오 : ";
cin >> position;
DeleteMiddleNode(position, head);
break;
case 6:
DeleteLastNode(head);
break;
case 7:
PrintList(head);
break;
case 8:
return 0;
}
}
}총평
이 글에서는 연결 리스트의 기초 of 기초인 단일 연결 리스트만 알아봤다.
이 외에도 원형 연결 리스트, 양방향 연결 리스트 등이 있으니 더 공부하고 싶다면 찾아보길 바란다.
놀랍게도 연결 리스트를 하도 오랜만에 짜다 보니 한참 걸렸다.
뇌가 초기화된 느낌이 들었다고 해야 하나...
연결 리스트 말고도 다른 자료구조들도 다 까먹었다.
복습 겸 당분간은 알고리즘 문제 대신 자료구조에 대해 공부를 해볼까 한다.
'자료구조 > C++' 카테고리의 다른 글
| [자료구조/C++] 스택(Stack) (0) | 2022.01.25 |
|---|
댓글