오늘은 단일 연결리스트가 무엇인지, 그리고 배열 기반 리스트와 비교하여 어떠한 장점이 있는지에 대해 소스코드와 함께 간단히 알아보겠습니다.
▶ 배열 기반 리스트란?
배열 기반 리스트는 가장 기본적인 리스트의 형태로 순차 리스트라고도 불립니다. 아래와 같은 형태를 가집니다.
▶ 배열 기반 리스트의 특징
- 특정 위치 원소에 즉시 접근 가능
- 데이터가 들어갈 공간을 미리 할당해야 함
- 원하는 위치로의 삽입, 삭제가 비효율적 (매번 모든 값을 이동시켜 주어야 함)
▶ 배열 기반 리스트 소스코드 (C언어)
#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 10000 // 충분히 큰 수
int arr[INF]; // 충분히 큰 배열 생성
int count = 0; // 카운트 변수 초기화
// 배열 맨 뒤에 요소 추가
void addback(int data){
arr[count] = data;
count++;
}
// 배열 맨 앞에 요소 추가
void addfirst(int data){
for(int i = count ; i >= 1 ; i--){
arr[i] = arr[i-1]; // 한 칸씩 밀기
}
arr[0] = data;
count++;
}
// 특정 인덱스 요소 추가
void addAt(int index, int data){
for(int i = count;i >= index ;i--){
arr[i+1] = arr[i];
}
arr[index] = data;
count++;
}
// 특정 인덱스 요소 삭제
void removeAt(int index){
for(int i = index; i < count - 1; i++){
arr[i] = arr[i + 1];
}
count--;
}
// 배열 출력
void show(void){
for(int i = 0; i < count; i++){
printf("%d ", arr[i]);
}
}
int main(void) {
addback(3);
addback(4);
addback(5);
addfirst(2);
addfirst(1);
addAt(3, 7);
show();
system("read");
return 0;
}출력값 -> 1 2 3 7 4 5
▶ 연결리스트란?
연결리스트는 각 노드가 데이터값과 함께 다른 노드의 주소값을 참조하고 있는 형태를 말합니다. 이는 구조체와 포인트 변수를 이용한 동적 메모리 할당을 통해 이루어집니다. 종류는 크게 단일 연결 리스트와 양방향 연결 리스트로 나누어지는데, 이번 포스트에서는 단일 연결 리스트의 형태에 대해 알아보겠습니다.
▶ 단일 연결 리스트
위 이미지는 단일 연결 리스트의 형태를 그림으로 나타낸 것입니다. 단일 연결 리스트는 각 노드가 다음 노드의 주솟값을 참조하고 있습니다.
▶ 연결 리스트의 특징
- 구조체와 포인터를 함께 사용하여 구현
- 필요할 때마다 공간을 할당받음
- 특정 인덱스로 바로 접근 불가, 노드를 하나씩 검색해야 함
- 삽입 및 삭제가 많은 경우 유리
- 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비될 수 있음
▶ 단일 연결 리스트 소스코드(C언어)
#include <stdio.h>
#include <stdlib.h>
// Node 구조체 선언
typedef struct {
int data;
struct Node *next;
} Node;
Node *head; //구조체 변수 head 정의
// 맨 앞에 데이터 삽입
void addFront(Node *root, int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = root->next;
root->next = node;
}
// 맨 앞의 데이터 삭제
void removeFront(Node* root) {
Node* front = root->next;
root->next = front->next;
free(front);
}
// 모든 노드 메모리 할당 해제
void freeAll(Node* root) {
Node* cur = head->next;
while (cur != NULL) {
Node* next = cur->next;
free(cur);
cur = next;
}
}
// 전체 리스트 출력
void showAll(Node* root) {
Node* cur = head->next;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
}
int main(void) {
head = (Node*)malloc(sizeof(Node));
addFront(head, 2);
addFront(head, 3);
addFront(head, 1);
addFront(head, 7);
addFront(head, 4);
removeFront(head);
showAll(head);
freeAll(head);
return 0;
}