Linked List - 순차 컨테이너

링크드 리스트는 각 요소가 데이터와 다음 요소에 대한 포인터를 포함하는 노드로 구성됩니다. 링크드 리스트는 메모리의 비연속적인 위치에 요소를 저장하며, 요소를 동적으로 추가하거나 제거할 수 있습니다.

 

링크드 리스트의 주요 특징과 기능은 다음과 같습니다:

1. 동적 크기 조절
   • 링크드 리스트는 요소를 동적으로 추가하거나 제거할 수 있으며, 크기를 자동으로 조절합니다. 이로써 사용자는 리스트의 크기를 사전에 정확히 알 필요가 없습니다.
2. 요소 액세스
   • 링크드 리스트는 각 노드가 다음 노드를 가리키는 포인터를 포함하고 있어, 순차적으로 접근해야 합니다. 특정 요소에 접근하려면 첫 번째 노드부터 시작하여 순차적으로 이동해야 합니다.
3. 메모리 관리
   • 링크드 리스트는 메모리를 동적으로 관리하며, 각 노드는 필요에 따라 할당 및 해제됩니다. 이는 메모리 사용의 효율성을 높이고 메모리 누수를 방지합니다.
4. 비연속적인 메모리 구조
   • 링크드 리스트의 요소는 메모리에서 연속된 위치에 저장되지 않으며, 각 요소는 포인터를 통해 다음 요소와 연결됩니다. 이는 삽입 및 삭제가 용이하게 합니다.
5. 다양한 기능
   • 링크드 리스트는 요소의 삽입, 삭제, 탐색 등의 작업을 효율적으로 수행할 수 있습니다. 특히, 중간에 요소를 삽입하거나 삭제하는 작업이 빠릅니다.

링크드 리스트는 데이터 삽입, 삭제에 있어서는 좋은 성능을 보이지만, 데이터 탐색에 있어서는 선형 탐색이 필요하여 퍼포먼스가 떨어질 수 있습니다. 이는 요소에 접근하는 데 O(n)의 시간 복잡도가 소요되기 때문입니다.