---

Array & ArrayList & LinkedList

---

1. 세 자료구조 비교

• Array : index로 빠르게 값을 찾을 수 있다.
• LinkedList : 데이터의 삽입/삭제가 빠르다.
• ArrayList : 데이터를 찾는데 빠르지만, 삽입/삭제가 느리다.

2. Array

• 선언할 때 크기와 데이터 타입을 지정해야 한다.(int[] arr = new int[10])

• 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조이다.

• 데이터가 계속 늘어날 때, 최대 사이즈를 알 수 없을 때 사용하기에는 부적합하다.

• 중간에 데이터를 삽입/삭제할 때 사용하기에는 부적합하다.

• index가 존재해서 데이터의 위치를 바로 알 수 있어 검색에 편하다.

• 이러한 단점을 보완 : List

3. List

• 크기를 정해주지 않아도 된다.

• array에서 index가 중요했다면, List에서는 순서가 중요하다.

• 중간에 데이터 삽입/삭제가 용이하고 index를 가지고 있어 검색도 빠르다.

• 중간에 데이터 삽입/삭제 시 시간이 오래걸린다는 단점이 존재한다.

4. LinkedList

• 단일, 다중 등 여러가지가 존재한다.(단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리킨다.)

• 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다.

• 데이터의 중간에 삽입/삭제를 하더라도 전체를 돌 필요 없이 이전 값과 다음 값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.

• K번째 값을 찾아라라는 예시에서 사용하기에는 부적합하다.

• LinkedList는 처음부터 살펴봐야하므로 순차 검색에 있어서는 시간이 오래 걸린다.