연결 리스트(Linked List)
메모리의 동적 할당을 기반으로 하는 리스트
연결 리스트의 구조
- 노드(Node): 아래 그림의 상자 같은 데이터 덩어리, 데이터 필드(data field)와 링크 필드(link field)로 구성
연결 리스트에서의 노드의 구조
int형을 저장하는 노드 구조체
- 헤드 포인터(Head Pointer): 첫 번째 노드의 주소를 저장하는 포인터
연결 리스트의 특징
- 노드들은 메모리의 어느 곳에나 위치할 수 있다. => 노드들의 주소가 연결 리스트 상의 순서와 동일하지 않다.
- 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하며, 동적으로 생성하기에 미리 공간을 확보할 필요가 없다.
- 링크필드를 위한 추가 공간이 필요하다.
- 배열에 비해 연산의 구현이나 사용 방법이 복잡하다.
- 오류가 없더라도 메모리의 동적 할당과 해제가 빈번하게 일어나면 프로그램이 느려질 수 있다.
연결 리스트의 종류
단순 연결 리스트(Singly Linked List): 하나의 방향으로만 연결
원형 연결 리스트(Circular Linked List): 단순 연결 리스트와 같으나 마지막 노드의 링크 값이 첫 번째 노드를 가리킴
이중 연결 리스트(Doubly Linked List): 각 노드마다 포인트가 2개씩 존재하여 선행 노드와 후속 노드를 모두 가리키는게 가능
연결 리스트의 3가지 종류
연결 리스트의 추상 자료형
데이터
같은 타입의 요소들이 순서를 가지고 저장된 데이터
연산
init(): 리스트의 초기화
insert(): 요소 삽입
delete(): 요소 삭제
get(): 요소 반환
isEmpty(): 리스트가 비어있는지 확인
replace(): 요소 교체
size(): 요소의 개수 반환
find(): 요소가 있는지 확인
clear(): 리스트를 비움
아래는 c에서의 단순 연결 리스트의 구현입니다.
#include <stdio.h>
#include <stdlib.h>
typedef int Data;
typedef struct LinkedNode {
Data data;
struct LinkedNode* link;
} Node;
Node* head = NULL;
void init() {
head = NULL;
}
int isEmpty() {
return head == NULL;
}
void insert_next(Node* before, Node* node) {
if (node != NULL) {
node->link = before->link;
before->link = node;
}
}
Node* get_entry(int pos) {
Node* p = head;
for (int i = 0; i < pos; i++) {
if (p == NULL) return NULL;
p = p->link;
}
return p;
}
void insert(int pos, Data data) {
Node* newNode, * prev;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->link = NULL;
if (pos == 0) {
newNode->link = head;
head = newNode;
}
else {
prev = get_entry(pos - 1);
if (prev != NULL)
insert_next(prev, newNode);
else free(newNode);
}
}
Node* remove_next(Node* before) {
Node* removed = before->link;
if (removed != NULL)
before->link = removed->link;
return removed;
}
void delete(int pos) {
Node* prev, * removed;
if (pos == 0 && !isEmpty()) {
removed = head;
head = head->link;
free(removed);
}
else {
prev = get_entry(pos - 1);
if (prev != NULL) {
removed = remove_next(prev);
free(removed);
}
}
}
int get_data(int pos) {
Node* p = head;
for (int i = 0; i < pos; i++) {
if (p == NULL) return -1;
p = p->link;
}
return p->data;
}
void replace(int pos, Data data) {
Node* p = get_entry(pos);
if (p != NULL)
p->data = data;
}
int size() {
int count = 0;
for (Node* p = head; p != NULL; p = p->link) count++;
return count;
}
Node* find(Data data) {
Node* p;
for (p = head; p != NULL; p = p->link)
if (p->data == data) return p;
return NULL;
}
void clear() {
while (!isEmpty()) delete(0);
}
int main() {
init();
printf("isEmpty : %d\n\n", isEmpty());
for (int i = 0; i < 5; i++) {
printf("Insert : %d\n", i * 10);
insert(i, i * 10);
}
printf("\nisEmpty : %d\n\n", isEmpty());
printf("size : %d\n\n", size());
printf("get_data(3) : %d\n\n", get_data(3));
printf("delete\n");
delete(0); delete(0);
printf("\nsize : %d\n", size());
for (int i = 0; i < size(); i++) {
printf("print data : %d\n", get_data(i));
}
printf("\nclear list\n");
clear();
printf("\nisEmpty : %d\n", isEmpty());
printf("size : %d", size());
return 0;
}
결과