[알고리즘] 배열과 리스트

[ Do it! 알고리즘 코딩테스트 with JAVA ] 강의를 듣고 정리한 글 입니다.

 

 

____________________________________________________________________________

1.배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. - 연속된 메모리 공간에 존재하여 관리가 수월하다.

 

인덱스를 통하여 값에 바로 접근할 수 있다. - 자료구조의 크기가 클 수록 유리

 

새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. - 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하기 때문

 

구조가 간단하여 코딩테스트에서 많이 사용한다.

 

 

시간 복잡도

 

삽입 / 삭제

- 배열의 맨 앞 삽입 / 삭제 : O(n)

- 배열의 맨 뒤에 삽입 / 삭제 : O(1)

- 배열의 중간에 삽입 / 삭제 : O(n)

 

탐색

- O(1)

배열의 원소를 인덱스로 접근 가능

 

____________________________________________________________________________

2.리스트

 

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.

 

인덱스가 없으므로 데이터를 삽입하거나 삭제하는 연산속도가 빠르다.

 

삽입할 때 크기를 별도로 지정하지 않아도 된다. 리스트의 크기는 정해져 있지 않다. - 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.

 

포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다. 

 

인덱스를 통한 접근이 불가능하기 때문에 포인터를 통해 순차적으로 탐색하여 탐색에는 불리하다.

 

크기가 가변적이기 때문에 메모리 낭비는 배열에 비해 적다.

 

그러나 별도의 주소를 저장하는 공간을 필요로 하기 때문에 추가적인 메모리가 필요하다는 단점도 존재한다.

 

시간 복잡도

 

삽입 / 삭제

- 리스트의 맨 앞 : O(1)

- 리스트의 중간 : O(n)

 

탐색

O(n)

리스트 처음부터 링크를 타고 순차적으로 탐색하기 때문