Java & SpringBoot로 시작하는 웹 프로그래밍 : 자바 인강 5주차

자바의 자료구조(Data Structure)

프로그램에서 사용할 많은 데이터를 메모리상에서 관리하는 여러가지 구현방법이 있다.

알고리즘의 기반된 효율적이고  자료구조가 좋다.

자료구조의 효율성에 따라 프로그램에 대한 수행속도에 밀접하게 나타난다.

좋은 자료구조는 효율성이좋아서 빨리 수행이되며 안좋고 더러운 자료구조는 수행능력이 떨어지며

여러 자료구조중에서 구현하려는 프로그램에 맞게 최적한 자료구조를 활용해야되서 자료구조의 이해가필요하고 중요하다.

 

자료구조

배열 열결리스트 스택 큐등 있으며 선형구조이다.

배열 (Array)

100개면 1000개 메모리를 정해두고 할당받지만

배열 선형으로 자료를 관리 정해진 메모리크기에 메모리를 먼저 할당 받아 사용하고,순차적으로 데이터를 빨리 받거나 호출할수있다.

왜냐하면 자료의 물리적인 위치와 논리적인 위치가 같기때문이다.

연결리스트

선형으로 자료를 관리, 자료가 추가될때마다 메모리를 할당 받고 자료는 링크로 연결되서 자료의 물리적 위치나 논리적인 위치가 다르다. 

LinkedList는 메모리를 필요할때마다 메모리를 추가해 가면서 사용하고 더블 링크드리스트 서큐러형 링크드리스트등이있다.            

스택(Stack) 과 큐(Queue) 

스택

가장 나중에 입력된 자료가  가장 먼저 출력 되는 구조이며 즉 후입선출 되는구조입니다.

큐

가장 먼저 입력된 자료가 가장 먼저 출력이되는 구조 선입선출 되는구조입니다.

비선형 구조

트리

tree 부모노드와 자식 노드사이에 연결로 이루어진 구조입니다.

힙(Heap) priority Queue를 구현하는

맥스힙Max heap) 부모 노드는 자식 노드보다 항상 크거나 같을때 맥스힙이라고 한다.

미니힙min heap)부모노드는 자식노드보다 항상 자거나 같을때 미니힙 이라고 한다.

이진 검색 트리

검색을 하기 위해서 나타내는 검색 트리로 부모노드가 같으면 안되고 부모노드보다 작으면 왼쪽  자식노드로 가고 부모노드가 크면

오른쪽으로간다

inorder traversal 탐색을 하게되면 자료가 정렬되어 출력된다.

 

그래프 Graph) 정점과 간선으로 이루어진 유한 집합체이다.

정점vertex) 여러 특성을 가진 객체 노드 정점이라고한다

간선 객체와객체 사이에 선 을 간선이라고한다.

 

해싱(Hashing)는  자료를 검색하기위한 자료구조이다

키에대한 자료를 검색하기위한 사전 (dictionary) 개념의 대한 자료구조이다.

Key는 유일하며 Key대한자료를 value를 둘다 저장된다.

index= h(Key)는 해시 함수가 Key대한 인덱스로 반환되며 해당 인덱스 위치에 대한 자료를 저장하거난 검색할수있다.

해시함수에 의한 인덱스 연산이 산술적으로 가능이며 저장되는 메모리 구조를 해시테이블 이라 한다.

Jdk 클래스HashMap과 properties이다.

 

배열 

동일한 데이터를 순서에 따라 관리하는구조이다.

정해진 메모리크기가있다

요소의 추가와 제거시 다른 요소들의 이동이 필요하며 배열 N번째 요소를 찾는 인덱스 연산이 빠르다.

 

연결 리스트( LinkedList) 구현하기

동일한 데이터 순서에 따라 관리하는 구조이며 자료를 저장하는(Node)에는 자료와 다음 요소를 가르키는 링크포인터가 있다,

자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함(정해진 크기가 없음)
연결 리스트 n번째 요소를 찾는게 걸리는 시간은 요소의 개수 비례O(n)

스택(Stack) 

마지막 위치(top)에서 만 자료를 추가 삭제 호출 (중간있는 자료를 꺼낼 수 없음)

Last in Frist Out 후입선출 구조 

택배 상자가 쌓여 있는 모양이며 가장 최근에 대한 자료를 찾아 오거나 게임에서 히스토리를 유지하고 이를 무를때 사용 할수있다.

함수의 메모리는 호출 순서에 따른 stack 구조)

 

큐(Queue) 구현하기 

첫번째 자료를 호출 하거나 삭제하고 마지막 자료에서 추가한다.

First in First Out(선입 선출) 구조

일상 생활에서 일렬로 줄서 있는 모양이다.

순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용되는 구조이다 홈쇼핑에 들어온 구입목록 등 활용된다.

제너릭(Generic)

클래스에서 사용하는 변수의 자료형이 여러개 알 수 있고, 그 함수은 동일한 경우 클래스의 자료형을 특정하지않고 추후 해당 클래스안에서 사용할때에 지정 할 수있도록 선언한다.

실제 사용되는 자료형의 변환은 컴파일러에 의해 검증 되므로 안정적인 프로그래밍 방식이다.

컬랙션 프레임 워크에서 많이 사용되고 있다,

T(type paraneter) 이클래스를 사용하는시점에 실제 사용할 자료형을 지정 스택 변수는 사용할수 없다.

E: element K: key V: value등 여려가지의 알파벳을 의미에 따라서 사용가능하다.

다이어몬드 연산자 

다이아몬드 연산자는 <>로 사용되며(자바 10)부터 

ArrayList list = new ArrayList <> (); // 다이어몬드 연산자안에서 자료형은 생략 할수 도 있다.

ex) ArrayList list = new ArrayList()를 varList = new ArrayList();로 자료형이 생략 할수이다.

 

 

 

<T extends 클래스 > 사용하기 

T 자료형의 범위를 제한 할 수있으며 

상위클래스에서 선언하거나 정의하는 함수를 활용 할  수 있다.

상속 받지 않는 경우 T는 Object로 변환 되어 ObjectClass가 기본으로 제공하는 메서드만 사용가능해서 T extends 클래스가 필요하다.

제네릭 함수란

자료형 매개 변수를 함수의 매개변수나 return 값으로 가지는 함수다.

자료형 매개 변수 하나 이상인 경우도 있으며 제네릭 클래스가 아니어도 내부에 제내릭 함수는 구현하여 사용 할 수있다.

Public<자료형 매개변수> 반환형 함수 이름

컬렉션 프레임 워크 

프래그램 구현에 필요한 자료 구조를 구현해놓은 JDK 라이브러리

java.util패키지에 구현되었 있으며 개발 소요 되는 시간을 절약하면서 최적화 된 알고리즘을 사용할수있다.

여러 구현 클래스의 인터페이스의 활용에 대한 이해가 필요하다,

 

컬렉션 인터페이스

하나의 객체를 관리하기 위한 함수 가 선언된 인터페이스이며 하위클래스에 List와 set인터페이스가 있다.

List 인터페이스 

객체에 순서에 따라 저장하고 관리하는데 필요한 함수가 선언된 인터페이스다.

자료구조 리스트(배열과 링크드리스트) 구현을 위한 인터페이스 이며중복을 하여 사용할수있다.

배열 리스트 벡터,링크드리스트 퀸등등

Set 인터페이스

순서와 관계없이 중복을 허용하지 않고 유일한 값을 관리하는데 필요한 메서드가 선언된다.

주민번호 사원번호 택배운송장 영화표 티켓등을 관리하는데 유용하다.

저장된 순서와 출력되는 순서는 다를 수있다.

Map인터페이스

쌍(pair)로 이루어진 객체를 관리하는데 사용하는 메서드들이 선언된 인터페이스다.

객체는 Key- value의 쌍으로 이루어지며 Key는 중복이 허용되지않는다.

요소의 순회 

컬렉션 프레임워크에 저장된 요소들을 하나씩 차례로 참조이며 순서가 있는 리스트 인터페이스의 경우는 Iterater를 사용하지 않고 

get(i)메서드를 활용할수있다.

set 인터페이스의 경우 get(i)메서드가 제공되지 않으며Iterater를 활용하여 객체를 순회한다.

boolean hasNext();이후 에 요소가 더있는지를 확인하는 함수, 요소가 있다면 ture를 반환되며 E next() 다음에 요소를 반환한다.

hashSet 클래스

Set 인터페이스를 구현한 클래스와 멤버의 중복되는지 여부를 확인 하기 위해 인스턴스의 같은지 확인해야한다.

equals()와 HashCode()함수를 같게 구현했는지 확인하기위해서 재정의해야한다.



Comparable과 Comparator 인터페이스 구현하기 

TreeSet클래스 활용하기

객체의 정렬에 사용하는클래스 

set 인터페이스를 구현하여 중복을 허용하지 않고,오름차순이나 내림차순으로 객체를 정렬할수있다.

이진 검색트리에 저장하기 위한 객체를 비교해야하며 이진검색트리 안에서 구현된다,

비교 대상이 되는 객체 Comparable과 Comparator 인터페이스를 구현해야 TREE SEt에 추가 될 수있다.

string integer등 JDK의 많은 클래스들이 이미  Comparable 구현 했다.

Hash Map 클래스 

Map 인터페이스를 구현한 클래스이며 가장 많이 사용되느 Map 인터페이스 기반 클래스 Key -value를 쌍으로 관리하는 함수를 구현함

검색을 위한 자료구조이며

Key를 이용하여 값을 지정하고 Key를 이용하여 값을 꺼내 오는 방식이며 hash 알리고즘에 구현된다.

Key가 되는 객체는 중복 될 수 가 없고 객체의 유일성을 비교를 위한 equals와 Hashcode 함수를 구현해야한다.

트리맵

Map 인터페이스를 구현한 클래스이고 Key에 대한 정렬을 구현 할 수 있다.

Key가 되는 클래스에 Comparable과 Comparator 인터페이스를 구현해서 Key-value쌍의 자료를 Key값 기준으로 정렬하여 관리 할수있다.