C언어 배열(array) vs 연결리스트(linked list) (feat.동적메모리 할당의 장점) - 1/2

배열과 연결리스트 두 자료구조 모두 데이터를 나열한다는 점에서 비슷하게 생각할수있습니다.

 

그러나 두 자료구조는 확실한 차이가 있습니다.

 

배열의 경우 사용이 매우 간단하다는 장점이 있는 반면, 배열의 가장 큰 단점은 크기가 고정된다는 점이다.

 

프로그램이 실행이 되고 나면 배열의 크기를 줄이거나 늘릴수없습니다. 

 

배열의 크기를 잘못 예측하여 실제보다 작은 크기로 선언할경우 저장공간이 부족하게되고 너무 큰 크기로 배열을 선언하면 메모리 저장공간을 낭비하게 됩니다

 

배열과 같이 프로그램이 실행전 메모르 크기가 결정되는 메모리할당 방법을 정적메모리 할당이라 합니다.

 

이러한 단점들을 보완하는 자료구조가 대표적으로 연결리스트(linked list)가 존재합니다.

 

연결리스트(linked list)의경우 동적메모리 할당을 이용하여 배열과는 다르게 선형 데이터 구조를 이루고 있으며

 

일종의 끈처럼 데이터 구조를 표현할 수 있다.

 

 

 

연결리스트는 배열이 가진 단점을 극복해내는 자료구조이다. 연결리스트는 크기를 동적으로 변경할수 있기 때문에

 

실행 도중 필요한 만큼 메모리를 확보할 수 있고, 필요없는 메모리는 삭제가 가능하다.

 

연결리스트의 단점으로는 포인터를 사용하기 때문에 사용법이 어렵고 오류가 났을때 문제점이 무엇인지 찾기 어렵다는점이다.

 

 

---

동적 메모리 할당

---

 

 

 

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

int	main(void){
	
	int *ptr = NULL;
	p2i = (int *)malloc(5*sizeof(int));
	
	//~~~~~
	
	free(p2i); 
}

 

malloc() 함수의 경우 stdlib.h헤더파일에 정의되어있으니 헤더파일을 포함하여야 한다.

malloc() 함수는 메모리를 할당받는 함수로 free 함수를 통해 메모리를 반납한다.

malloc() 함수는 반환되는 주소의 타입이 void* 이므로 주소를 받는 포인터에 맞춰 명시적인 타입 변환을 시켜주어야 한다.

 

예제4.1 ) 

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

typedef struct Movie_Strcut{
	char title[20]; //제목 
	int release; //개봉년도 
	int viewers; //관객수 
}movie;

int	main(void){
	
	int *iptr = (int *)malloc(sizeof(int));
	movie *mptr = (movie*)malloc(sizeof(movie));
	
	if((iptr == NULL )or(mptr == NULL)){
		printf("메모리 할당실패 \n");
		return (1);
	}
	*iptr = 20;
	printf("iptr 메모리할당후 : %d \n\n",*iptr);
	free(iptr);
	strcpy(mptr->title,"미나리");
	mptr->release = 2021;
	mptr->viewers = 100000;
	printf("mptr 메모리 할당후 제목 : %s		개봉연도: %d		관객수 %d",mptr->title,mptr->release,mptr->viewers);
	free(mptr);

	return 0;	
}

 

---

연결리스트(Linked list)

---

 

연결리스트는 하나의 구조체안에 필드로 다음 구조체를 가르키는 포인터와 데이터를 필드로 갖는 구조체를 의미한다.

 

예제) 단순 연결리스트 다루기 기초

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node{
	int data;
	struct Node* link;
}Node;

int main(){
	Node *head, *temp;
	head = (Node *)malloc(sizeof(Node));
	
	if(head ==NULL)	exit(1);
	
	head->data = 10;
	head->link = NULL;
	
	temp = (Node *)malloc(sizeof(Node));
	if(temp ==NULL)	exit(1);
	
	temp->data = 20;
	temp->link = NULL;
	head->link = temp;
	
	printf("head-> %d ->%d \n",head->data, head->link->data);
	free(temp);
	free(head);
	
	return 0;
}

 

단순연결리스트 함수들

함수	설명	반환값
create_node	동적으로 노드를 생성	노드 포인터
count_nodes	연결리스트의 길이를 계산	길이
search_node	연결리스트의 노드를 탐색	노드 포인터
insert_node	연결리스트에 노드를 상비	없음
delete_node	연결리스트에서 노드를 삭제	노드 포인터
concatenate_lists	두 연결리스트의 결합	헤드 포인터
reverse_list	연결리스트 순서를 반대로 변경	헤드포인터

 

 

이어보기