Linked List(연결리스트)

List를 구현하는 두가지 방법

Array

• 구현이 쉽고 단순합니다.
• random access가 가능합니다.
• 리스트의 중간에 새로운 데이터를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 합니다.
• 크기가 고정되어 있습니다.-reallocation 필요
• 각각의 항목들이 메모리에 연속적으로 저장됩니다.

Linked List

• 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며,
• 크기의 제한이 없습니다.
• random access가 불가능하여 필요한 노드에 접근이 불편합니다.
• 각각의 항목들이 메모리에 연속적으로 저장되지 않으며 연결된 다음 주소가 함께 저장됩니다

메모리 저장 방식의 차이

• Array는 각각의 항목들이 메모리에 연속적으로 저장됩니다.
• Linked List는 각각의 항목들이 메모리에 연속적으로 저장되지 않습니다.

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

사진 출처
http://dorson23.blogspot.com/2018/02/c-1-linkedlist.html
https://server-engineer.tistory.com/130