자료구조
-
Array와 LinkedList의 차이자료구조 2023. 1. 5. 15:18
배열(Array) : 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조 -> 인덱스를 통해 접근이 용이 배열의 크기는 생성 시에 결정하며 변경이 불가하다. 장점 메모리 상에 연속적으로 저장되어 있어 index만 알면 Random Access 가능 (* Random Access : 자료의 주소를 알고 있다면 모든 자료에 대해 동일한 시간에 접근이 가능한 방식) 단점 삽입, 삭제 시 삽입이나 삭제를 하려는 위치 이후의 데이터 값을 모두 한칸씩 이동시켜야 하므로 비효율적 배열의 크기를 변경할 수 없음 시간복잡도 탐색 : O(1) (index를 아는 경우) 삽입/삭제 : O(n) LinkedList : 노드들이 순차적으로 연결된 형태를 띄고 있으며 첫 노드는 head, 마지막 노드는 tail이라 한다..
-
자료구조란? Data Structure자료구조 2023. 1. 4. 14:16
자료구조란? : 데이터의 집합을 의미하며 자료들을 더 효율적으로 저장, 관리하기 위해 사용된다. 자료구조의 선택 기준 자료의 처리 시간 자료의 크기 자료의 활용 빈도 자료의 갱신 빈도 프로그램의 용이성 자료구조의 특징 1. 효율성 : 데이터를 목적에 맞게 효율적으로 관리, 사용하여 업무의 효율을 높인다. 2. 추상화 : 추상화란 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것. 자료구조를 이용하면 데이터를 언제, 어떻게 사용할 것인지만 고려하면 되고, 내부 구현에 대해서는 고려하지 않아도 되므로 구현 외적인 부분에 더 신경쓸 수 있다. 3. 재사용성 : 다양한 프로그램에서 범용적으로 사용 가능하다. 자료구조의 분류 선형 구조 Array, LinkedList, Stack, Queu..
-
Deque(덱, 데크) - 자바자료구조 2022. 8. 6. 16:06
: deque란 Double-Ended Queue로 FIFO 형식의 일반적인 큐와 다르게 큐의 양쪽으로 삽입과 삭제를 할 수 있는 자료구조 선언 Deque dq = new LinkedList(); Deque dq = new ArrayDeque(); add() addFirst() addLast() offer() offerFirst() offerLast() add() 와 offer()은 addLast() offerLast()와 같은 의미 remove() removeFirst() removeLast() poll() pollFirst() pollLast() remove() 와 poll()은 removeFirst()와 pollFirst()와 같은 의미 getFirst() getLast() peek() peekFi..
-
큐 구현자료구조 2022. 3. 29. 15:22
public class Queue { private int max; private int front; private int rear; private int num; //현재 큐에 들어있는 수들의 개수 private int[] que; public class EmptyQueueException extends RuntimeException { } public class OverflowQueueException extends RuntimeException { } public Queue(int capacity) { max = capacity; front = 0; rear = 0; num = 0; try { que = new int[max]; }catch (OutOfMemoryError e) { max = 0; ..
-
스택 구현자료구조 2022. 3. 29. 14:31
public class Stack { private int ptr; private int max; private int[] stk; public class EmptyStackException extends RuntimeException { } public class OverflowStackException extends RuntimeException { } public Stack(int capacity) { ptr = 0; max = capacity; try { stk = new int[max]; }catch (OutOfMemoryError e) { max = 0; } } public int push(int x) throws OverflowStackException { if (ptr >= max) thr..