62일차 (Array List와 Linked List)

어레이 리스트(Array List)와 링크드 리스트(Linked List)는 데이터를 저장하는 두 가지 기본적인 자료 구조이다. 

 

어레이 리스트(Array List)

• 연속적인 메모리 할당: 어레이 리스트는 연속된 메모리 위치에 데이터를 저장한다. 이것은 인덱스를 통한 빠른 접근을 가능하게 해 준다.
• 인덱스를 통한 빠른 접근: 특정 인덱스의 요소에 대한 접근이 빠르며, 일반적으로 O(1)의 시간 복잡도를 가진다.
• 크기 조정의 어려움: 초기에 할당된 공간을 넘어서는 경우, 새로운 더 큰 어레이를 생성하고 기존의 데이터를 복사해야 한다. 이는 비용이 많이 드는 작업일 수 있다.
• 삽입과 삭제의 비효율성: 중간에 요소를 삽입하거나 삭제할 경우, 다른 모든 요소들을 이동해야 하므로 O(n)의 시간이 소요된다.

 

링크드 리스트(Linked List)

• 비연속적인 메모리 할당: 링크드 리스트의 각 요소는 다음 요소의 주소를 포함하고 있어 연속적인 메모리 할당이 필요 없다.
• 동적 크기 조정: 새로운 요소를 추가하거나 제거하는 것이 간단하다. 메모리가 허용하는 한 어떤 크기로도 확장 가능하다.
• 순차 접근: 특정 인덱스의 요소에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하므로 접근 시간이 O(n)이 될 수 있다.
• 삽입과 삭제의 효율성: 어떤 요소의 삽입이나 삭제는 O(1)의 시간에 가능하다. 그러나 삭제를 위해서는 삭제할 요소에 도달해야 하므로 탐색 시간이 추가된다.

 

 

Array List는 빠른 인덱스 접근이 필요할 때 유리하고, Linked List는 데이터의 동적인 추가 및 삭제가 빈번히 일어날 때 유리하다. 따라서 사용 사례에 따라 적합한 자료 구조를 선택하는 것이 중요하다.