[Data Structure] List

List

데이터를 순서대로(선형 구조) 저장하는 자료구조

• 리스트는 배열과 다르게 동적으로 크기 변경이 가능합니다.
• 리스트는 구현방법에 따라 구분됩니다.
  • 배열을 기반으로 구현된 순차 리스트
  • 연결 리스트

배열 기반 리스트(Array List)

배열로 구현한 리스트는 동적 배열을 기반으로 하는 자료구조입니다. 연속된 메모리 블록에 데이터를 저장하며, 데이터가 추가될 때마다 배열 크기가 동적으로 확장됩니다. 대표적인 예로 Python의 list나 Java의 ArrayList가 있습니다.

장점

• 임의 접근 (Random Access): 배열은 연속된 메모리 공간에 데이터를 저장하기 때문에, 특정 인덱스에 바로 접근할 수 있습니다.
• 메모리 효율성: 배열은 메모리 공간이 연속적으로 할당되어 있기 때문에, 데이터가 많을 때 메모리 할당이 효율적입니다.
• 배열의 크기가 유동적: 배열의 크기는 동적으로 확장될 수 있습니다. 배열이 꽉 차면 새로운 배열을 만들고, 기존 데이터를 복사하여 확장합니다.

단점

• 삽입/삭제 시 데이터 이동: 배열에서 중간에 데이터를 삽입하거나 삭제하면, 삽입/삭제 위치 이후의 데이터를 이동해야 합니다.
• 배열 크기의 재조정 비용: 배열이 꽉 찼을 때 배열의 크기를 확장할 때마다 새로운 배열을 할당하고 기존 데이터를 복사해야 하므로 시간이 오래 걸릴 수 있습니다.
• 메모리의 낭비 가능성: 미리 할당한 배열의 크기가 너무 커서 남는 공간이 많으면, 메모리가 낭비될 수 있습니다.

시간 복잡도

• 탐색: O(1)
  • 인덱스를 통한 접근
• 수정: O(1)
  • 인덱스를 모른다면 처음부터 탐색을 해야하니까 O(n)
• 삽입, 삭제: O(n)
  • 삽입, 삭제 후에도 배열이 연속되게 만들어야 하기 때문
  • 인덱스의 맨 끝에 삽입, 삭제를 한다면 상수 시간
• 배열의 크기 확장: O(n)
  • 복사 및 재할당 되기 때문

연결 리스트(Linked List)

연결 리스트는 포인터를 이용하여 각 요소가 서로 연결된 자료구조입니다. 각 요소는 데이터와 다음 요소를 가리키는 포인터(참조)를 포함합니다. 연결 리스트는 연속된 메모리 공간에 저장되지 않고, 각 노드가 독립적인 메모리 위치에 배치됩니다.

종류

• 단일 연결 리스트 (Singly Linked List)
• 이중 연결 리스트 (Doubly Linked List)
  • prev, next로 양방향 탐색 가능
• 원형 연결 리스트 (Circular Linked List)
  • 마지막 노드가 nullptr을 가리키는게 아니라 첫번째 노드를 가리키는 형태

장점

• 동적 크기: 연결 리스트는 크기가 동적으로 변합니다. 삽입이나 삭제 시 크기를 미리 할당할 필요가 없으며, 데이터의 크기에 맞게 메모리가 할당됩니다.
• 삽입/삭제 효율성: 배열과 달리 중간에 데이터를 삽입하거나 삭제할 때, 삽입 위치만 알고 있으면 삽입이 효율적입니다.
• 메모리 낭비가 적음: 연결 리스트는 데이터 크기에 맞게 메모리가 할당되므로, 미리 크기를 정할 필요가 없어 메모리 낭비가 적습니다.

단점

• 임의 접근 불가: 연결 리스트는 배열처럼 연속된 메모리 공간에 데이터를 저장하지 않기 때문에, 임의의 인덱스로 바로 접근할 수 없습니다.
• 추가적인 메모리 사용: 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터를 저장해야 하므로, 추가적인 메모리 공간이 필요합니다.

시간 복잡도

• 탐색: O(n)
• 삽입, 삭제: O(n)
  • 삽입, 삭제 자체는 상수 시간
  • 인덱스의 맨 끝에 삽입, 삭제를 한다면 상수 시간
  • 단일 연결 리스트의 경우 tail 포인터의 탐색이 필요할 수 있으므로 만찬가지로 O(n)

Reference
https://velog.io/@yyj8771/리스트-List-자료구조
https://enjoyplaying.tistory.com/30