ArrayList와 Linked List 비교

N사 면접 질문


ArrayList와 LinkedList의 차이점과 장단점은 무엇일까요?

---

비슷한 성격의 두 List의 차이점

ArrayList와 Linked List는 저장해야하는 객체의 수를 정확히 모를 때 사용하곤 했죠. 원하는 위치에 저장하거나 순차적으로 삭제, 접근할 때 등등 사용하는 입장에서 기능적으로는 비슷한 두 List는 구조적인 설계 측면에서 보면 차이점을 알 수 있습니다.

• ArrayList

  
  ArrayList는 re-size array기반으로 구현된 List 입니다. 내부적으로 크기가 고정인 배열로 이루어져 있고 값이 포화가 될 경우 전보다 더 길이가 긴 배열을 새로 생성하여 이전 값들을 복사하는 방식으로 무한한 객체를 저장하도록 구현한 것입니다.

• Linked List

  
  Linked List는 값과 Node를 가리키는 포인터를 가지고 있는 Node를 기반으로 구현된 List 입니다. ArrayList와 달리 주소의 연결로 객체를 저장하기 때문에 보다 객체의 저장/ 삭제가 용이합니다.

구조적인 측면에서 나오는 장단점

• ArrayList의 추가와 삭제

  
  ArrayList는 내부적으로 크기가 고정된 배열로 이루어져 있기 때문에 포화 상태일 때 값이 추가가 되면 배열 크기를 늘려주는 작업을 반드시 해야 하고 이전 값들을 복사하는 작업이 추가로 필요합니다. 반대로 배열의 중간 인덱스에서 삭제 작업이 이루어진다면 배열 중간의 값을 빈공간으로 둘 수 없기에 뒤에 있는 값들을 1칸씩 땡겨오는 작업이 필요합니다.
  이는 ArrayList의 추가와 삭제는 O(n)의 시간을 소요한다는 것을 나타냅니다.

• Linked List의 추가와 삭제
  
  Lineked List는 Node의 포인터로 서로 연결되어 있어 추가와 삭제 작업에서는 이 포인터의 값을 변경하면 쉽게 이루어 집니다. 단, 추가와 삭제 하려는 위치가 List의 양 끝이 아니라면 해당 위치를 찾는 search time이 필요하게 됩니다.
  따라서 Linked List의 추가와 삭제는 search time + O(1)의 시간을 소요한다는 것을 나타내고 ArrayList보다 좀 더 효율적이라는 것을 알 수 있습니다.

---

• ArrayList의 요소 접근
  
  ArrayList는 내부적으로 배열로 구현되어 있습니다. 이는 Random Access가 가능한 것으로 원하는 인덱스의 접근이 O(1)로 자유롭다는 뜻입니다.

• Linked List의 요소 접근

  
  Linked List는 List의 양 끝을 가리키는 head,tail 포인터만 가지고 있어 Sequential Access만 가능합니다. 따라서 중간 값에 접근하기 위해서는 head또는 tail에서 Node의 포인터값을 순차적으로 이동하면서 찾는 과정이 필요합니다. 이는 O(n)의 시간을 소요해서 ArrayList보다 비효율적입니다.

---

• ArrayList의 메모리 구조

  
  ArrayList는 배열 기반으로 연속된 기억 장소의 할당으로 메모리 구조가 생성됩니다. 이는 배열의 길이만큼 메모리를 계속 점유하고 있는 상태이며 배열의 값이 비어 있어도 그 길이만큼 기억 장소를 낭비하게 됩니다.
  하지만 연속하게 할당되어 있기 때문에 순차적인 접근을 할때에는 공간 지역성의 특성을 지닙니다.

• Linked List의 요소 접근

  
  Linked List는 Node의 연결을 기반으로 구현되어 있어 연속적인 할당을 보장하지 않습니다. 그때의 메모리 상황과 맞게 필요한 크기만큼 자유롭게 메모리에 적재되어 연속적으로 할당이 될수도 안될수도 있습니다. 자유로운 메모리 구조의 특성은 사용하지 않게 되는 Node의 기억 장소를 재활용 할 수 있게 해주어 메모리를 좀 더 효율적으로 사용할 수 있게 해줍니다. 하지만 순차적인 접근을 할 때에는 연속적인 메모리 할당을 보장할 수 없어 ArrayList 보다 시간을 소요할 수 있습니다.

참고

• 자료구조: Linked List 대 ArrayList