[4] 리스트 ① 단일 연결리스트
추상자료형
추상자료형이란 데이터 구조의 추상형으로서 데이터가 컴퓨터에 저장되고 실행되는 기계적인 메커니즘과는 구분되어 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것을 말한다.
ADT는(Abstract Data Type)의 약자로 구체적으로 세 가지를 명시한다.
① 다루는 데이터
② 데이터에 관한 작업들
③ 데이터를 다루는 중 발생 가능한 에러 상황들
데이터를 컴퓨터에 효과적으로 표현하고 컴퓨터 상에서 효율적으로 처리할 수 있도록 하는 기술을 다루는 데이터 구조에 관한 학습은 중요하므로 이러한 데이터 구조를 기계적 관점이 아닌 인간의 관점에 가까운 추상자료형의 관점이 중요하다.
리스트 ADT
리스트 ADT는 연속적인 임의 개체를 모델링한다.
리스트를 구성하는 개체는 해당 리스트의 원소가 되며 각 원소에 대한 식별과 접근은 순위에 의해 이루어진다. 리스트 ADT는 순서 혹은 무순으로 구현되며 스택과 큐, 집합 등을 표현하기 위한 도구 및 복작한 데이터 구조를 구성하는 일부분으로 사용된다.
연결리스트
연결리스트란 대부분의 알고리즘에서 사용하는 자료구조로, 프로그램 실행 중에도 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며 링크라는 개념을 통해 물리 메모리를 연속적으로 사용하지 않아도 되므로 관리가 쉽다.
이때 데이터를 구조체로 묶어서 포인터로 연결할 수 있다는 큰 장점을 가진다.
연결리스트를 구성하는 노드는 다음과 같다.
1. 헤드 노드: 해드 노드에는 데이터를 저장하지 않는다. 헤드 노드를 사용하면 연결리스트를 관리할 때 용이하다.
2. 테일 노드 :테일 노드에도 데이터를 저장하지 않는다. 헤드 노드와 마찬가지로 묵시적으로 사용하지 않는다.
연결리스트의 생성
먼저 연결리스트의 장점에 대해 알아보자. 연결리스트의 장점은 곧 배열의 단점 극복이다. 배열이 같은 자료형을 갖는 집합으로 연속적인 데이터를 저장한다. 이때 배열은 생성할 때 크기가 고정되므로 프로그램 실행 중에 배열의 크기를 바꿀 수없다는 점을 연결리스트는 해결 할 수 있다.
배열은 연속된 메모리를 사용하지만
단일 연결리스트는 반드시 연속적이지 않으며, 데이터를 '링크'로 연결한다.
[ 배열을 이용한 리스트 생성]
N개의 크기를 가진 배열 V를 사용하며 변수 n으로 리스트의 크기를 관리한다.
원소 접근을 위한 get 함수와 원소 저장을 위한 set 함수를 구현하면 아래와 같다.
코드는 아래의 [더보기] 란을 확인한다.
#include <stdio.h>
#include <stdlib.h>
// 노드 포인터 타입 정의
typedef int Node;
// 연결 리스트 ADT 함수 정의
Node* initialize(int n) {
Node* head = NULL;
return head;
}
Node* insert(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
*newNode = data;
newNode[1] = (Node)head;
head = newNode;
return head;
}
Node* add(Node* head, int r, int data) {
if (r < 0) {
printf("인덱스는 0 이상이어야 합니다.\n");
exit(1);
}
if (r == 0) {
return insert(head, data);
}
Node* current = head;
int idx = 0;
while (current != NULL) {
if (idx == r - 1) {
Node* newNode = (Node*)malloc(sizeof(Node));
*newNode = data;
newNode[1] = current[1];
current[1] = (Node)newNode;
return head;
}
current = (Node*)current[1];
idx++;
}
printf("인덱스 범위를 벗어납니다.\n");
exit(1);
}
void printList(Node* head) {
printf("리스트: ");
while (head != NULL) {
printf("%d ", *head);
head = (Node*)head[1];
}
printf("\n");
}
int get(Node* head, int r) {
int idx = 0;
while (head != NULL) {
if (idx == r) {
return *head;
}
head = (Node*)head[1];
idx++;
}
printf("인덱스 범위를 벗어납니다.\n");
exit(1);
}
Node* removeElement(Node* head, int r) {
if (head == NULL) return NULL;
if (r == 0) {
Node* next = (Node*)head[1];
free(head);
return next;
}
Node* current = head;
Node* prev = NULL;
int idx = 0;
while (current != NULL && idx != r) {
prev = current;
current = (Node*)current[1];
idx++;
}
if (current == NULL) {
printf("인덱스 범위를 벗어납니다.\n");
exit(1);
}
prev[1] = current[1];
free(current);
return head;
}
int main() {
Node* list = NULL;
int n;
printf("리스트의 크기를 입력하세요: ");
scanf("%d", &n);
printf("%d개의 노드를 추가하세요:\n", n);
for (int i = 0; i < n; i++) {
int data;
printf("데이터 입력: ");
scanf("%d", &data);
list = insert(list, data);
}
printf("노드 추가 후: ");
printList(list);
int r;
printf("삭제할 위치의 인덱스를 입력하세요: ");
scanf("%d", &r);
list = removeElement(list, r);
printf("노드 삭제 후: ");
printList(list);
}
배열을 이용하여 리스트를 구현할 경우 데이터구조에 의한 기억장소 사용량은 O(n)이며 리스트 get,set과 같은 처리함수의 작업은 O(1)시간에, add와 remve는 인덱스를 찾기 때문에 O(n)의 시간이 걸린다.
위의 코드는 GTP4로 작성한 코드로, 필자가 사용하는 변수의 이름과는 다르므로 사용시에 주의가 필요하다. GPT의 성능을 확인하기 위해 코드 작성을 요구해보았다.
구조체를 이용한 연결리스트 구현
연결리스트의 알고리즘을 구상하기전에 C에서의 연결리스트 구조체는 다음과 같다.
/*연결 리스트를 구현할 구조체*/
typedef struct ListNode{
int data;
struct ListNode* next;//자가 참조 구조체
/*다음 노드의 주소를 저장할 자기참조 구조체포인터*/
}ListNode;단일 연결리스트의 삽입 알고리즘 (배열)
예를 들어 "헤드노트-A-B-D-E-테일노드"의 구조에 노드 C를 추가하는 삽입 알고리즘을 생각해보자.
배열을 사용한 데이터 삽입을 코드로 작성하면 다음과 같다.
코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char ipt,Data[5]={'A','B','D','E'};
char c;
int main(){
int i,temp,temp2;
c = 'C';
for(i=0;i<5;i++) printf("%2c",Data[i]); printf("\n");
for(i=0;i<5;i++)
if(Data[i]>c) break;
temp = Data[i]; Data[i] = c; i++;
for(;i<5;i++){
temp2 = Data[i];
Data[i] = temp;
temp = temp2;
}
for(int i=0;i<5;i++)printf("%c ",Data[i]);
}5개의 데이터를 저장할 때에는 삽입에 있어 반복 처리는 쉽지만 데이터의 양이 늘어날 수록 많은 데이터의 이동이 필요하다. 다시말해 전체 데이터의 수가 증가하면 증가할 수록 비효율적이며 이를 해결하기 위한 단일 연결리스트의 알고리즘을 확인해보자.
단일 연결리스트의 삽입 알고리즘 (구조체)
단일 연결 리스트는 한 방향으로만 연결되어 있다. 따라서 나와 연결된 다음 노드는 알 수 있지만 내 이전 노드는 알 수 없다. 그러므로 역행해서 바로 이동할 수도 없다. 단일 연결리스트는 헤드노드, 데이터 노드, 엔드노드(테일노드)로 이루어져있다.
이때 헤드노드와 엔드노는 더미데이터를 가지고 있는데 이는 데이터를 가지고 있지 않고 노드 정보만 가지고 있다는 뜻이다.
· head(머리 더미) = 데이터 없이 첫번째 노드를 가르킨다.
· tail(꼬리 더미) = 데이터 없이 꼬리 자신을 가르킨다.
즉 head 와 tail 은 오로지 처음과 끝을 알리는 역할만 한다. 사실 엔드노드 필요없이 NULL으로 끝을 확인해도 무방하다. 결국 헤드 노드와 엔드 노드는 편의상 추가하는 '묵시적 존재'이다.
단일 연결리스트의 순서도는 아래와 같다.
1. 연결리스트 구조체 생성하기
2. 헤드(head)노드와 엔드(end)노드를 동적할당으로 생성 후 NULL과 연결
3. Node1이라는 새로운 노드를 생성
4. Node1을 head와 NULL사이에 연결(node1의 꼬리를 head의 꼬리로 연결)
5. Node1의 값을 업데이트
6. 순회용 노드 생성
7. 다음 노드의 방향이 NULL이 아닐 때 까지 반복
8. 반복 종료 시 메모리 해제
아래의 [더보기] 란의 코드는 연결리스트를 생성 전의 기본적인 구조체와 헤드/엔드 노드의 동적할당 과정이다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*연결 리스트를 구현할 구조체*/
typedef struct ListNode{
int data;
struct ListNode* next;//자가 참조 구조체
/*다음 노드의 주소를 저장할 자기참조 구조체포인터*/
}ListNode;
int main(){
/*노드를 메모리 동적 할당으로 생성하기*/
ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
ListNode* end = (ListNode*)malloc(sizeof(ListNode)); //엔드 노드 생성
end = NULL;// end->next = end;
head->next = end;
while(curr != NULL){
printf("%d\n", curr->data);
curr = curr->next;
}
}단일 연결리스트의 함수 : add 함수
add 함수의 기본 로직은 아래와 같다.
① 삽입하고자 하는 위치 바로 앞까지 간다. (i < rank)
② 이때의 노드가 NULL이 아니라면, 이 노드를 임시로 저장한다. 이때의 노드를 curr라고 하자.
③ 새로운 노드를 동적할당하여 생성한다. 이때의 노드를 p라고 하자
④ p에 데이터를 담고, 이 노드의 next를 curr의 next로 저장한다.
⑤ curr의 next를p의 next로 바꾼다.
코드는 아래의 [더보기] 란을 확인한다.
ListNode* add(ListNode *head, int rank, int value){//구조체 함수
/*list의 순위 r에 원소 e를 추가해야함으로 순위r까지 반복한 후 해당 위치에 원소 e를 추가하도록한다.*/
int cnt = 0;
ListNode* check = head->next; //순회용 노드 생성
while(check != NULL){
cnt ++;
check = check->next;
}free(check);
//printf("cnt = %d\n",cnt);
if(cnt > rank) {printf("invalid position");return 0;}
else{
ListNode* curr = head; //순회용 노드 생성
for(int i=0;i<rank;i++)curr= curr->next;
//위 반복문을 통해 이미 순위가 r인 노드까지 이동함.(ㄱ)
ListNode *p=(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.
p->data = value;
p->next = curr->next;
curr->next = p;
// printf("추가된 노드의 데이터는 %d입니다.\n",p->data);
return head; //다음 노드의 위치를 반환함.
}
}단일 연결리스트의 함수 : delete 함수
delete 함수의 기본 로직은 아래와 같다.
① 삭제하고자 하는 노드 바로 앞까지 이동한다. (i < rank)
② 다음 노드가 NULL이 아니라면 이 노드를 임시로 저장한다. 이때의 노드를 rear 라고 하자.
③ 삭제할 노드는 저장한 노드의 다음 노드이다. 그 노드를 임시로 저장한다. 이때의 노드를 tmp라고 하자
④ tmp의 next를 rear의 next에 저장한다.
⑤ tmp를 삭제한다.
코드는 아래의 [더보기] 란을 확인한다.
// delete(list, r) : list의 순위 r에 위치한 원소를 삭제한다 (주교재의 remove와 동일)
ListNode* delete(ListNode *head, int rank){//구조체 함수
ListNode* rear = head; //순회용 노드 생성
for(int i=0;i<rank-1;i++)rear= rear->next;//삭제할 노드의 뒤까지 반복
ListNode* tmp = rear->next; printf("데이터 [%d]를 삭제합니다.\n",tmp->data);
//삭제할 노드는 저장한 노드의 다음 노드이다. 그 노드를 임시로 저장한다.
rear->next = tmp->next; free(tmp);
// (삭제할 노드-1)의 다음 노드는 (삭제할 노드의 + 1)
return head;
}단일 연결리스트의 함수 : print 함수
print 함수의 로직은 순회중 노드의 next값이 NULL이 아닐 때까지 반복하여 리스트에 저장된 값을 출력한다.
코드는 아래의 [더보기] 란을 확인한다.
void print(ListNode *head){
ListNode* prt = head->next; //순회용 노드 생성
while(prt != NULL){
printf("%d ", prt->data);
prt = prt->next;
}free(prt);
printf("\n");
}현재는 입력/삭제/출력 함수 밖에 없으나 추후에 추가할 예정이며 이번에 구현한 리스트는 단일 연결리스트로 역방향 순회가 존재하지 않는다. 함수와 변수의 이름은 [cmd + shift+L]로 한번에 변경하여 사용할 수 있다.