배열 및 배열 활용 자료구조

배열

2차원 배열 BASE0인 경우

 

ARRAY[2][6]의 위치 :

행, 열	0	1	2	3	4	5	6
0행
1
2							여기
3

 

 

문자열은 각 요소에 문자가 저장된 문자 배열이라고 볼 수 있다.\

 

N번째 요소의 참조가 빠른 것은 배열, 느린것은 연결리스트구조

*java의 ArrayList는 Array와 비슷하다. ArrayList는 내부적으로 Default 10개의 공간을 가진 배열로 구성되어있다. 

책에서는 배열과 연결리스트를 비교하고 있음.

 

자료구조	읽기(참조)	추가/삭제
ArrayList	빠르다	느리다
LinkedList	느리다	빠르다

 

시간복잡도	ArrayList	LinkedList
탐색	O(1)	O(1)
맨 뒤 데이터 추가/삭제	O(1) or O(n)	O(1)
맨 뒤 외의 위치에 데이터 추가/삭제	O(n)	O(1)
임의 위치 데이터 탐색	O(1)	O(n)
크기 구하기	O(n)	O(1) or O(n)

 

LinkedList의 탐색 성능 보완을 위해 양방향 리스트 Double LinkedList 방식도 사용한다.

 

링버퍼

 

링버퍼는 배열의 마지막 요소와 1번째 요소를 연결시킨 자료구조이다. 마지막 요소의 다음 요소는 배열의 1번째 요소가 된다.

링버퍼는 가장 오래된 데이터를 버리는 FIFO의 큐구조를 구현할 때 유용하다.

ex) 최근 발생한 수십건의 정보를 유지해야하는 휴대전화의 통화 이력 구현에 활용할 수 있다.

 

참고도서 : 그림으로 배우는 알고리즘 Basic - 스기우라 켄