Array vs ArrayList vs LinkedList

1. Array

• index로 접근이 가능하다.
• 검색이 용이하다.
• 배열 크기가 정해져있고, 연속된 메모리 공간에 저장된다.
• 중간에 데이터를 저장, 삭제하는 경우 비효율적이다.

int arr[10];
string arr[5];

와 같이, 선언할 때 크기와 데이터타입을 지정해 주어야 한다.

2. ArrayList

• 선언할 때 크기를 지정해주지 않아도 된다.
• C++에서는 벡터를 생각하면 된다.
• array에서는 배열에 접근하기 위해 index가 중요했지만, list에서는 데이터의 순서가 중요하다.
• 배열 크기가 동적이라는 장점이 있지만, 중간에 데이터를 삽입, 삭제할 경우 여전히 시간이 많이 걸린다.

3. LinkedList

• 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 구현된다.
• index로 접근하지 못하고 헤드부터 순차적으로 접근해야하기 때문에, 탐색 시에는 비효율적이다.
• 포인터 비용이 추가적으로 발생한다.
• 메모리가 연속적이지 않아서 캐시 효과를 누리지 못한다.

struct Node{
	int data;
    	Node* nxt;
};