자료구조 공부#13 (연결리스트)

 

2021.04.08 - [전체글] - 자료구조 공부#12 (덱)

 

---

리스트란?

2021.03.07 - [이론공부/자료구조] - 자료구조 공부 #1 (자료구조와 알고리즘)

자료구조 공부 #1 (자료구조와 알고리즘)

1강에 들은 자료구조중 리스트에 대한 가벼운 내용참고

 

 

C에서 리스트 기본 연산

L = (item0 , item1, item2, ...... itemn-1)

• 리스트 새로운 항목 추가
• 리스트 항목 삭제
• 리스트에서 특정한 항목 탐색

리스트 객체 구조

교수님이 제시해주신 리스트의 객체 추상 구조

배열로 리스트 구현 구조

 

ArrayListType 구조체

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

자세한 내용은 주석을 참고하자

 

C로 구현하기

// 에러 출력
void error(const char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

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

// 리스트 공백 1, 공백 아님 0
int is_empty(ArrayListType* L) {
	return L->size == 0;
}


// 리스트 가득차있으면 1, 아니면 0
int is_full(ArrayListType* L) {
	return L->size == MAX_LIST_SIZE;
}

// get_entry
element get_entry(ArrayListType* L, int pos) {
	if (pos < 0 || pos >= L->size)
		error("위치오류");
	return L->array[pos];
}

// 리스트 출력 함수
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;
}

insert_fist 함수에 경우는 자신이 직접 구현해 보시란다.
혹여 이 글을 보고 구현해보는 사람들은 해보길 권장한다.

void insert_fist(ArrayListType* L, element item) {
	if (L->size >= MAX_LIST_SIZE) {
		error("리스트 오버플로우");
	}
	if (!is_full(L)) {
		for (int i = (L->size - 1); i >= 0; i--)
			L->array[i + 1] = L->array[i];
		L->array[0] = item;
		L->size++;
	}
}

내가 구현해본 insert_fist, 리스트 맨앞 0자리 뒤에 아이템들을 다 뒷칸으로 넘기고, 빈 0 자리에 아이템을 넣는 구조이다.

 

// 특정 pos 에 아이템 추가
void list_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 list_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;
}

 

list_insert()

list_insert() 작동구조

특정 리스트 값들을 pos 를 기준으로 전부 뒤로 넘기고, pos에 item을 넣는 구조이다.

 

list_delete()

list_delete() 작동구조

list_insert() 와는 다르게 pos 를 기준으로 전부 앞으로 넘기고 pos에 item은 뺴는 구조 이다.

 

 

 

---

리스트 연결된 표현 (Linked list)

• 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장
• 노드는 데이터 필드와 링크 필드로 구성
  • 데이터 필드 - 리스트의 원소, 데이터 값을 저장하는 곳
  • 링크 필드 - 다른 노드의 주소값을 저장하는 장소(포인터)

Linked list 삽입과 삭제

장점

• 삽입, 삭제 용이하다
• 연속된 메모리 공간이 필요없다
• 크기 제한이 없다

단점

• 구현이 어려운 편이다
• 오류가 발생하기 쉽다

 

노드의 구조

노드 구조

연결 리스트 종류

 

 

연결 리스트 종류 화살표(포인터)

 

 

단순 연결 리스트 구현

typedef int element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
} ListNode;

노드

 

 

ListNode* head = NULL;

head = (ListNode*)malloc(sizeof(ListNode));
head->data = 10;
head->link = NULL;

 

리스트 생성

ListNode* p;

p = (ListNode*)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

2 번째 노드 생성

 

head->link =p;

 

1, 2 번쨰 노드 연결

단순 연결 리스트 연산

 

 

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_first()

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

 

insert()

delete_first()

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

 

delete_first()

 

delete()

ListNode* list_delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

delete()

 

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

typedef int element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
} ListNode;

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

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

ListNode* list_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);
		print_list(head);
	}
	insert(head, head->link, 9);
	print_list(head);

	list_delete(head, head->link);
	print_list(head);

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

	return 0;
}

 

단순 연결리스트 과제겸, 내가 직접 타이핑한 코드

 

---

느낀점 : list 구조를 잘 이해하자.