[0218] java 자료구조

자료구조란

자료구조의 종류

 

연결 리스트

스택,큐

 

체인 해시

트리

 

 

업캐스팅, 다운캐스팅

예) Parent ->Child

Child 클래스는 Parent 클래스를 상속받음

Child 클래스는 grade 라는 변수가 있음

Parent 클래스는 age라는 변수가 있음

 

기본: Child c= new Child();

 

• 부모 타입으로 자식 객체를 참조할 수 있음(업캐스팅)

예) Parent p= new Child();

이때 Child 클래스의 grade 변수 공간 없음

 

• 자식 타입으로 부모 객체를 참조할 수 없다

예) Child c= new Parent(); (x)

컴파일 에러 생김

 

 

시간 복잡도

알고리즘의 효율성을 비교할때 사용함

 

규칙

• 입력값은 항상 0보다 크다
• 함수는 입력값보다 더 많은 일을 한다
• 모든 상수는 제거(무시)한다
• 낮은 차수는 제거(무시) 한다
• log의 밑은 무시한다
• 등호를 사용해 표시한다 ("2n = O(n)" == "2n∈ O(n)")

 

*log 는 대부분 나누기 혹은 곱하기 일때 자주 사용된다

*log 는 계산하기 쉬운 밑 (대부분 10 즉, ln을 사용)으로 사용하면 된다

 

 

빅 오 표기법

기준 대상을 그래프에 그리고 비교 대상을 그려 비교하는 방법

 

O : 비교 대상과 같거나 빠르다

o : 비교 대상 빠르지만 같지 않다

 

Θ : 비교 대상과 같다

 

Ω : 비교 대상과 같거나 느리다

ω : 비교 대상 느리지만 같지 않다

 

 

 

 

*java 에서 할당되는 메모리값

int = 4byte

long 8 byte

student s= new student(); 일때

s 4byte

heap에 student 클래스와 관련된 모든 내용이 저장되어 있음

s의 4byte는 heap에 저장된 student의 내용의 주소를 담음

 

 

객체를 비교하는 방법

• .equal()

 object 일때는 메모리의 주소 비교

string 일때는 주소 비교(x) string의 값 비교

=> 이때 equals 는 string class 에서 object의 class를 오버라이드한 것

• .compareTo()

정수를 반환함

a.compareTo(b);

일때

if(a>b) => return 0보다 큰 값

if(a==b) => return 0

if(a<b) => return 0보다 작은 값

 

 

제네릭 프로그래밍

다양한 자료형의 객체에 대해 작성한 코드를 재사용한다는 객체 지향 기법

 

매개변수화 타입으로 구현

// 클래스
public class 클래스명
public class 클래스명<E>

// 함수
public void 함수명(String S)
public void 함수명(E obj)

//생성자
public String 클래스명()
public E 클래스명()

//배열 컴파일 정상
E[] storage = (E[]) new Object[size];

//배열 컴파일 오류
E[] storage = new E[size];

 

 

---

이 글은

자바로 구현하고 배우는 자료구조

강의를 참고하였습니다