[자료구조] 1. Array, List (ArrayList, Linked List)

Array (배열)

같은 자료형에 대한 자료들을 메모리에 연속적으로 저장하기 위해 사용된다.
물리적 저장 순서와 논리적 저장 순서가 일치하는 특징이 있다.

선언되면 컴파일 타임에 할당할 사이즈를 미리 정해놓고 정적 메모리를 할당함 ➡ 크기가 미리 정해지며, 사이즈 변경이 힘듦

index를 통한 random access가 가능하다. (이는 배열의 원소들이 연속된 메모리 위치에 저장되기 때문임)

 

크기 : 자료형에 대한 메모리 할당 크기 * 배열 요소의 개수

삽입 : O(N)
삭제 : O(N)
탐색 : O(1)
▶ 삽입/삭제 시에는 해당 원소를 삭제한 뒤, 다른 원소들의 조정이 필요하기 때문에 worst case가 O(N)이 됨

 

배열을 사용하기 좋은 경우

• 데이터의 개수가 정해져 있다
• 데이터 탐색을 할 일이 많다

 

Code

	// 크기가 10인 Array 선언 및 초기화
	int array_size = 9;		// 배열에 들어간 원소의 개수, 원소를 9개 넣을 것
	int my_array[10] = { 0,1,2,3,4,5,6,7,8, };		// 현재 [0,1,2,3,4,5,6,7,8,0]과 같이 들어있다

	// 삽입 : index가 3인 곳에 원소 999를 넣을 때
	int to_insert = 3;
	int to_insert_value = 999;
	for (int i = array_size; i > to_insert; i--)
	{
		my_array[i] = my_array[i - 1];
	}
	my_array[to_insert] = to_insert_value;
	array_size++;

	// 삭제 : index가 5인 원소를 삭제할 때
	int to_delete = 5;
	for (int j = to_delete; j < array_size - 1; j++)
	{
		my_array[j] = my_array[j + 1];
	}
	my_array[array_size] = 0;
	array_size--;

	// 탐색 : index가 8인 원소를 출력할 때
	cout << my_array[8];		// 8번째에 있는 값인 "7" 출력

 

---

 

List

데이터를 순서 있게 저장하기 위해 사용된다.

 

구현 방법에 따라 arrayList/linked list로 나뉜다

Dinamic Array ( [C++] Vector, [Java] ArrayList )

배열을 이용해 구현한 리스트
처음에는 고정된 크기를 할당받지만, 이를 넘어설 경우 동적으로 크기가 조절되는 특징이 있음

index를 사용하여 특정 값에 접근은 빠르지만 데이터 추가와 삭제가 느림

 

Linked List

값을 가진 노드에 다음 노드를 연결하는 식으로 구현한 리스트
한 노드에 값이 저장되어 있고, 다음/이전 값의 주소를 저장해서 연결

단일 Linked List -> 해당 노드 다음 노드를 알 수 있는 것
다중 Linked List -> 해당 노드 앞의 노드와 다음 노드 모두를 알 수 있는 것

물리적 저장 순서와 논리적 저장 순서가 일치하지 않는다. ➡ 탐색할 때 처음부터 다 찾아봐야 함
따라서 삽입/삭제 자체는 빠르지만 해당 지점까지 접근해야 해서 O(N)일 수도 있음

배열과 다르게 데이터를 빈틈없이 저장할 수 있다.
(삭제할 때 삭제 후, 원소를 연속적으로 위치시킴)

 

Linked List를 사용하기 좋은 경우

• 데이터 삽입과 삭제가 많을 경우

 

Code

Single Linked List : https://github.com/yarncha/computer-science/blob/main/Data%20Structure/single_linked_list.cpp

GitHub - yarncha/computer-science: Computer Science 공부 후 지식 쌓기

class를 이용해 insert, delete를 구현하고 추가로 검색 기능이랑 출력, 사이즈 출력 등을 자세하게 구현해 보았다.

 

 

해당 글은 다음 글들을 참고하여 작성했습니다.
https://cis.stvincent.edu/html/tutorials/swd/arrays/arrays.html
https://opentutorials.org/
https://xlinux.nist.gov/dads/
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure
https://github.com/gyoogle/tech-interview-for-developer#data-structure
https://github.com/WooVictory/Ready-For-Tech-Interview#-data-structure-