자료구조 & Java 컬렉션 프레임워크 공부

자료구조란? 자료구조(Data Structure) > * 데이터 단위와 데이터 자체 간의 물리적 또는 논리적 관계 > * 프로그램을 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것으로 정의할 때, '데이터의 표현'을 담당하는 것 자료구조의 종류 > 선형

1. 컬렉션 프레임워크란? 2. 컬렉션 프레임워크의 핵심 인터페이스 3. 컬렉션 클래스 정리 & 요약 컬렉션 클래스 간 관계 컬렉션 클래스별 특징 Reference

리스트 리스트(List) 개념 정리 > * 데이터를 일렬로 나열한 자료구조 > * 배열 기반 리스트(ArrayList)와 연결 리스트(LinkedList)로 세분 가능 > * 중복된 데이터 저장 가능 Reference Do-it! 자료구조와 함께 배우는 알고리즘

Java 컬렉션 프레임워크에서 List 인터페이스를 구현한 컬렉션 클래스: 데이터의 저장 순서를 유지하고, 데이터의 중복을 허용Object 배열을 이용해서 데이터를 순차적으로 저장하고, 이 배열이 포화 상태면 보다 더 큰 새로운 배열을 생성한 후 기존 배열의 데이터를

1. 연결 리스트 연결리스트의 기본 특징 > * 리스트의 데이터를 저장하는 노드(Node)들이 사슬의 형태로 연결된 리스트 > * 저장할 데이터의 개수는 리스트 초기화 시점에서 따로 결정되지 않음(동적 할당) > * 데이터 삽입/삭제 - $$O(1)$$ : 데이터

1. java.util.LinkedList 개괄 > * 원형 이중 연결 리스트의 형태로 구현 : > * 한 노드가 다른 노드를 연결/분리하는 방식으로 동작 > * 기본적으로는 비동기화된 리스트이기 때문에, 동기화가 필요한 경우 Collections.synchroniz

ArrayList시간복잡도는 $$O(1)$$인덱스가 N인 데이터 주소 = 배열 시작 주소 + 데이터 타입의 크기 \* N: 배열의 시작 주소, 데이터 타입의 크기, 접근하려는 인덱스 값을 알면 접근하려는 데이터의 위치를 계산 가능LinkedList최악의 경우 시간복잡도

1. 스택(Stack) > * 후입 선출(LIFO; Last-In, First-Out) 구조의 자료구조 > : 가장 나중에 저장된 데이터부터 가장 먼저 꺼내는 방식의 자료구조 2. 스택 구현 스택의 주요 기능 정의 Stack 인터페이스 배열을 사용한 스택 구현

상위 클래스java.util.Vector컬렉션 프레임워크가 등장하기 이전에 사용된, 객체배열에 관한 컬렉션 클래스: 저장 가능 용량 초과 시, 기존의 용량을 증가시킨 객체배열을 재생성한 후 기존 데이터를 복사하여 사용일부 메서드에서 synchronized 키워드 사용:

선입선출(FIFO; First-In, First-Out) 구조의 자료구조: 가장 먼저 저장된 데이터부터 가장 먼저 꺼내는 방식의 자료구조구현 코드는 여기에서 확인 가능Queue 인터페이스ArrayBaseQueue 클래스실행용 코드 및 실행 결과LinkedListBase

add() 메서드offer() 메서드public boolean add(Object e) / public boolean offer(Object e)큐의 맨 마지막에 새로운 데이터를 추가Queue의 offer() 메서드는 add() 메서드를 바탕으로 구현remove() 메

1. 덱 > * Deque; Double-Ended QUEue : 데이터의 추가/삭제를 양방향으로 수행할 수 있는 선형 자료구조 > * 스택과 큐의 특성을 모두 보유 2. 덱 구현 전체 구현 코드는 여기에서 확인 가능 덱의 주요 기능 정의 Deque 인터페이스

배열 기반 링 버퍼로 덱 자료구조를 구현java.util.Stack 기반 스택, java.util.LinkedList 기반 큐보다 실행 속도가 빠름: 내부 코드에서는 저장 위치에 관계없이 인덱스를 사용해서 덱의 현재 머리/꼬리에 바로 접근 가능하기 때문(어디까지나 내부

키(key)와 값(value)이 하나의 쌍을 이루어 저장되는 자료 구조테이블에서 키는 고유값을 가지며, 키가 존재하지 않는 값은 저장 불가키 값을 사용해 임의의 위치에 저장된 값에 접근 가능: 탐색 시 시간복잡도는 $$O(1)$$딕셔너리(dictionary) 또는 맵(

데이터 간의 계층적 관계를 나타내기 위한 비선형 자료구조: 트리의 핵심은 계층적 관계의 표현이며, 데이터 저장/삭제는 이를 위한 수단트리 구성 요소 관련노드(Node)트리에서 데이터가 저장되는 부분간선(Edge)노드와 노드를 연결하는 연결선루트 노드(Root Node)

1. java.util.HashMap 개괄 Java 언어에서의 해싱 방법 - 체인법 체인법(chaining) 개요 > * 해시 테이블의 버킷은 배열, 각 버킷에 저장할 데이터는 연결리스트의 노드로 구현 > : 해시 코드가 동일하여 데이터를 저장할 버킷이 중복될 때

1. java.util.HashSet 개괄 연관된 인터페이스/클래스

1. java.util.TreeMap 개괄 > * 이진 검색 트리를 사용하여 키-값 쌍으로 이루어진 데이터를 저장하는 컬렉션 클래스 > * Map 인터페이스를 구현 > * HashMap에 비해 범위 검색과 정렬에 특화됨 : 단, 검색을 수행하는 대부분의 경우 Hash

이진 검색 트리를 기반으로 데이터를 저장하는 컬렉션 클래스: 레드-블랙 트리로 구현정렬, 검색, 범위 검색에 특화됨데이터 추가/삭제 시간이 느림: 데이터 추가 시 저장 위치를 탐색하는 작업을 필요로 하고, 삭제 시에는 트리의 일부를 재구성해야 하기 때문Set 인터페이스