Linked List

데이터 와 link 로 구성된 노드의 개념을 이용해서 데이터를 저장하는 선형 자료구조

• 노드를 물리적으로 연속해서 저장하지 않고 link를 이용해서 다음 데이터를 가리키는 형태로 데이터를 저장하는 방식

Double Linked List

Link 가 2개로 Binary Tree 구현에 이용

[자료구조] 덱

덱은 기존의 원형 큐에서 일부 기능이 추가된, 전단과 후단 양쪽 모두에서 삽입과 삭제의 입출력과 반환이 가능한 원형 큐

HashSet

• Set의 파생클래스 (Collection)

  • 중복되는 원소를 넣는경우 하나만 저장된다
    • 중복원소를 허용하지않는다
  • hashSet은 순서개념이없다. 따라서 Collection.sort()를 사용할수없다. 만약정렬을 하고 싶다면 리스트로 변환 후 정렬해야함 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드 사용방법

• getOrDefault(Object key, V DefaultValue)

• key : 값을 가져와야 하는 요소의 키입니다.

• defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값입니다. 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환됩니다.

StringTokenizer

• 문자열을 구분자로 이용하여 분리할때 사용함
• 만약에 BufferedReader 메서드로 입력을 읽어들이면 라인 단위로 읽어들일수에없다
• 꼭 BufferedReader 가 아니더라도 스페이스 기준으로 또는 컴마,공백 을 기준으로 문자열들을 분리해줄수있고 특정 문자에 따라 문자열을 나누고싶을때 StringTokenizer를 사용함

 StringTokenizer st=new StringTokenizer(); //객체생성
    StringTokenizer st=new StringTokenizer(분리할문자열,구분자); //문자열분리
    StringTokenizer st=new StringTokenizer(분리할문자열,구분자,boolean); // boolean은 구분자로 분리된 문자열을 토큰에 포함시키냐 여부 
//default는 false다 

Scanner
//압력받는 값이 있는가 확인하는함수는 
//hasNext(), hasNextInt()

선택정렬

• 전체 배열에서 가장 작은요소를 찾고 그 요소를 배열의 첫 번째 요소와 교환.
• 그 후 A의 두번째 요소부터 마지막 요소까지 확인하여 가장 작은 요소를 찾은 후
  그 요소를 두 번째 요소와 교환
• n-1 번을 반복.

삽입 정렬

9 7 8 2 5

• 7이 9보다 작으므로 7을 9앞에 삽입

7 9 8 2 5

• 7 9 는 했고 9,8을 비교

7 8 9 2 5

• 7 8 9 는 정렬되어있고 2는 앞에있는 모든 요소보다 작으므로 7앞에 삽입

2 7 8 9 5

• 5 또한 앞에 index들보다는 작고 2보단 크므로 2 앞에 5를 삽입

2 5 7 8 9 완료

힙정렬

트리

• 부모노드 : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미
• 자식노드 : 자기 자신 과 연결 된 노드 중 자신보다 낮은 노드를 의미
• 루트노드 : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다.
• 단말노드 : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미함 .
• 내부노드 : 단말 노드가 아닌 노드
• 형제 노드 : 부모가 같은 노드를 말한다
• 깊이 : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미
• 레벨 : 특정 깊이에 있는 노드들의 집합을 말함.
• 차수 : 특정 노드가 하위 (자식) 노드와 연결 된 개수

이진트리

모든 노드의 최대 차수를 2로 제한함. 즉 노드는 자식노드를 최대 2개까지 밖에 못갖는것을 '이진트리'라고함

완전 이진트리

• '마지막 레벨' 을 제외한 모든 노드가 채워져있으면서 모든 노드 (=사실상 마지막 레벨의 노드들)가 왼쪽부터 채워져있어야함.

LinkedList

LinkedList는 ArrayList와 가장 큰 차이점은 '노드' 객체를 이용을 해서 연결한다.

• LinkedList는 배열을 이용하는 것이 아닌 하나의 객체를 두고 그 안에 데이터와 다른 노드를 가리키는 래퍼런스 데이터로 구성하여 여러노드를 하나의 체인 처럼 연결하는것

• 하나의 노드 객체에는 저당할 데이터 data 가 변수에 담기고 reference 데이터(참조 데이터) 다음에 연결할 노드를 가리키는 데이터가 담긴다 .

BFS(깊이우선탐색) DFS(너비우선탐)

• 정점
  • 각 출발점과 도착점
• 간선
  • 그 정점과 연결된 관ㄱ ㅖ
• DFS 스택사용, 이동과정을 할때 주로계산
• BFS 큐 사용 , 최단거리 계산할때 주로계산
• 나중에들어온사람이먼저나가고 스택
• 먼저들어온사람이 먼저나간다 큐