Collection Frameworks

자료구조(Data Structure)

자료(Data:값)을 메모리에서 구조적으로 처리하는 방법론으로 규모가 큰 데이터를 처리해야할 경우 자료구조가 필요함.

• 집에 책이 한두권있을때, 책장이 필요한가?
• 책이 수백권이 있을때는 어떻해야 하나?
• 책이 수만권 있을때는 또 무엇이 필요한가?

대표적 자료구조 : Tree구조(directory)

결국 정리정돈 진화의 산물 => 데이터의 자료구조.

data structure는 전공자들의 대학교 수업중 2,3학년이후에 배우는 고급과정이지만, 이런 대규모의 데이터를 다루어 본 적이 없어 공감이 안된다.
굳이 이걸 왜 써야하는가? 하는 의문이 이어짐. 상상력이 필요하다.
내가 만든 알고리즘으로 대규모의 데이터를 눈깜짝할 사이에 처리해서 많은 사람이 여유로운 저녁을 보내는 모습을...

자료구조란 대규모데이터를 보관, 검색, 삭제처리 할 때의 시간,공간적 효율성을 고려해 만든 알고리즘

‘자료구조와 알고리즘’ 논쟁을 보면 중요하지 않다는 측의 주장 중 가장 많은 논거가 “이미 대부분의 자료구조와 알고리즘은 라이브러리로 구현이 다 되어 있으니 잘 쓰기만 하면 된다.”라는 것이다.

하지만, 개인적으로 PS(Problem Solving) 트레이닝을 하면서 가장 많이 생각하는 것은 O(n)???시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)???에 대한 것이다.

아무리 이미 주요 자료구조와 알고리즘이 라이브러리로 존재한다고 하더라도 내가 작성한 for문이 사용자의 HTTP 요청에 1시간만에 응답할 수 있다거나 1GB의데이터를 처리하는데 100GB의 메모리가 필요하다면, 우리는 그 솔루션을 사용할 수 없다.

프로그래밍을 잘하는 5가지 방법??? 1. 자료구조와 알고리즘 공부하기

1. 단순 구조 : 정수, 실수, 문자(열) 등의 기본적인 데이터 타입을 말한다
2. 선형구조 : 각 자료들 사이의 관계가 일대일(1:1). 즉 선형으로 연결된 경우의 데이터 타입.
   • 배열과 같은 연속된 공간을 나열해서 사용하는 방법
   • 연결리스트(Linked List) 를 사용하는 방법 : 노드의 포인터 부분으로 서로 연결시킨 리스트
   • 대표적인 선형구조
     • 리스트(List)
     • 스택(Stack)
     • 큐(Queue)
     • 덱/디큐(Deque)
3. 비선형구조 : 선형구조가 아닌 계층 구조 혹은 망 구조를 가지는 경우를 말한다.
   • 트리(Tree)
   • 그래프(Graph)등이 대표적인 비선형 구조이다.
4. 파일구조 : 보조기억장치에 저장되는 파일에 대한 자료구조를 말한다. 파일 구조는 메모리가 아닌 디스크에 저장된다는 가정에 기반을 둔 것이므로 주로 대용량의 자료를 대상으로 한다. 파일의 구성 방식에 따라
   • 순차적 파일 구조
   • 상대적 파일 구조
   • 색인 파일 구조
   • 다중 키 파일 구조 등이 있다.

자료구조(Data Structure)란?
선형/비선형

Collections FrameWork

• 컬렉션Collection은 자바에서 제공하는 자료구조를 담당하는 프레임워크이다.
• 추가, 삭제, 정렬 등의 기능처리가 간단하게 해결 되어 자료구조적 알고리즘을 구현할 필요가 없다.
• Java.util 패키지에 포함되어 있으며, 인터페이스를 통해서 정형화된 방법으로 다양한 컬렉션 클래스를 이용할 수 있다.

• 배열의 단점
  1. 한번 크기를 지정하면, 변경할 수 없다. 필요에 따라 늘리거나 줄일 수 없음. 공간의 크기가 부족하면 에러가 발생하므로, 넉넉한 크기로 할당하게 됨. 메모리를 낭비하는 결과를 초래함.
  2. 배열에 기록된 데이터에 대한 중간위치의 추가, 삭제가 불편함.
     • 맨 앞이나 중간 위치에 추가할 경우, 그 위치의 데이터부터 마지막에 기록된 데이터까지를 하나씩 뒤로 밀어내고, 추가해야 함. 삭제의 경우도 마찬가지임.
     • 배열의 추가, 삭제에 대한 알고리즘이 복잡하다.
  3. 한 타입의 데이터만 저장한다.

• 컬렉션은 저장하는 크기의 제약이 없다. 자료를 구조적으로 처리하는 자료구조가 내장이 되어 제공이 됨

  • 추가, 삭제, 정렬 등의 기능처리가 간단하게 해결됨.
  • 자료구조적인 알고리즘 구현이 필요없다.
  • 여러 타입을 저장할 수 있다.
  • 객체만 저장함 : 필요할 경우 데이터의 저장을 위해 Wrapper 클래스를 사용함

• 컬렉션은 두 부류로 나눠짐

  1. Collection 인터페이스의 후손들
     - List 인터페이스 계열
     - Set 인터페이스 계열
  2. Map 인터페이스의 후손들

인터페이스

• java.util.List : 중복을 허용하고, 순서있음. 인덱스이용가능 java.util.ArrayList
• java.util.Set : 집합. 중복없고, 순서없음. java.util.HashSet
• java.util.Map : 키와 값의 쌍을 요소로 저장함. 키를 통해 값을 꺼낼 수 있음. java.util.HashMap

상속에 대한 계층구조

set

• Collection - Set - AbstractSet - HashSet : 중복제거
• Collection - Set - AbstractSet - HashSet - LinkedHashSet : 저장되는 순서유지
• Collection - Set - AbstractSet - TreeSet : 자동 오름차순정렬됨

list

• Collection - List - AbstractList - ArrayList : 배열처럼 사용(Thread Safe 기능없음)
• Collection - List - AbstractList - AbstractSequentialList - LinkedList : (Thread Safe 기능없음)
• Collection - List - AbstractList - Vector: 하위호환용 더이상 사용하지 말것.(Thread Safe 기능포함)

map

• Map - AbstractMap - HashMap : (Thread Safe 기능없음)
• Map - HashTable : 구버젼(Thread Safe 기능포함)