[자료구조] Linked List와 Array List 차이는?

링크드 리스트와 어레이 리스트는 모두 데이터를 저장하는 자료 구조이지만, 구현 방식과 성능 특성에서 차이가 있습니다.

1. 구현 방식

• 어레이 리스트 (Array List):
  • 내부적으로 연속된 메모리 공간을 사용하여 데이터를 저장합니다.
  • 배열로 구현되며, 인덱스를 사용해 요소에 접근합니다.
  • 고정된 크기의 메모리 블록을 사용하고, 크기가 초과하면 크기를 늘리기 위해 새로운 배열을 할당하고 기존 값을 복사하는 방식으로 처리됩니다.
• 링크드 리스트 (Linked List):
  • 각 요소가 데이터와 '다음' 요소를 가리키는 포인터(혹은 참조)를 포함하는 노드로 구성됩니다.
  • 요소들이 연속된 메모리 공간에 저장되지 않고, 각각의 노드가 다른 노드를 참조하는 형태입니다.

2. 특징

• 어레이 리스트:
  • 장점:
    • 인덱스 접근 시간: O(1)로 빠릅니다.
    • 메모리 관리가 간단하고, 동적 배열로 크기 조정이 가능합니다.
  • 단점:
    • 삽입/삭제 성능: 중간에 요소를 삽입하거나 삭제할 때 O(n)의 시간이 걸립니다.
    • 배열 크기 초과 시 새로운 배열을 할당하고 기존 데이터를 복사해야 하므로 리소스 소모가 있습니다.
• 링크드 리스트:
  • 장점:
    • 삽입/삭제 성능: 리스트 중간에서 삽입 또는 삭제가 O(1)로 빠릅니다.
    • 동적으로 크기가 조정되며, 메모리 낭비가 적습니다.
  • 단점:
    • 인덱스 접근: 순차적으로 노드를 따라가야 하므로 O(n) 시간이 걸립니다.
    • 각 노드마다 추가적인 포인터 저장이 필요하므로 메모리 오버헤드가 발생합니다.

3. 사용 용도

• 어레이 리스트: 빠른 인덱스 접근이 필요한 경우, 예를 들어, 데이터를 조회하는 데 주로 사용됩니다.
• 링크드 리스트: 삽입과 삭제가 빈번한 작업일 때 유리하며, 순차적으로 데이터를 처리하는 경우에 적합합니다.

4. 예시

• 어레이 리스트: Java의 ArrayList, C++의 std::vector
• 링크드 리스트: Java의 LinkedList, C++의 std::list

이렇게 각각의 자료 구조는 장단점이 있기 때문에, 상황에 맞게 적절히 선택하여 사용합니다.

배열 lis