CS/자료구조 & 알고리즘

[자료구조] 리스트 List

초오오이 2025. 3. 23. 12:11

 


 

1. 리스트

  • 리스트는 배열과 마찬가지로 데이터를 순차적으로 저장하는 자료구조이다.
  • 배열과는 달리, 리스트는 크기가 고정되어 있지 않고 동적으로 변할 수 있으며, 요소의 삽입과 삭제가 일반적으로 더 유연하다는 특징을 지닌다.

 

2. 특징

장점

  • 동적 크기: 배열 기반 리스트의 경우, 필요에 따라 자동으로 크기가 조절되어 데이터를 유연하게 추가하거나 삭제할 수 있다. 연결 리스트는 태생적으로 크기에 제한이 없다.
  • 쉬운 삽입 및 삭제
    • 연결 리스트: 특정 위치(노드)에서의 데이터 삽입 및 삭제가 (해당 노드 또는 이전 노드에 대한 참조가 있다면) O(1)로 매우 효율적이다.
    • 배열 기반 리스트: 리스트의 끝에서의 삽입(append)과 삭제(pop)는 평균적으로 O(1)의 시간 복잡도를 가진다. (단, 배열 용량 확장이 필요한 경우는 예외) 그러나 리스트의 중간에 데이터를 삽입하거나 삭제하는 경우, 해당 위치 이후의 요소들을 이동시켜야 하므로 O(N)의 시간이 소요될 수 있다.

단점

  • 순차 접근 (주로 연결 리스트): 연결 리스트의 경우, 특정 인덱스의 요소에 접근하려면 리스트의 처음부터 순차적으로 탐색해야 한다. 따라서 배열처럼 인덱스를 통한 직접적인 접근(O(1))이 불가능하며, 접근 속도가 상대적으로 느릴 수 있다 (O(N)). 배열 기반 리스트는 인덱스를 통한 접근이 O(1)로 빠르다.
  • 메모리 오버헤드 (주로 연결 리스트): 연결 리스트는 각 요소(노드)가 실제 데이터와 다음 요소(또는 이전 요소)를 가리키는 포인터(참조)를 함께 저장해야 하므로, 데이터 외의 추가적인 메모리 공간이 필요하다.
  • 캐시 비효율성 (주로 연결 리스트): 연결 리스트의 노드들은 메모리 상에 흩어져 있을 가능성이 높아, CPU 캐시의 지역성(locality)을 활용하기 어려워 배열 기반 구조보다 성능이 떨어질 수 있다.