リンクリスト

Listを実現する2つの方法

Array

Linked List

メモリストレージ方式の違い

リンクリストの実装

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
   int data;
   struct node* next; //자기 참조 구조체
} NODE;

create

NODE* create(int data) {
	NODE* new_node = (NODE*)malloc(sizeof(NODE));
	new_node->next = NULL;
	new_node->data = data;
}

insert

//해당 함수는 data 오름차순으로 정렬된 데이터들에 적절한 위치에 삽입합니다.
//데이터를 들어놓은 data 만들기
	//노드 중간 삽입을 할 경우 커서 두개 만드는 이유
	//과정 -> 삽입 이전노드의 위치와 삽입 이후 그다음 노드의 위치도 알아야 한다
	//1.삽입하려는 새로운 노드 생성
	//2.삽입하려는 이전 노드까지 이동
	//3.삽입 노드의 link를 이전 노드의 link로 저장
	//4.이전 노드의 link를 삽입 노드의 주소로 저장
NODE* insert(NODE* head, int data) {
	NODE* node, * p, * q;
	node = create(data);
	
	p = head;
	q = head;
	//커서 =원하는 위치로 옮겨주기 순서: q new data p
	while (p != NULL) {
		//p data가 처음으로 data보다 크면 탈출
		if (p->data > data) { //적절한 위치 찾기
			break;
		}
		//한칸씩 이동
		q = p;
		p = p->next;
	}
	//p가 맨 앞에 있다면 즉 head 앞에 있다면
	//만약 head에 아무것도 없다 해도 이 if문으로 들어간다
	if (p == head) {
		node->next = head;//node가 head를 가리키게 한다
		head = node;//head는 맨앞에 있어야 하기 떄문에 head를 맨 앞으로 이동
	}
	//제일 앞에 있는게 아니라면
	else {
		node->next = p;
		q->next = node;
	}
	return head;
}

delete

//해당 함수는 data 값을 가진 노드를 삭제합니다.
NODE* deleteNode(NODE* head, int data) {
	NODE* p, * q;
	p = head;
	q = head;
	//접근
	while (p != NULL) {
		if (p->data == data) { //삭제할 노드를 찾을 경우
			break;
		}
		q = p;
		p = p->next;
	}
	if (p == NULL) { //커서가 끝까지 이동한 것은 삭제할 노드가 없다는 것입니다.
		return head;
	}
	else if (p == head) { //삭제 노드가 가장 앞에 있을 경우
		head = head->next;
		free(p);
		return head;
	}
	else { // 삭제 노드가 중간에 있는 경우
		q->next = p->next; //삭제노드 이전노드와 삭제노드 다음노드를 연결합니다.
		free(p);
		return head;
	}
}