과제를 할 때 어떤 자료구조를 선택하는 것이 효율적일지 고민을 많이 한다. 이때 자료구조의 차이점을 잘 알고 있으면 선택이 쉬워진다. gnl 보너스를 진행하다가 배열과 리스트 각각의 특징과 차이점이 궁금하여 공부해 보게 되었다. 먼저 각각의 특징을 간단히 알아보고 차이점을 따져보며 자세히 비교를 해보겠다.

1. 배열이란?

• 같은 특성을 갖는 원소들이 순서대로 구성된 집합으로 선형자료구조에 속한다.
• 배열의 특징으로는 배열은 고정된 크기를 가지기 때문에 크기를 정해줘야 사용할 수 있으며, 메모리 상에 연속적으로 존재한다.

int main()
{
	int arr[10];
	char str[100];
	
	int arr2[10] = {0,1,2,3,4,5,6,7,8,9}
}

• 메모리상에 연속적으로 존재해 있어 인덱스를 활용해 데이터의 접근과 수정이 빠르게 이루어진다.

#include 

int main()
{
	int arr[10] = {0,1,2,3,4,5,6,7,8,9}

	int a = arr[3];
}

2. 리스트란?

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

  

• 크기가 가변적이고 데이터를 빈틈없이 적재할 수 있어 메모리의 낭비가 없다.

• 데이터들이 순차적으로 구성되어 있지만 메모리 상에서 연속적으로 존재하진 않는다.

3. 이 둘의 차이점은?

1. 메모리 상의 데이터의 순서

   배열은 연속적으로 리스트는 불연속적으로 존재한다. 이 뜻은 배열은 원소 하나하나의 메모리 주소가 이어져있다는 뜻이고, 리스트는 그렇지 않다는 것이다.

   연속적이라는 뜻은 단어로만 들으면 잘 와닿지 않는다. 눈으로 확인하기 위해 배열을 선언하고 메모리의 주소를 찍어보는 코드를 짜고 뽑아보겠다.

   • 배열 속 원소의 주소값을 확인하기 위한 코드

   #include <stdio.h>
   
   int main()
   {
   	int i = 0;
   	int arr[10] = {0,1,2,3,4,5,6,7,8,9};
   
   	while (i < 10)
   	{
   		printf("%d번째 원소의 주소값은 %p입니다.\\n", i, &arr[i]);
   		i++;
   	}
   
   	return (0);
   }
   

   • 배열의 주소값을 뽑은 결과 : int type은 4byte이므로 배열의 각 원소의 주소가 4씩 증가하는 모습을 볼 수 있다.

     

   • 리스트의 주소값을 확인하기 위한 코드

     #include <stdio.h>
     #include <stdlib.h>
     
     struct node{
     	int data;
     	struct node* next;
     }node;
     
     int main()
     {
     	struct node* first;
     	struct node* second;
     	struct node* third;
     
     	first = (struct node *)malloc(sizeof(struct node));
     	second = (struct node *)malloc(sizeof(struct node));
     	third = (struct node *)malloc(sizeof(struct node));
     
     	first->data = 0;
     	first->next = second;
     
     	second->data = 1;
     	second->next = third;
     
     	third->data = 2;
     	third->next = NULL;
     
     	printf("first의 주소는 %p 입니다\\n", &first);
     	printf("second의 주소는 %p 입니다\\n", &second);
     	printf("third의 주소는 %p 입니다\\n", &third);
     
     	return (0);
     }
     

   • 리스트의 주소값을 뽑은 결과

     

   ⇒ 결론적으로 메모리 주소의 연속성은 데이터의 조회, 수정과 관련이 있다.

   배열의 경우 메모리 상의 주소가 연속적이기 때문에 인덱스를 이용해 빠르게 값에 접근을 할 수 있는 것이고, 리스트는 내가 원하는 값이 나올 때까지 조건문을 돌려가며 첫 번째 노드부터 차례로 조회해 보아야 한다.

2. 삽입 및 삭제 방법과 복잡도

   배열의 경우 처음과 끝이 아닌 원소를 삽입할 때 원하는 자리를 비워놓기 위해 데이터를 한 칸씩 미뤄야한다. 그마저도 미리 선언된 배열의 공간이 충분하다는 가정하에 가능하다. 삭제도 마찬가지로 삭제된 자리를 채우기 위해 데이터를 한 칸씩 다 당겨야 한다.

   리스트는 크기를 미리 지정하지 않고 다음 노드를 가리키는 포인터의 주소만 변경해 주면 되기 때문에 삽입과 삭제가 비교적 쉽게 가능하다.

4. 언제 어떤 것을 쓰면 좋을까

데이터의 순서를 바꿔가며 삽입 또는 삭제 연산을 많이 사용 할때는 리스트, 배열의 끝에만 삽입, 삭제를 하고 빠르게 값에 접근해야 할 일이 많을 때는 배열을 사용하는 것이 좋다. 위의 내용을 잘 숙지하고 있으면 주어진 문제에서 가장 효율적으로 사용할 수 있는 자료구조를 선택할 수 있을 것이다.