[자료구조] List - 순차리스트

순차리스트 이미지

---

List - 순차리스트 (배열,  ArrayList ...)

순차 리스트(Sequentail List)는 데이트를 메모리 상에 연속적으로 젖아하는 방식의 리스트 구조로써 대표적으로 배열이 있음.
배열 기반의 자료구조에서 많이 사용됨.

특징

1. 연속된 메모리 공간 사용
순차 리스트는 배열처럼 데이터를 메모리 상의 연속된 공간에 저장함. 이로 인해 인덱스를 통한 접근 속도가 빠름.
메모리 상의 특정 위치에서 바로 데이터를 찾아올 수 있기 때문에 조회 시간 복잡도는 **O(1)** 임

2. 빠른 조회
순차 리스트의 가장 큰 장점 중 하나는 인덱스를 사용한 데이터 조회가 매우 빠르다는 점. 이는 연속된 메모리 구조 덕분으로, 인덱스르르 통해 직접 원하는 위치에 접근할 수 있기 때문.

3. 고정된 크기
순차 리스트는 일반적으로 고정된 크기의 배열을 사용함. 즉, 처음 리스트를 생성할 때 정해진 크기 이상으로 요소를 저장할 수 없으며, 크기를 넘기면 더 큰 배열을 할당하ㅏ고 데이터를 복사해야 함. 동적 배열을 사용하는 경우에는 자동으로 크기가 확장될 수 있지만, 일반적인 순차 리스트는 크기가 고정됨.

4. 삽입 및 삭제의 기능
순차 리스트에서 중간에 데이터를 삽입하거나 삭제하는 작업은 비효율적임. 삽입이나 삭제 시, 그 이후의 모든 요소들을 이동시켜야 하기 때문에 시간 복잡도는 **O(n)**임. 맨 끝에 요소를 삽입하거나 삭제하는 경우는 빠르게 처리되며 시간 복잡도가 **O(1)**임.

5. 메모리 활용
순차 리스트는 미리 할당된 연속적인 메모리 공간을 사용하기 때문에 메모리 관리가 단순하지만, 배열의 크기가 고정되어 있다면 할당된 공간이 낭비될수 있음. 반대로, 배열이 가득 찰 경우 더 이상 데이터를 추가할 수 없는 한계가 있음.

6. 데이터의 접근 방식
순차 리스트는 데이터에 순차적으로 접근하는 방식이 기본이지만, 인덱스를 사용해 임의 접근(Random Access)이 가능하다는 점이 일반적인 연결 리스트와의 차이점

7. 정렬된 데이터 관리
순차 리스트는 기본적으로 정렬되지 않은 상태로 저장됨. 만약, 정렬된 데이터를 유지하려고 한다면, 삽입시 적절한 위치에 넣기 위한 추가 연산이 필요할 수 있으며, 이는 **O(n)**의 시간 복잡도를 가짐

8. 순차 탐색
순차 리스트는 데이터를 순차적으로 저장하고 있기 때문에, 정렬되지 않은 리스트에서 특정 값을 찾기 위해서는 순차 탐색이 필요 할 수 있음. 이 경우 시간 복잡도는 **O(n)** 임.

9. 동기화 문제
순차 리스트는 배열과 유사하기 때문에 기본적으로 스레드 안전(thread-safe)하지 않음. 멀티스레드 환경에서 동기화가 필요하다면 별도의 조치가 필요.

핵심
순차리스트는 연속된 메모리 공간을 사용해 빠른 조회가 가능하지만, 중간에 데이터를 삽입하거나 삭제할 때는 성능이 저할될 수 있음. 배열 기반으로 데이터를 저장하는 방식이기 때문에 메모리 공간을 효율적으로 사용하기 어려울 수 있으며, 크기가 고정되는 단점이 있음.