[알고리즘] 배열과 연결리스트

배열 

; 같은 타입의 변수들로 이루어진 유한 집합

- 가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치

- 삽입과 삭제 시 시간 복잡도 o(N)

- 배열 요소(배열을 구성하는 각각의 값), 인덱스(위치를 가리키는 숫자)로 구성

 

1차원 배열

int main() {
	int arr[3] ={10,20,30};
	for(int i=0;i<3;i++){
		printf("%d %p\n",arr[i],&arr[i]);	 //arr[i]는 arr[i]의 값,  &arr[i]는 arr[i]의 주소 값 
	}
	int *p=arr;				//포인터형 변수 p는 arr를 가리킴 
	for(int i=0;i<3;i++){
		printf("%d %p\n",*(p+i),p+i)		//*(p+i) = arr[i], p+i = &arr[i] 
	}
	return 0;
}

2차원 배열

int main() {
	int arr[3][2]={{1,2},{3,4},{5,6}};
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			printf("%d %p\n",arr[i][j],&arr[i][j]);
		}
	}
	int *p=arr[0]; // = &arr[0][0]과 동일한 식(배열의 첫번째 요소의 주소값 = 배열의 값)
	int *p2=&arr[0][0];
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			printf("%d %p\n",*(p++),p2++);
		}
	} 
	return 0;
}

3차원 배열

int main() {
	int arr[3][2][2]={{{1,2},{3,4}},{{5,6},{7,8}},{{9,10},{11,12}}};
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			for(int l=0;l<2;l++){
				printf("%d %p\n",arr[i][j][l],&arr[i][j][l]);
			}
		}
	}
	int *p=arr[0][0]; 
	int *p2=&arr[0][0][0];
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			for(int l=0;l<2;l++){
				printf("%d %p\n",*(p++),p2++);
			}
		}
	} 
	return 0;
}

 

연결 리스트

; 자기 자신 다음에 어떤 원소인지만을 기억하고 있음

- 배열의 문제점을 해결하기 위한 자료구조

- 삽입과 삭제 시 시간 복잡도 O(1)

- 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기에 원하는 위치를 탐색할 경우, 첫번째 원소부터 다 확인해봐야 함

-> 시간 복잡도 O(n)

- Tree의 근간이 되는 자료구조