99코딩

연결 리스트(Linked List)

메모리의 동적 할당을 기반으로 하는 리스트

연결 리스트의 구조

 - 노드(Node): 아래 그림의 상자 같은 데이터 덩어리, 데이터 필드(data field)와 링크 필드(link field)로 구성

 - 헤드 포인터(Head Pointer): 첫 번째 노드의 주소를 저장하는 포인터

연결 리스트의 특징

 - 노드들은 메모리의 어느 곳에나 위치할 수 있다. => 노드들의 주소가 연결 리스트 상의 순서와 동일하지 않다.

 - 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하며, 동적으로 생성하기에 미리 공간을 확보할 필요가 없다.

 - 링크필드를 위한 추가 공간이 필요하다.

 - 배열에 비해 연산의 구현이나 사용 방법이 복잡하다.

 - 오류가 없더라도 메모리의 동적 할당과 해제가 빈번하게 일어나면 프로그램이 느려질 수 있다.

연결 리스트의 종류

단순 연결 리스트(Singly Linked List): 하나의 방향으로만 연결

원형 연결 리스트(Circular Linked List): 단순 연결 리스트와 같으나 마지막 노드의 링크 값이 첫 번째 노드를 가리킴

이중 연결 리스트(Doubly Linked List): 각 노드마다 포인트가 2개씩 존재하여 선행 노드와 후속 노드를 모두 가리키는게 가능

연결 리스트의 추상 자료형

데이터

같은 타입의 요소들이 순서를 가지고 저장된 데이터

연산

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;
}