[📗c언어 쉽게 풀어쓴 자료구조6] 연결리스트1

👑 리스트 추상 데이터 타입

• 집합과 달리 항목 간에 순서가 있음 (집합은 없음)
• insert(): 삽입
• delete(): 삭제

-> 배열 또는 포인터로 표현할 수 있음

👑 배열로 구현된 리스트 (순차적 표현)

• 장점: 구현이 쉬움, 임의의 항목 추출 쉬움
• 단점: 중간에 삽입, 삭제가 어려움, 크기가 제한됨
• insert(): 중간 삽입, pos요소부터 뒤로 이동 후 삽입

#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 error(char* message) {
	fprintf(stderr, "%s\n", message);
}

//리스트 초기화 함수
void init(ArrayListType* L) {
	L->size = 0;
}

//공백 함수
int is_empty(ArrayListType* L) {
	return L->size = 0;
}

//포화 함수
int is_full(ArrayListType* L) {
	return L->size == MAX_LIST_SIZE;
}

//리스트 출력
void print_list(ArrayListType* L) {
	for (int 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) {
		error("리스트 오버플로우");
	}
	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++;
	}
}

//삭제 함수 (pos위치의 것)
element delete(ArrayListType* L, int pos) {
	element item;
	if (pos < 0 || pos >= L->size)
		error("위치 오류");
	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 list;
	init(&list);
	insert(&list, 0, 10); print_list(&list);
	insert(&list, 0, 20); print_list(&list);
	insert(&list, 0, 30); print_list(&list);
	insert_last(&list, 40);print_list(&list);
	delete(&list, 0); print_list(&list);
}

👑 연결 리스트

• 장점: 공간 제한 없음 (동적 할당), 중간 삽입 삭제 어려움
• 단점: 구현 어렵
• 헤드 중요!!! (첫 노드)
• 포인터로 구현 (data, link 필드로 구성)

& 연결리스트의 종류
1. 단순 연결 리스트
2. 원형 연결 리스트
3. 이중 연결 리스트

👑 단순 연결리스트

• 마지막 노드 NULL 가리킴 (마지막 노드의 link field 값: NULL)
• 노드 생성: malloc
• 노드 삭제: free

& 단순 연결 리스트의 연산

• insert_first(): 리스트의 시작 부분에 항목 삽입
• insert(): 리스트의 중간 부분에 항목 삽입
• delete_first(): 리스트의 첫 번째 항목 삭제
• delete(): 리스트의 중간 항목 삭제
• print_list(): 리스트 방문하여 모든 항목 출력

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

//insert_first 함수
ListNode* insert_first(ListNode* head, int value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}

//insert 함수
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;
}

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

//delete 함수
ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

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

int main(void)
{
	ListNode* head = NULL;
	for (int i = 0;i < 5;i++) {
		head = insert_first(head, i);
		print_list(head);
	}
	for (int i = 0;i < 5;i++) {
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}

⭕ TIL (Today I learned)

& 단순 연결리스트로 구현하는 것 코드 어려웠음. 삽입, 삭제 상상하면서 코드 보기.
또, ListNode* p하면 p자체가 포인터임!!!! head도 자체로 포인터임!!!! 그걸 가리키면, 코드 헷갈리지 않음.
단순 연결리스트에서 첫 번째에 삽입, 삭제/ 중간에 삽입, 삭제 하는 것 두 종류 있었음