Java/Data Structure (자료구조)4 [자료구조] 이진 트리 (Binary Tree) Binary Tree (이진 트리) 각 노드가 최대 2개의 자식을 갖는 트리 ■ 정의 - 루트: 트리의 가장 윗부분에 위치하는 노드 - 리프: 트리의 가장 아랫부분에 위치하는 노드 - 안쪽 노드: 리프를 제외한 나머지 노드(루트 포함) - 자식: 어떤 노드에서 가지로 연결된 아래쪽 노드 - 부모: 어떤 노드에서 가지로 연결된 바로 위쪽 노드 - 형제: 부모가 같은 노드 - 레벨: 루트로부터 얼마나 떨어져 있는지를 나타낸 값 - 차수: 노드가 갖는 자식의 수 - 높이: 루트에서 가장 멀리 떨어진 리프까지의 거리 - 서브트리: 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리 Binary Tree(이진 트리) 순회 방법 ■ 정의 ● preorder (전위 순회) : root Node -.. 2023. 3. 29. [자료구조] 연결리스트 (LinkedList) / 배열리스트 (ArrayList) LinkedList (연결리스트) ■ 정의 - LinkedList (연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값을 가지고 각 포인터 변수의 주소도 따로 존재 ■ 생성자 - LinkedList list = new LinkedList(); ■ Code 더보기 import java.util.Comparator; public class LinkedList { class Node { private E data; private Node next; Node(E data, Node next) { this.data = data; this.next = next; } } private Node hea.. 2023. 3. 28. [자료구조] 덱(Dequeue, Double-ended Queue) 덱 (Dequeue, Double-ended Queue) ■ 정의 - Dequeue(덱)은 양쪽에서 넣고 빼고가 가능한 큐 - 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라 스택, 큐 모두 사용 가능 - 스케줄링이 복잡해질수록 큐와 스택보다 효율이 잘 나옴 ■ 메소드 Deque dq = new LinkedList(); 메소드 의미 addFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 예외 발생 offerFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 false 리턴 addLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 예외 발생 offerLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 false 리턴 r.. 2023. 2. 24. [자료구조] 스택(Stack) / 큐(Queue) 스택(Stack) ■ 정의 - 데이터를 일시적으로 쌓아 놓는 자료구조 - 데이터의 입력과 출력 순서는 후입선출 (LIFO: Last In First Out) ■ 메소드 Stack s = new Stack(); Stack s = new Stack(int capacity); // 스택의 capacity 결정 메소드 의미 push(int item) 스택에 데이터를 저장 pop() 스택의 꼭대기에 있는 데이터를 제거하고, 그 값을 반환 isFull() 스택이 empty 상태인지 확인 isEmpty() 스택이 full 상태인지 확인 clear() 스택의 모든 요소를 삭제 peek() 스택의 가장 최상위(마지막)에 위치한 데이터 출력 capacity() 스택의 용량 확인 (스택 전체 크기) size() 스택의 크기.. 2023. 2. 22. 이전 1 다음
