자료구조의 분류
대표적으로 선형 자료구조와 비선형 자료구조 나눌 수 있는데 이러한 분류를 보통 형태에 따른 자료구조라고 보며, 각 자료구조에 알맞게 구체화된 것들을 구현된 자료구조라고 한다.
선형 자료구조(Linear Data Structure)
: 리스트(List), 큐(Queue), 덱(Deque)
비선형 자료구조(NonLinear Data Structure)
: 그래프(Graph), 트리(Tree)
집합 자료구조
: 집합(Set)
Java Collection Framework
일정 타입의 데이터이 모여 쉽게 가공할 수 있도록 지원하는 자료구조의 뼈대(기본 구조)라는 의미
자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉜다. (List, Queue, Set)
앞서 설명한 형태에 따른 자료구조로 볼 수 있다. 그리고 각 분야별로 구현된 것들이 있다.
점선은 구현 관계이고, 실선은 확장 관계이다. (인터페이스끼리는 다중 상속이 가능하다) 또한 Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키에 있다.
List (리스트)
배열과 List 인터페이스에서 지원하는 클래스들과의 공통점과 차이점
[공통점]
1. 동일한 특성의 데이터들을 묶는다.
2. 반복문내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다.
[차이점 - 배열]
1. 처음 선언한 배열의 크기(길이)는 변경할 수 없다. 이를 정적 할당(static allocation)이라고 한다.
2. 메모리에 연속적으로 나열되어 할당된다.
3. index에 위치한 하나의 데이터(element) 삭제하더라도 해당 index에는 빈 공간으로 계속 남는다.
[차이점 - 리스트]
1. 리스트의 길이가 가변적이다. 이를 동적 할당(dynamic allocation)이라고 한다.
2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고 각 데이터들은 주소(reference)로 연결되어 있다. C에서의 포인터라고 생각하면 된다.)
3. 데이터(element) 사이에 빈 공간을 허용하지 않는다.
[배열의 장단점]
<장점>
1. 데이터 크기가 정해져있을 경우 메모리 관리가 편하다.
2. 메모리에 연속적으로 나열되어 할당되기 때문에 index를 통한 색인(접근)속도가 빠르다.
<단점>
1. 배열의 크기를 변경할 수 없기 때문에 초기에 너무 큰 크기로 설정할 경우 메모리 낭비가 심하다.
2. 데이터 삽입, 삭제 시 뒤의 데이터들을 모두 밀어내거나 당겨주어야 하기 때문에 속도가 느리다.
[리스트의 장단점]
<장점>
1. 데이터의 개수에 따라 메모리를 동적으로 할당해주기 때문에 메모리 관리가 편하다.
2. 포인터(주소)로 각 데이터들이 연결되어 있어서 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입/삭제가 용이하다.(ArrayList는 예외)
<단점>
1. 객체로 데이터를 다루기 때문에 적은양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다.
간단히 예로들어 primitive type인 Int는 4Byte를 차지한다. 반면에 Wraaper class인 Integer는 32bit JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 '최소 16Byte를 차지한다. 거기에다가 이러한 객체데이터들을 다시 주소로 연결하기 때문에 16 + α 가 된다.
2. 기본적으로 주소를 기반으로 구성되어있고 메모리에 순차적으로 할당하는 것이 아니기 때문에(물리적 주소가 순차적이지 않다) 색인(검색)능력은 떨어진다.
List Interface에 선언된 대표적인 메소드
