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

리스트(List, Linear List)

데이터를 순서대로 나열한 형태의 자료구조이다.

 - 순차 리스트(ArrayList): 배열 기반으로 구현된 리스트 => 논리적인 순서와 물리적인 순서가 같다.

 - 연결 리스트(LinkedList): 메모리의 동적 할당을 기반으로 구현된 리스트

리스트의 특징

 - 데이터를 나란히 저장한다.

 - 중복된 데이터의 저장도 허용된다.

 - 임의의 위치에 있는 항목에 대한 연산이 허용된다.

배열 기반 리스트의 장점

 - 데이터의 참조가 쉬움

배열 기반 리스트의 단점

 - 배열의 길이가 초기에 결정되어야하고 중간에 변경이 불가능하다.

 - 삭제의 과정에서 데이터의 이동이 자주 발생한다.

리스트의 추상 자료형

데이터

임의의 접근 방법을 제공하는 같은 타입의 요소들이 나란히 저장된 자료구조

연산

init(): 리스트의 초기화

insert(): 요소 삽입

delete(): 요소 삭제

get(): 요소 반환

isEmpty(): 리스트가 비어있는지 확인

isFull(): 리스트가 가득찼는지 확인

replace(): 요소 교체

size(): 요소의 개수 반환

find(): 요소가 있는지 확인

clear(): 리스트를 비움

아래는 c에서 배열을 기반으로 리스트의 구현입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100

typedef int Element;
Element data[MAX_LIST_SIZE];
int length = 0;

//초기화
void init() {
	length = 0;
};

//비우기
void clear() {
	length = 0;
};

//비어있는지 확인
int isEmpty() {
	return length == 0;
};

//가득 찼는지 확인
int isFull() {
	return length == MAX_LIST_SIZE;
};

//pos 위치에 e삽입
void insert(int pos, Element e) {
	if(!isFull() && pos <= length) {
		for (int i = pos; i < length; i++) {
			data[i + 1] = data[i];
		}
		data[pos] = e;
		length++;
	}
};

//pos 위치에 있는 데이터 삭제
void delete(int pos) {
	if (!isEmpty() && pos <= length) {
		for (int i = pos; i < length; i++) {
			data[i] = data[i + 1];
		}
		length--;
	}
};

//pos 위치에 있는 데이터를 e로 교체
void replace(int pos, Element e) {
	data[pos] = e;
};

//pos 위치에 있는 데이터 반환
int get(int pos) {
	return data[pos];
};

//e와 값이 같은 데이터를 찾으면 해당 데이터의 인덱스 반환
int find(Element e) {
	if (!isEmpty()) {
		for (int i = 0; i < length; i++) {
			if (e == data[i]) return i;
		}
	}
};

//리스트 내부의 요소 전부 출력
void printList() {
	if (!isEmpty()) {
		for (int i = 0; i < length; i++) {
			printf("%d ", data[i]);
		}
		printf("\n");
	}
}
//리스트의 요소의 개수
int size() {
	return length;
};

추상적 자료형(Abstract Data Type, ADT)

기능을 어떻게 구현하는 지에 대한 방법은 나타내지 않고 순수하게 기능이 무엇인지만 언급한 것을 추상 자료형(ADT)라 한다.

특징

 - 무엇인지만 명시하고 어떻게 구현하는지는 언급하지 않는다. 

 - 사용자가 내부 구현을 알지 못해도 사용할 수 있다.

 - 세부 구현 방법이 언급되지 않음으로써 세부 내용을 숨겨 정보의 은닉이 가능하다.

 - 자료구조의 구현과 구현된 자료구조의 활용은 완전히 구분되도록 정의해야 한다.

추상적 자료형의 예시

 - 스택

 - 큐

 -  덱

 - 리스트 등

추상 자료형의 정의

한 게임 내에 가상의 총기가 있다고 가정하고 추상 자료형을 정의해보면

추상 자료형: 총

- Data: 방아쇠, 탄 수

- Operation: Firing(), Reload()

이를 C의 헤더 파일로 구현하면 아래와 같이 될 것이다.

typedef struct{
	int trigger;
    int ammo;
} Gun;

void Fire();
void Reload();