06 연결리스트1

 

• 배열(array) 리스트(list)의 차이점
• 배열은 인덱스를 가진 데이터의 집합이고, 리스트는 인덱스 없이 순차적으로 저장된 데이터의 집합이다.
• 배열은 메모리에 연속적으로 저장되고 리스트는 메모리에 분산 되어 저장된다. 

6.1 배열(array)로 구현된 리스트

- 배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당됨(리스트의 순차적 표현)

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


typedef int element;
typedef struct {
	element array[MAX_LIST_SIZE]; // 배열의 정의
	int size; // 현재 리스트에 저장된 항목들의 개수
} ArrayListType;

// 오류 처리 함수
void init(ArrayListType* L)
{
	L->size = 0;
}

// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType* L)
{
	return L->size == 0;
}

// 리스트가 가득 차 있으면 1을 반환
// 그렇지 않으면 1을 반환
int is_full(ArrayListType* L)
{
	return L->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType* L, int pos)
{
	if (pos < 0 || pos >= L->size)
		printf("위치 오류");
	return L->array[pos];
}

// 리스트 출력
void print_list(ArrayListType* L)
{
	int i;
	for (i = 0; i < L->size; i++)
		printf("%d->", L->array[i]);
	printf("\n");
}

void insert_last(ArrayListType* L, element item)
{
	if (L->size >= MAX_LIST_SIZE)
	{
		printf("리스트 오버플로우");
	}
	L->array[L->size++] = item;
}

void insert(ArrayListType* L, int pos, element item)
{
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--)
			L->array[i + 1] = L->array[i];
		L->array[pos] = item;
		L->size++;
	}
}

element delect(ArrayListType* L, int pos)
{
	element item;

	if (pos < 0 || pos >= L->size)
		printf("위치 오류");
	item = L->array[pos];
	for (int i = pos; i < (L->size - 1); i++)
		L->array[i] = L->array[i + 1];
	L->size--;
	return item;
}

int main(void)
{
	// ArrayListType를 정적으로 생성하고 ArrayListType를 가리키는 포인터를 함수의 매개변수로 전달
	ArrayListType list;

	init(&list);
	insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
	insert(&list, 0, 20); print_list(&list); // 0번째 위치에 20 추가
	insert(&list, 0, 30); print_list(&list); // 0번째 위치에 30 추가
	insert_last(&list, 40); print_list(&list); // 맨끝에 40 추가
	delect(&list, 0); print_list(&list); // 0번째 항목 삭제
	return 0;
}

6.2 연결 리스트(Linked List)

- 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현

- 이 연결된 표현은 포인터를 사용하여 데이터들을 연결함

• 연결 리스트의 구조

- 연결리스트는 노드(node)들의 집합, 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용

Data field에는 우리가 저장하고 싶은 데이터가 들어감, Link field에는 다른 노드를 가리키는 포인터가 저장됨

- 연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야 만이 전체의 노드에 접근할수 있음

- 따라서 연결 리스트마다 첫번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드포인터(head pointer)라고 한다

연결 리스트의 종류

6.3 단순 연결 리스트(Single Linked List)

- 노드 들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결. 마지막 노드의 링크 필드값 NULL

• 노드의 정의

- 노드는 자기 참조 구조체(자기 자신을 참조하는 포인터를 포함하는 구조체)를 이용하여 정의됨

#include<stdio.h>
#include<stdlib.h>

typedef int element;

typedef struct ListNode { // 노드 타입을 구조체로 정의
	element data;
	struct ListNode* link;
} ListNode;

// 공백 리스트 생성
// 구조체 변수 선언
ListNode* head = NULL;

• 노드의 생성

노드의 크기만큼 동적메모리를 할당 받음, 이 동적 메모리가 하나의 노드가됨. 동적메모리의 주소를 헤드 포인터인 head에 저장

head = (ListNode*)malloc(sizeof(ListNode));

• 노드의 연결

// 두번째 노드 생성
ListNode* p;
p = (ListNode*)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

// 첫번째 노드의 링크가 두번째 노드를 가리킴
head->link = p;

#include<stdio.h>
#include<stdlib.h>

typedef int element;
typedef struct ListNode { // 노드 타입을 구조체로 정의
	element data;
	struct ListNode* link;
} ListNode;

// 오류 처리 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head; // 헤드 포인터의 값을 복사
	head = p; // 헤드 포인터 변경
	return head;
}

// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, element value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}

ListNode* delete_first(ListNode* head)
{
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}

// pre가 가리키는 노드의 다음 노드를 삭제
ListNode* delete(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

int main(void)
{
	ListNode* head = NULL;

	for (int i = 0; i < 5; i++)
	{
		head = insert_first(head, i); // insert_first()가 반환된 헤드 포인터를 head에 대입
		print_list(head);
	}

	for (int i = 0; i < 5; i++)
	{
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}