배열과 연결리스트

배열

배열은 메모리에 지정된 만큼의 연속된 저장 공간을 선점하여 사용하는 저장 방식입니다.

int[] grade = new grade {85, 65, 90};

그림 처럼, 변수는 배열의 시작 주소를 가리키고있고, int배열이기 때문에 4Byte씩 공간을 차지하고 있습니다.

순서대로 저장되어 있기 때문에, 특정 위치의 데이터를 찾는데 1번의 연산이면 됩니다.

이 처럼 원하는 데이터로 접근 하는데 1번의 연산으로 접근할 수 있기 때문에 O(1)의 시간 복잡도로 표시할 수 있습니다.

그런데 만약 배열 제일 처음에 데이터를 삽입하고 싶다면?

그리고 배열의 첫 자리에 데이터를 삽입합니다.

데이터를 삽입하기 위해서 배열의 길이(3)만큼 이동이 발생하였는데요.

이는 추가할 때 뿐만 아니라, 삭제할때도 동일합니다.

그래서 정리하면, 배열은 다음과 같은 복잡도를 가지게 됩니다.

그래서 배열은 다음과 같은 상황에 유리합니다. 특정 번지수의 데이터 참조가 많을 경우, 데이터 추가 • 삭제가 빈번하지 않은 경우에 유리합니다.

연결리스트는 아래 그림처럼 각 Node가 데이터와 다음 Node의 주소를 갖는 형태로 이루어져 있습니다.

만약, 다음 Node의 주소가 없다면 그곳이 연결리스트의 끝 지점 입니다.

만약 연결리스트에서 3번째에 있는 노드의 데이터를 찾고 싶다면 어떻게 해야할까요?

3번째 데이터를 찾기 위해서 3번의 연산이 필요합니다.

그런데 만약 배열 제일 처음에 데이터를 삽입하고 싶다면 어떻까요?

1번의 연산으로 가능하니 O(1)의 시간 복잡도로 표현 가능합니다.

하지만 여전히 n번째 데이터를 찾으려면 n번 연산이 필요해서, 가운데에 있는 데이터는 O(n)만큼 시간이 소요됩니다.

정리하면, 연결리스트는 다음과 같은 복잡도를 가지게 됩니다.