[Java 자료구조] 여러가지 자료구조 (1)

자료구조

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 방법들
• 자료 종류에 따라 자료구조를 결정하고 알고리즘(로직)을 구현한다.
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다.

 

자료구조의 종류

선형 자료구조 (한 줄로 자료 관리)

: 전 요소와 후 요소가 1:1의 관계를 맺는 자료구조를 말한다.

 

배열 (Array)

• 가장 큰 특징은 중간이 비면 안된다는 것이다.
• 정해진 크기의 메모리를 먼저 할당 받아 사용한다.
• 물리적 위치와 논리적 위치가 같다.
• 어느 위치에 있는 요소를 꺼내오는 것이 빠르다는 장점이 있다.
• 시작 주소에서 떨어져 있는 거리를 계산하여 요소를 찾는다. O(1)
• 추가, 삭제 시 배열의 개수만큼 이동이 발생하기 때문에 수행 시간이 배열의 개수에 dependant하다 O(n)

 

연결 리스트 (Linked-list)

• 배열과 달리 필요할 때 메모리를 할당 받는다
• 각 노드에는 데이터 + 다음 element에 대한 링크(객체의 참조변수를 가리킴)가 존재한다.
• 물리적 위치와 논리적 위치가 다를 수 있다.
• 연결 리스트에서 뒤의 노드가 앞의 노드를 가리키는 링크를 추가하면 double linked-list
• 맨 뒤의 노드는 null을 가리키는데, 맨 앞의 노드를 가리키게 하면 circular linked-list
• 자료를 추가할 때 추가되는 노드의 링크만 변경해주고, 기존의 링크를 제거해주면 된다.
• 데이터 추가, 삭제 시 수행 속도가 배열보다 훨씬 빠르다. O(1)
• 반면 검색 연산은 처음 노드부터 원하는 노드까지 찾아가야 하므로 배열보다 느리다. O(n)

 

	배열	연결 리스트
검색 성능	O(1)	O(n)
추가, 삭제 성능	O(n)	O(1)

 

스택 (Stack)

• 자료가 추가되고 삭제되는 연산이 맨 끝(top)에서만 일어난다.
• LIFO (Last In First Out)
• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를때 사용할 수 있다.
• 함수의 메모리는 호출 순서에 따른 stack구조로 되어있다.

 

큐 (Queue)

• 자료가 추가되고 삭제되는 연산이 양쪽에서 일어난다.
• front에서 자료를 삭제(dequeue)하고 rear에서 자료를 추가(enqueue)한다.
• FIFO (First In First Out)
• 자료가 제거되면 앞으로 당겨지지 않음 → 메모리 낭비 발생
• 이를 방지하기 위해 circular queue로 구현하기도 함
• 콜센터의 문의 전화, 메세지 큐 등에 활용

 

스택, 큐는 array와 linked list로 구현할 수 있다.

 

	스택	큐
자료의 추가와 제거 위치	top	front, rear
추가 연산	push	enqueue
제거 연산	pop	dequeque
입출력 순서	LIFO	FIFO