프로그래밍/- java
자료구조
즐겁게 하하하
2022. 1. 30. 17:27
728x90
배열
List스택큐( fifo )트리
저장순서x, 중복x그래프
그래프를 구현하는 방법 : 인접 행렬, 인접 리스트
그래프를 탐색하는 방법 : BFS(bread first search), DFS(depth first search)해싱
자료를 검색하기 위한 자료 구조
key는 유일하고 이에 대한 value를 쌍으로 저장 index = h(key)
저장순서X , 키는 중복x , 값은 중복0★ 제네릭 프로그래밍
- 클래스에서 사용하는 변수의 자료형이 여러개 일수 있고, 그 기능(메서드)은 동일한 경우
추후 해당 클래스를 사용할 때 지정 할 수 있도록 선언
- 자료형 매개변수 T : static 변수는 사용불가 , 이 클래스를 사용하는 시점에 자료형 지정
- GenericPrinter : 제네릭 자료형
- E : element, K: key, V : value 등 여러 알파벳을 의미에 따라 사용 가능
★ <T extends 클래스> 사용하기
- T 자료형의 범위를 제한 할 수 있음
- 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음
- 상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 제공하는 메서드만 사용가능
class FruitBox< T extends Fruit >{ } :: Fruit 자손만 타입으로 지정 가능
class FruitBox< T extends InterFace1 & InterFace2 >{ } :: 인터페이스도 extends
★ 와일드 카드 <?> :: 하나의 참조 변수로 대입된 타입이 다른 객체를 참조 가능
ArrayList<TV> tvList = new ArrayList<TV>() :: 기존
ArrayList<TV> tvList = new ArrayList<LgTv>() :: 타입 불일치 Error
ArrayList<? extends TV> list = new ArrayList<LgTv>() :: 와일드카드
<? extends T> :: T의 자손들만 가능
<? super T> :: T의 조상들만 가능
<?> :: 제한없음
static Juice makeJuice( FruitBox<? extends Fruit> box ) { } :: 메서드 매개변수 ok
★ 지네릭 메서드 ( 지네릭 타입이 선언된 메서드 )
- 타입 변수는 메서드 내에서만 유효
static <T extends Fruit> Juice makeJuice( FruitBox<T> box ){ }
public static < T , V > double makeRectangle( Point<T,V> p1 , Point<T,V> p2 ) {}
FruitBox<Fruit> fruitBox = new FruitBox<Fruit>();
System.out.println( Juicer.<Fruit>makeJuice(fruitBox) );
★ 지네릭 형변환
Box<Object> objBox = new Box<Object>();
Box<String> strBox = new Box<String>();
- Box<Object> objBox = (Box<Object>)strBox; :: 불가능 , Box<Object> -> Box<String>
- Box<? extends Object> wBox = new Box<String>(); :: 형변환 가능
★ 컴파일러는 지네릭 타입을 제거하고 필요한 곳에 형변환을 넣는다
컬렉션 프레임웍( List , Set, Map )
- java.util 패키지에 구현되어 있음
1. List
저장순서0 , 중복0
데이터 저장에 배열을 이용한다.
- linked list ( 기차 ) :: 연결기반 0 - 1 - 2 - 4 - 5
└ 3 ┘
장점 : 불연속적으로 존재하는 데이터를 연결
단점: 접근성이 나쁘다.( 0번부터 순서대로 찾아야 함 ) 0 > 1 > 2 > 3 > 4 > 5
- double linked list
단점: 접근성이 나쁘다.( 징검다리 처럼 앞뒤로 이동 )
0 <> 1 <> 2 <> 3 <> 4 <> 5
2. Set
저장순서x, 중복x
- HashSet
- 같은 객체가 없으면 저장, 있으면 pass
- equals, hashCode을 구현하지 않으면 중복 비교 안됨
이클립스 : 소스 - hashCode() 및 equals() 생성
- 정렬 해야 하는경우 LinkedList 이용해야함.
- LinkedHashSet - 순서 유지됨
- TreeSet
- 범위 검색과 정렬에 유리 , 추가삭제에 시간 大
- 이진트리는 모든 노드가 최대 2개의 하위 노드 갖음
- 부모보다 작은건 왼쪽 , 큰건 오른쪽에 저장
- Comparable 또는 Comparator를 호출해서 비교
Comparator의 활용 : 이미 Comparable이 구현된 경우
Comparator로 비교하는 방식을 다시 구현할 수 있음
- 결과가 자동으로 정렬되어 나옴.
- 전위 중위 후위 순회법이 있으며, 중위순회하면 오름차순 정렬된다.
4. Map
키와 값의 쌍으로 이루어진 집합
저장순서X , 키는 중복x , 값은 중복0
- key는 equals, hashCode를 이용하여 유일성을 비교 해야함.
- HashMap( 동기화 안되어있음 )
- 해싱기법으로 데이터 저장, 검색이 빠르다.
- Hashtable( 동기화 되어있음 )
- TreeMap
- LinkedHashMap - 순서 유지됨
Comparable , Comparator : 객체 정렬에 필요한 메서드를 정의한 interface
왼쪽大 : 양수 / 같다 : 0 / 오른大 : 음수
Comparable : 기본 정렬기준 구현
Comparator : 기본 정렬 기준 외 다른 기준으로 정렬하고자 할 때
sort() : 두 대상에 대하여 1) 비교 2) 자리바꿈
Comparable : int compareTo( Object o ); :: 주어진 객체o를 자신과 비교
Comparator : int compare( Object o1 , Object o2 ); :: 두 객체를 비교 
Collection 요소를 순회하는 Iterator
1회용, 재사용시 다시 선언
컬렉션에 저장된 데이터를 접근하는데 사용되는 interface
List인터페이스의 경우는 Iterator를 사용 하지 않고 get(i) 메서드를 활용
Set 인터페이스의 경우 get(i) 메서드가 제공되지 않으므로 Iterator를 활용
Map 에는 iterator() 가 없다. keySet() , entrySet() , Values() 호출
boolean hasNext : 읽어올 요소가 남아있는지 확인 있으면 true; 없으면 false;
Object next() : 다음 요소를 읽어온다. next() 를 호출하기 전에 hasNext()를 호출해서
읽어올 요소가 있는지 확인하는게 안전하다.
List list = new ArrayList();
Iterator it = list.iterator(); :: 객체를 반환 ( 1회용, 재사용시 다시 선언 )
while( it.hasNext() ){ //boolean
System.out.println( it.next() );
}
728x90