[자료구조] Array VS LinkedList

Array

• 배열의 크기는 한 번 정하면 변경할 수 없다.

• 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다.

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 인덱스를 사용해 특정 원소에 접근이 가능하다.

  • 즉, Random Access(비순차적 접급)가 가능하다.

• 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다.

• 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용)

  • 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다.

• 배열의 원소를 삭제할 경우 

  • 삭제한 원소보다 큰 인덱스를 값을 갖는 원소들을 1씩 옮겨줘야 하기 때문에 시간 복잡도는 O(n)이다.

• 배열의 원소를 삽입할 경우

  • 배열의 크기가 충분할 때는 시간 복잡도는 O(1)이다.

  • 여유 공간이 없을 경우, 확장이 필요하기 때문에 (새로운 원소를 추가하고 인덱스를 1씩 옮겨줘야 함)시간 복잡도는 O(n)이다.

• 메모리는 Array가 선언될 때(컴파일 할 때) Stack 영역에 할당한다.

LinkedList

• LinkedList 구조

 

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.

• 즉, 메모리를 연속적으로 사용하지 않는다. 

• 순차적 접근방식이다. 즉, 특정 원소에 접근하기 위해서 처음부터 검색하면서 찾는다. 

• 동적으로 삽입, 삭제가 편하다.

• 원소를 삽입할 경우

  • 맨 앞 , 맨 뒤 삽입은 위치를 찾지 않아도 되서 시간 복잡도 O(1)이다.

  • 중간 삽입은 이전 노드와 다음 노드의 위치를 알고 있는 경우 시간 복잡도는 O(1)이다.

  • 하지만 탐색을 해야하는 경우 시간 복잡도 O(n)이다.

• 원소를 삭제할 경우

  • 삽입과 마찬가지로 맨 앞, 맨 뒤 삭제는 시간 복잡도 O(1)이다.

  • 중간 삭제는 시간 복잡도 O(n) 또는 O(1)이다. (삽입과 같음)

• 특정 위치에 있는 원소에 바로 접근이 불가능하다. (주소를 바로 알 수 없기 때문)

  • 원하는 원소를 찾기 위해서 최소 한 번은 리스트를 순회해야하기 때문에 시간 복잡도는 O(n)이다.

• 메모리는 새로운 노드가 추가될 때 (Runtime) Heap 영역에 할당한다.

ArrayList

• 크기가 가변적이다.

• 내부적으로 배열을 사용하기 때문에(인덱스를 이용해서) 접근하는 것이 빠르다.

• add(), remove()를 통해 추가/삭제가 가능하다.

  • 데이터 추가/삭제 시 메모리를 재할당하기 때문에 속도가 배열보다 느리다.

Array VS LinkedList

작업	Array	LinkedList
탐색	O(1)	O(n)
삽입	O(n)	O(1) : 맨 앞, 맨 뒤   O(n) : 탐색을 통한 중간 삽입
삭제	O(n)	O(1) : 맨 앞, 맨 뒤  O(n) : 탐색을 통한 중간 삭제

 

 

 

* 다음번에는 자바 컬렉션에 대해 정리해야겠다.

  - vector , linkedlist, arraylist