List(리스트)와 Array(배열)

 

List(리스트)

- 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조입니다.

장점 : 데이터의 추가, 삭제 쉬움

단점 : 데이터 조회 느림

 

- 데이터들은 각각 포인터를 가지고, 이 포인터는 각각 데이터의 다음 데이터의 메모리 주소를 가리킵니다.

 

- 리스트는 포인터를 이용하므로 메모리상에서 연결된 위치에 있을 필요가 없습니다. 따라서 분산되어 배치됩니다.

 

- 데이터 추가 방법

A와 B 데이터 사이에 C라는 데이터를 추가할 때,
A의 포인터가 C의 메모리 주소를 가리키게 하고,
C의 포인터가 B의 메모리 주소를 가리키게 하면 끝이다.

 

- 데이터 삭제 방법

A와 B와 C가 연결되어 있을 때, B를 제거하고자 한다.

A의 포인터를 C의 메모리주소를 가리키면 해결된다.

 

따라서 List에서의 시간복잡도는 다음과 같다.

데이터 조회 : O(n)

데이터 추가, 삭제 : O(1)

 

---

 

Array(배열)

- 배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조입니다.

대부분의 특징이 List(리스트)와 반대인 특징이 있습니다.

 

장점 : 데이터의 조회 쉬움

단점 : 데이터 추가, 삭제 느림

 

- 데이터 추가 방법

ex) A, B 사이에 C를 넣어라.

1) 배열의 길이를 3으로 늘린다.

2) B를 array[2]로 옮긴다.

3) C를 array[1]에 추가한다.

 

- 데이터 삭제 방법

ex) A, B, C 사이에 B를 삭제해라.

1) B를 삭제한다.

2) C를 array[1]로 옮긴다.

3) 배열의 길이를 2로 줄인다.

 

 

따라서 Array에서의 시간복잡도는 다음과 같다.

데이터 조회 : O(1)

데이터 추가, 삭제 : O(n)