Array vs ArrayList vs LinkedList

Array(배열)

- Index로 빠르게 값을 찾는 것이 가능하다.

 

- 배열을 선언할 때 크기와 데이터 타입을 지정해주어야 하기때문에, 만약 계속 데이터가 늘어나는 경우가 발생하거나, 최대 사이즈를 알 수 없는 경우에는 적합한 자료구조 선택이 아니다. -> 이런 단점을 보완하고자 List가 등장하였다.

 

- Index가 중요하다.

 

- 중간에 데이터를 삽입하거나 삭제할때도 굉장히 비 효울적이다. (비용이 많이 듬) -> 이런 단점을 보완하고자 List가 등장하였다.

 

ArrayList

- 배열처럼 선언할때 크기와 데이터 타입을 지정해주지 않아 된다.

 

- 데이터를 찾는데 빠르게 찾을 수 있지만, 중간에 데이터를 추가 및 삭제할때 시간이 오래 걸림 ->이런 단점을 보완하고자 LikedList가 등장하였다.

 

- 순서가 중요하다.

 

LinkedList

- 연속적인 메모리 위치에 저장되지 않은 선형 데이터 구조이다. (포인터 사용)

 

- 각 노드는 데이터 필드와 다음노드에 대한 참조를 포함하는 노드로 구성되어 있다. 

 

- 배열처럼 선언할때 크기와 데이터 타입을 지정해주지 않아 된다.

 

- 한 노드에 연결된 다른 노드의 포인터 위치를 가리키는 방식으로 되어 있어 데이터의 삽입, 삭제가 빠르다.

 

- 단일 LikedList는 뒤에 따라오는 노드의 포인터 위치를 가리키고, 다중 LikedList는 앞 뒤 모든 노드를 가리킨다. 

 

- 하지만 검색에 있어서는 Array 나 ArrayList 처럼 Index를 갖고 있지 않기 때문에, 처음부터 데이터를 순회해야 하므로(순차검색) 시간이 오래 걸린다.

 

- 순서가 중요함

---

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

 

<Data structures> chapter 3, Array vs ArrayList vs LinkedList end

---