같은 종류의 데이터를 순차적으로 저장하는 자료구조
➡ 장점
➡ 단점
배열 | 리스트 | |
---|---|---|
데이터 | 같은 타입의 데이터만 저장 | 다양한 데이터를 저장할 수 있음 |
크기 | 처음 저장한 후 변경X | 가변적으로 변경 가능 |
Integer data_list[] = new integer[10]; //선언
Integer[] data_list = new integer[10]; //가능
data_list[0] = 1 // 할당
Integer data_list[] = {1, 2, 3, 4, 5}; //초기화
System.out.println(data_list[2]); // 출력
ArrayList 클래스는 가변 길이의 배열 자료구조를 다룰 수 있는 기능 제공
import java.util.ArrayList;
ArrayList<Integer> list1 = new ArrayList<Integer>(); // 선언
list1.add(1); // 배열에 아이템 추가 (추가할 값)
list1.get(0); // 배열에 아이템 읽기 (인덱스 번호)
list1.set(0, 5); // 배열에 아이템 변경 (인덱스 번호, 변경할 값)
특정 기준에 의해 오름차순/내림차순 순서대로 재배열 하는 것
종류
def BubbleSort(a):
for i in range(len(a)-1),0,-1):
for j in range(0,i):
if a[j] > a[j+1]:
a[j],a[j+1] = a[j+1],a[j]
카운팅 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬 ➡ O(n+k)
선택 정렬 ➡ O(n²)
퀵 정렬 ➡ [평균]O(nlogn) [최악] O(n²)
삽입 정렬 ➡ O(n²)
병합 정렬 ➡ O(nlogn)
한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
➡ LIFO 방식 (Last In First Out)
➡ push : 데이터를 스택에 넣기
➡ pop : 데이터를 스택에서 꺼내기
Import java.util.Stack;
Stack<Integer> stack_int = new Stack<Integer>(); // 정수형 선언
stack_int.push(1); // 데이터 추가
stack_int.push(2);
stack_int.pop(); // 데이터 추출
Import java.util.ArrayList;
public class MyStack<T> {
private ArrayList<T> stack = new ArrayList<T>();
public void push(T item) {
stack.add(item);
}
public T pop() {
if (stack.isEmpty()) {
return null;
}
return stack.remove(stack.size() - 1);
}
public boolean isEmpty() {
return stack.isEmpty();
}
public static void main(String[] args) {
MyStack<Integer> ms = new MyStack<Integer>();
ms.push(1);
ms.push(2);
System.out.println(ms.pop());
System.out.println(ms.pop());
}
}
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
➡ FIFO 방식 (First In First Out)
➡ Enqueue : 큐에 데이터를 넣는 기능
➡ Dequeue : 큐에서 데이터를 꺼내는 기능
➡ 사용
import java.util.LinkedList; // 큐 사용 위해 필요
import java.util.Queue;
Queue<Integer> queue_int = new LinkedList<Integer>(); // 정수형 선언
Queue<String> queue_str = new LinkedList<String>(); // 문자형 선언
queue_int.add(1); // 삽입 성공 여부 return (true/false)
queue_int.offer(2);
queue_int.poll(); // 삭제한 값 return
queue_int.remove();
public class MyQueue<T> {
private ArrayList<T> queue = new ArrayList<T>();
public void enqueue(T item) {
queue.add(item);
}
public T dequeue() {
if (queue.isEmpty()) {
return null;
}
return queue.remove(0); // 첫번째 인덱스 삭제
}
public boolean isEmpty() {
return queue.isEmpty();
{
public static void main(String[] args) {
MyQueue<Integer> mq = new Myqueue<Integer>();
mq.enqueue(1);
mq.enqueue(2);
mq.enqueue(3);
System.out.println(mq.dequeue());
System.out.println(mq.dequeue());
System.out.println(mq.dequeue());
}
}
✔ 특징
➡ 리스트로 구현
➡ 큐의 크기 = 리스트의 크기
➡ 삽입 위치 : rear = rear+1
➡ 삭제 위치 : front = front+1
✔ 상태
➡ 초기 상태 : front = rear = -1
➡ 공백 상태 : front = rear
➡ 포화 상태 : rear = n-1
✔ 특징
➡ 리스트로 구현
➡ 리스트의 처음과 끝이 연결된 원형 형태의 큐
➡ 삽입 위치 : rear = (rear+1) % n
➡ 삭제 위치 : front = (front+1) % n
✔ 상태
➡ 초기 상태 : front = rear = 0
➡ 공백 상태 : front = rear
➡ 포화 상태 : rear+1 = front
✔ 특징
➡ 연결 리스르토 구현
➡ 노드의 연결 순서는 링크로 연결
✔ 상태
➡ 초기 상태 : front = rear = None
➡ 공백 상태 : front = rear = None
➡ 포화 상태 :
✔ 특징
➡ 장점
➡ 단점
✔ Linked List 클래스
public class Node<T> {
T data;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
// Node 인스턴스간 연결
Node<Integer>node1 = new Node<Integer>(1);
Node<Integer>node2 = new Node<Integer>(2);
node1.next = node2;
Node head = node1;
// 연결 리스트에 데이터 추가
public class SingleLinkedList<T> {
public Node<T> head = null;
public clss Node<T> {
T data;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
public void addNode(T data) {
if (head == null) {
head = new Node<T>(data);
}
else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
}
}
}
SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<integer>();
MyLinkedListaddNode(1);
MyLinkedList.head.data;
MyLinkedList.addNode(2);
MyLinkedList.head.next.data;
✔ 특징
➡ 양방향으로 연결 (노드 탐색 양쪽으로 모두 가능)
✔ Double Linked List 클래스
public class DoubleLinkedList<T> {
public Node<T> head = null;
public Node<T> tail = null;
public class Node<T> {
T data;
Node<T> prev = null;
Node<T> next = next;
public Node(T data) {
this.data = data;
}
}
public void addNode(T data) {
if (this.head == null) {
this.head = new Node<T>(data);
this.tail = this.head;
} else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
node.next.prev = node;
this.tail = node.next;
}
}
public void printAll() {
if (this.head != null) {
Node<T> node = this.head;
System.out.println(node.data);
while (node.next != null) {
node = node.next;
System.out.println(node.data);
}
}
}
// head부터 검색
public T searchFromHead(T isData) {
if(this.head == null) {
return null;
} else {
Node<T> node = this.head;
while (node != null) {
if (node.data == isData) {
return node.data;
} else {
node = node.next;
}
}
return null;
}
}
// tail부터 검색
public T searchFromTail(T isData) {
if (this.head == null) {
return null;
} else {
Node<T> node = this.tail;
while (node != null) {
if (node.data == isData) {
return node.data;
} else {
node = node.prev;
}
}
}
}
}
DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();
MyLinkedList.add.Node(2);
MyLinkedList.add.Node(3);
MyLinkedList.printAll();
➡ 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조
➡ 해쉬 함수를 통해 배열에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
➡ 해쉬 함수 : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
➡ 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
✔ 특징
➡ Key를 통해 저장 및 탐색 속도가 획기적으로 빨라짐
➡ 주소(인덱스 번호)에 대한 공간을 배열로 미리 할당한 후, 키에 따른 데이터 저장 및 탐색 지원
✔ HashTable 클래스
public class MyHash {
public Slot[] hastTable;
public MyHash(Integer size) {
this.hashTable = new Slot[size];
}
public clas Slot {
String value;
Slot(String value) {
this.value = value;
}
}
}
문제
코드
해설
문제
코드
해설
데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 이진 트리
✔ 특징
➡ 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같음 (최대힙의 경우)
➡ 완전이진트리 형태를 가짐
✔ 힙 vs 이진탐색트리
➡ 힙 : 각 노드의 값이 자식 노드보다 크거나 같음
➡ 이진탐색트리 : 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽
문제
코드
해설
문제
코드
해설
➡