1. 들어가기전에

• 자료구조의 목적은 데이터를 공간과 시간 양편에서 더 효율적으로 다룰 수 있도록 하는 것으로 볼 수 있다.

• 현실에서 물건을 보관하고 이를 찾아 이용하는 일은 분류만 적절히 한다면 큰 차이가 없을 가능성이 높지만, 컴퓨터에서는 다르다. 컴퓨터는 자료를 메모리에 할당하는 것과 이를 찾는 것에 있어서 사람만큼의 동작을 바로 할 수는 없다.

• 그래서 자료구조는 메모리 할당 방법, 데이터를 찾거나 활용하는 방법에 따라 여럿 존재한다. 개별 자료구조는 어떤 것은 메모리 할당이 최적화되어 있는 반면 검색에 시간이 걸리거나, 검색은 빠른 편이지만 할당이 불편하거나, 데이터를 꺼내는 것에 있어서 제한적이지만 속도가 빠른 등 각각 여러가지 특성을 가지고 있다.

• 특히, 특정 작업을 수행하는 알고리즘을 효율적으로 작성하기 위해서는 여러 자료구조 중 가장 적합한 것을 이용하는 것이 필요하다.

• 이하의 개념들은 자료구조를 다루기 위해 알아야할 몇몇 기초이다.

2. ADT

• ADT는 Abstract Data Type의 약자로, 자료구조의 구현방법은 다루지 않는 대신, 특정 자료구조의 일반적인 특성과 동작들을 설명한 것을 의미한다.

• 개별 프로그래밍 언어별로 기본적으로 지원하는 자료구조의 성격이 다르고, 구현방법이 상이할 수 있기 때문에, 일반론을 정해놓고 그에따라 개별 자료구조의 구현은 일반론에 맞추어서 하는 것이 대부분이다. 그렇기 때문에, 앞으로 논할 대부분의 자료구조와 알고리즘은 ADT로 할 것이다.

3. Big-O notation

• 알고리즘의 시간 복잡도를 나타내는 일종의 기준이다. 풀어서 설명하면, 특정 동작이 가장 오래 걸리는 경우의 시간을 어떤 함수로 표현할 수 있는지를 통해, 시간이 얼마나 걸리는지 알 수 있도록 한 것이다.

• 예를 들어, 4개의 데이터가 들어있는 배열, 혹은 리스트에 데이터 A가 들어있는지 그렇지 않은지 확인하기 위해선, 최소 1번, 최대 4번 자료구조 안의 데이터를 불러와서 비교하는 작업이 필요하다. 만약 데이터가 8개라면 최소 1번, 최대 8번 확인이 필요하다. 이 경우 일반적으로 n번 확인해야하는 것이다.

• 위의 예시의 경우, 시간복잡도는 O(n)으로 표현한다. 경우에 따라 O(log n), O(n * n) 등으로 표현한다.

• 다만, 일반적으로는 시간복잡도가 일정하지만, 특정한 경우에만 변동이 있는 경우, 전반적인 시간복잡도를 평균을 내어 표현하는 경우가 있다. 이런 경우를 Amortized cost로 부른다.

4. Generic

• 보통 클래스를 작성함에 있어 클래스의 인스턴스 타입 혹은 메서드의 리턴 타입 등은 클래스 내부에서 정해진대로 값이 들어오고 나가야 한다. 당연히 다른 타입의 데이터를 선언하거나 하면 컴파일 단계에서 오류가 난다.

• 하지만, 클래스나 인터페이스에 따라서는 여러 타입에 따라 동일한 동작을 해야하는 경우가 생긴다. 예를들어, 클래스가 인스턴스가 타입 제한이 없고, getter 메서드가 들어온 타입을 그대로 반환해주어야할 필요가 있다. 인스턴스의 타입을 Object로 할 수도 있지만, 이 경우 전에 다룬 Casting의 문제 때문에 메서드를 원하는대로 사용할 수 없다.

• 이런 경우, Generic 클래스를 작성함을 통해 문제를 해결할 수 있다. 제네릭 클래스는 인스턴스나 메서드의 타입을 외부에서 지정한대로 정한다.

public class Example<T>{
	private T value;
    ~~~
    public T getValue(){
    	~~~
    }
}

public static void main(){
	Example<String> x1 = new Example<String>("new");
    Example<Integer> x2 = new Example<Integer>(1);
}

• 위의 예시에서, Example로 선언하는 객체는 원하는 타입으로 정할 수 있다. 변수들은 모두 Example 객체이지만 x1은 String, x2는 Integer 타입으로 value가 정해지는 것이다.

5. Garbage Collection

• 대다수의 프로그래밍 언어가 어떤 변수나 객체를 선언하면, 메모리에 값이 할당되기는 한다. 하지만, 선언한 변수나 객체는 메모리에 할당된 데이터 자체가 아닌, 메모리에 값이 할당되어있는 주소를 가지고 있고, 해당 주소로 이동하면 그 주소에 해당하는 값이 존재한다.

• 이때, 일부의 프로그래밍 언어는 변수의 삭제나 변경 등으로 인해, 더 이상 특정 메모리를 가리키는 주소값이 존재하지 않게 되는 경우, 그 메모리를 비워서 공간 효율을 꾀하는데, 이를 garbage collection이라 한다.