[4-2] 제네릭 프로그래밍 ~ 컬렉션 프레임워크

💡 제네릭 프로그래밍

제네릭 프로그래밍이란 여러 자료형이 대체될 수 있도록 프로그래밍하는 것이다. 즉, 하나의 자료형에 국한하지 않고 여러 자료형이 쓰일 수 있도록 프로그래밍 하는 것이다. 대부분의 컬렉션 프레임워크가 제네릭 프로그래밍 방식으로 구현되어있다.

제네릭 클래스 정의하기

제네릭 프로그래밍 방식으로 만든 제네릭 클래스에 <T>는 매개변수 타입을 의미한다. 만들 때는 사용할 타입이 대체 될 곳에 문자 하나를 동일하게 쓰고 사용할 때는 그 문자 대신에 사용할 참조형 타입(클래스)을 쓴다.

자료형 매개변수 T

• type의 의미로 T를 많이 사용한다.
• <T>에서 <>는 다이아몬드 연산자라고 한다. 다이아몬드 연산자 내부에서 자료형은 생략이 가능하다.
• static 키워드는 T에 사용할 수 없다.

T extends 클래스

• T가 사용될 클래스를 제한하기 위해 사용한다.
• Material에서 상속받지 않은 Water와 같은 클래스는 프린터 재료로 사용할 수 없다.
• Material에 정의된 메서드를 공유할 수 있다.

💡 자료구조

자료를 '어떻게' 관리하느냐에 따라 알고리즘도 바뀌고 프로그래밍하는 방법도 달라질 수 있다. 자료를 어떤 구조로 관리할 것인지에 대한 것을 자료구조, 그 자료구조를 바탕으로 어떤 logic으로 구현하느냐에 대한 것을 알고리즘이라고 한다. 또 이런 것들에는 여러가지가 있어서 어떤 것을 어떨 때 쓰는지에 대해 이해해야한다.

기본적인 자료구조

• Array(배열)
• Linked List
• Stack
• Queue
• Tree
• Hashing

배열(Array)

배열은 일렬로 되어있는 선형적 자료구조의 대표이다. 같은 형의 데이터 타입을 메모리에 저장한다.

✔ 배열의 특징

• fixed - length로 시작한다. 즉, 생성할 때 길이를 정해놓고 시작한다는 것!

만약 아래와 같이 3개짜리의 배열을 선언했는데, 4개가 필요하다면 어떻게 해야할까? 배열은 자동으로 늘어나지 않는다. 따라서 더 큰 배열을 새로 만든 후, 기존 배열의 요소를 복사하고 요소를 더 추가한다.

• 장점 : 인덱스 연산을 할 수 있다. a[n]을 찾는데 빠르다.
• 단점 : 중간을 비워둘 수 없는 연속적인 자료구조이다. in/out, insert/del 에 들어가는 연산이 요소 n개에 종속되어 있다.(요소의 개수에 따라 연산의 횟수가 늘어나거나 줄어든다.) → O(n)

만약 아래와 같이 C 부분에 다른 요소를 넣고 싶다면 바로 넣는 것이 아니라, 한 칸씩 오른쪽으로 옮겨 자리를 만든 후 넣어야한다.

아래와 같이 B 요소를 삭제하고 싶을 경우에도 삭제하고 한 칸씩 왼쪽으로 옮겨 빈 자리가 없도록 만들어야 한다.

• 만약 배열이 꽉 찬 상태에서 맨 앞의 요소를 삭제하거나 추가하면 최대 n-1개가 이동한다.
• 따라서 배열의 요소가 계속 변한다면 배열을 쓰는 것은 좋은 방법이아니다.

Linked List

✔ 배열과 비교하면?

배열은 길이를 정해놓고 시작한다. 그러나 Linked List는 길이를 정해놓고 시작하는 것이 아니라 필요할 때마다 그 자료에 대한 node를 할당받는다. 그리고 메모리도 할당받고, 그 전의 node가 다음 node의 주소를 가리키게 된다. 따라서, 물리적인 위치와 논리적인 위치가 동일한 배열과 달리 Linked List는 물리적인 위치와 논리적인 위치가 다르다.

✔ 배열의 단점을 보완하는 Linked List

배열은 다른 요소를 삽입하거나 삭제할 때 오른쪽이나 왼쪽으로 한 칸씩 옮겨야했다. 그러나 Linked List는 아래 그림과 같이 node를 이용해 배열보다 빠르게 요소를 삽입하거나 삭제할 수 있다. 요소들이 다 옮길 필요 없이 node가 가리키는 곳을 바꿔주면 되기 때문이다.

✔ 배열 vs Linked List 정리

배열	Linked List
요소가 거의 변하지 않을 때 사용한다.	요소가 유동적일 때 사용한다.(insert/del이 많이 일어날 때)
논리적 위치 == 물리적 위치이기 때문에 인덱스 연산자에서 주소를 계산할 수 있다.	무조건 앞에서부터 찾아가야한다.
자바에 객체배열을 구현해놓은 ArrayList가 있다.	자바에서 LinkedList가 구현되어있다.

Stack

• JDK가 제공하는 Stack을 써도 되고 ArrayList를 활용하여 stack처럼 사용할 수 있다. 
• 중간에 데이터가 삽입되지 않는다.
• stack의 일반적인 의미는 '쌓다', '더미'라는 뜻으로 가장 나중에 들어간 것이 가장 먼저 나오는 구조를 갖고있다. 이것을 후입선출, 즉 LIFO(Last In First Out)이라고 한다.
• 요소를 집어 넣을 때 : push()
• 요소를 꺼내서 제거할 때 : pop()
• stack 맨 위에 있는 요소를 반환할 때 : peak()

stack에서 데이터가 삽입/제거되는 것은 아래 그림과 같이 위에서 삽입/제거된다. 맨 위 C의 위치를 Top이라고 하며, 항상 Top의 위치에서 push를 하고, Top의 위치에서 pop된다. 가장 최근의 정보를 참조할 때나 왔던 길을 되돌아갈 때, 홈페이지에서 뒤로 가기를 할 때의 구조를 stack이라고 한다.

Queue

• ArrayList, LinkedList, Vector를 이용해서 사용할 수 있다.
• 중간에 데이터가 삽입되지 않는다.
• 먼저 들어간 것이 먼저 나가는 구조 갖고있다. 이것을 선입선출, 즉 FIFO(First In First Out)이라고 한다.

Queue는 아래 그림과 같이 뒤(rear)에서 들어가서 꺼낼 때는 앞(front)에서 꺼내는 구조이다. 이때 끝에서 들어가는 것을 enqueue라고 하고, 앞에서 꺼내지는 것을 dequeue라고 한다. 선착순으로 상품을 받거나, 전화 상담을 기다리거나 할 때의 구조가 queue와 같다.

 

Stack과 Queue에 대해 쉽게 설명한 영상이다. 팬케이크와 버스라고 생각하니 좀 더 이해가 잘 된다.

Tree

• Tree는 계층이 있는 자료구조이다.
• 컬렉션 프레임워크가 아니더라도 Tree로 시작하는게 있는데, 그것이 Binary Search Tree로 되어있다. Binary Tree란 하나의 노드가 있고, 그 밑에 자식 노드가 최대 2개인 Tree를 말한다.
• 맨 위의 노드는 parent node라고 한다. 그 아래 왼쪽에 있는 노드를 left cild, 오른쪽에 있는 노드를 right child 라고 한다.

Binary Tree(BST)

• 나를 중심으로 왼쪽 서브트리 키 값은 나보다 작고, 오늘쪽 서브트리 키 값은 나보다 크다.
• 중복은 허용하지 않는다.
• JDK에서 Treeset, TreeMap이 Red-Black Tree로 구현이 되어있다.

아래 그림을 보면 이해가 갈 것이다. 이렇게 Tree를 사용하면 검색의 속도가 빨라진다. 물론 어느정도 균형잡힌 Tree라는 전제 하에 그렇다. 밸런스를 맞추기 위해 고안된 Tree에는 AVL, Red Black이 있다.

Hashing

• 산술 연산을 이용한 검색 방식으로, 빠른 검색을 위한 알고리즘이다.
• Hash Function에 Key값을 넣으면 객체가 들어가야하는 위치(index값)를 알려준다
• HashMap, HashSet
• 평균 시간 복잡도는 자료가 n개 일 때 O(n)이다.