연결 리스트 구조와 삽입 (Linked List)

연결 리스트 Linked List

 

개념

* node라는 구조의 집합니다.

* node = 값 + (다음 노드를 향하는 포인터)로 구성되어 있다.

 

 

[값 + 포인터] 구조가 갖는 장점

* 포인터가 다음 값의 위치를 알고 있으니 배열처럼 메모리가 빈틈없이 연속적일 필요가 없음.

  = 자료들이 산재해 있다.

 

* 자료들이 여기저기 떨어져 있다면?

  = 동적 할당 (아닐 수도 있지만 보통 동적)

 

* 연결 리스트에 최대 길이 따윈 없다! 

  = 포인터로 다음 값을 알아낸다 -> 메모리에 값이 분포될 수 있다 -> 최대 크기 설정이 없다

 

 

node의 구조

typedef struct node{
	int num;
	struct node* next;
}node_t;

* 가볍게 보면 어지러울 수 있다. 천천히 구조를 생각하자

 

* node_t = 값 + (다음 노드를 가리키는 포인터)로 구성되어 있다.

* 포인터의 자료형은 struct node*이니 이런 구조가 탄생했다.

 

* 이상한 점 = next의 자료형을 struct node*라고 하면 되지만 node_t*라고 하면 에러가 뜬다...

* 현재 크기는 8바이트! 굳이 num 한 개가 아니라 여러 변수들 넣어서 사용하는 것도 가능하다.

 

 

삽입할 주소를 알고 있는 삽입

*  삽입할 위치의 전 node 포인터 값 = new_node의 주소

* new_node 포인터 값 = 삽입할 위치의 다음 node의 주소 

* 시간 복잡도 = O(1)

 

 

무조건 Head 다음으로 삽입하는 삽입

* Head를 알고 있으니 (삽입할 주소를 알고 있는) 삽입과 같다.

* 시간 복잡도 = O(1)

void addStack_firstPosition(node_t** p, int num1) {
	//새로운 node 생성
	node_t* new_node = malloc(sizeof(node_t));
	//new_node에 값 넣기 
	new_node->num = num1;
	//new_node의 next = 원래 head의 값
	new_node->next = *p;
	//head값 = new_node
	*p = new_node;
}

* 원래 head가 가리키고 있던 곳을 new_node가 가리키게 만들고, 

  head는 new_node를 가리키게 된다.

* 함수로 만들지 않았다면 굳이 이중포인터를 사용할 필요가 없기는 하다.

  하지만 함수로 만든다면 head를 참조해야 하기 때문에 이중 포인터가 필요하다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef struct node{
	int num;
	struct node* next;
}node_t;

void addStack_firstPosition(node_t** p, int num1) {
	node_t* new_node = malloc(sizeof(node_t));

	new_node->num = num1;
	new_node->next = *p;

	*p = new_node;
}

void free_all_stack(node_t* head) {
	node_t* p = head;
	node_t* next;

	while (p != NULL) {
		next = p->next;
		free(p);
		p = next;
	}
}

void print_all_stack(node_t* head) {
	node_t* p = head;

	while (p != NULL) {
		printf("\n%d", p->num);
		p = p->next;
	}
}

int main(){
	node_t* head = NULL;

	addStack_firstPosition(&head, 2);
	addStack_firstPosition(&head, 3);
	addStack_firstPosition(&head, 5);
	addStack_firstPosition(&head, 7);

	printf("넣어진 스택 순서 head부터");
	print_all_stack(head);

	free_all_stack(&head);
	head = NULL;
}

 

* head 바로 다음에 삽입되다 보니 마지막에 넣은 7이 가장 먼저 출력됐다.

 

 

 

 

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.