[자료구조] Array vs ArrayList vs LinkedList

 

세 자료구조를 한 문장으로 정의하면 아래와 같이 말할 수 있다.

 

 

 

 

 

 

• Array는 index로 빠르게 값을 찾는 것이 가능하다.
• ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느리다.
• LinkedList는 데이터의 삽입 및 삭제가 빠르다.

 

 

ArrayList vs LinkedList 차이

ArrayList는 데이터들이 순서대로 늘어선 배열의 형식을 취하고 있지만, 
LinkedList는 자료의 주소값으로 서로 연결된 형식을 가지고 있다.

 

이러한 구조에 의해 둘은 각각의 장단점을 가지고 있다.

 

 

ArrayList

• 원하는 데이터에 무작위로 접근할 수 있다.
• 리스트의 크기가 제한되어 있으며, 리스트의 크기를 재조정하는 것은 많은 연산이 필요하다.
• 데이터의 추가 / 삭제를 위해서는 임시 배열을 생성하여 복제하고 있어 시간이 오래 걸린다.

 

 

LinkedList

• 리스트의 크기에 영향 없이 데이터를 추가할 수 있다.
• 데이터를 추가하기 위해 새로운 노드를 생성하여 연결하므로 추가/삭제 연산이 빠르다.
• 무작위 접근이 불가능하며, 순차 접근이 가능하다.

 

 

---

 

Array vs Linked List

 

Array

가장 기본적인 자료구조인 Array 자료구조는, 
논리적 저장 순서와 물리적 저장 순서가 일치한다.

따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다.
즉, random access가 가능하다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)),
또 한 가지의 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다.

만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때,
배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다.

따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 
shift 해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 

그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.


삽입의 경우도 마찬가지이다. 
만약 첫번째 자리에 새로운 원소를 추가하고자 한다면
모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

 

 

 

Linked List

이 부분에 대한 문제점을 해결하기 위한 자료구조이다.

각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.
따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다.

하지만 Linked List 역시 한 가지 문제가 있다.

이렇게만 보면 가장 좋은 방법 같아보이지만,
List의 k번째 값을 찾아라에서는 비효율적이다.

array나 arrayList에서는 index를 갖고 있기 때문에 검색이 빠르지만,
LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점이 존재한다.

원하는 위치에 삽입을 하고자 하면
원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. 

Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다.
이것은 일단 삽입하고 정렬하는 것과 마찬가지이다.
이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때,
그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고,
삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 

 

이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며,

Tree 에서 사용되었을 때 그 유용성이 드러난다.

 

 

 

---

출처

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Array%20vs%20ArrayList%20vs%20LinkedList.md
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Array.md
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Linked%20List.md
• https://javanewbie.tistory.com/48
• https://blex.me/@baealex/%EC%B7%A8%EC%A4%80%EC%83%9D%EC%9D%B4-%EC%83%9D%EA%B0%81%ED%95%98%EB%8A%94-%EA%B0%9C%EB%B0%9C%EC%9E%90-%EA%B8%B0%EC%88%A0%EB%A9%B4%EC%A0%91-%EC%A4%80%EB%B9%84