배열(Array) : 요소들을 인덱스에 기반하여 연속적으로 저장하는 자료구조 ArrayList : 동적 크기를 가지는 배열로, 내부적으로 배열을 사용하여 구현되는 자료구조 LinkedList : 각 요소들을 노드로 구성하고, 노드들은 데이터와 다음 노드를 가리키는 포인터로 연결되는 자료구조 Array, ArrayList, LinkedList 비교 1. 크기 조정 배열 : 고정 크기로 선언되며, 크기를 변경할 수 없다. ArrayList, LinkedList : 동적으로 크기가 조정된다. 2. 타입 제한 배열 : 제네릭 타입 사용 불가능 ArrayList, LinkedList : 제네릭 타입을 사용가능 배열에 제네릭 타입을 사용할 수 없는 이유는 배열은 컴파일 시점에서 자신의 요소 타입을 알고 있어야 하는..
연결리스트란? 연결리스트 : 데이터 요소들을 노드(Node)라는 단위로 구성하여 메모리 상에서 연속적으로 배치되지 않고, 각 노드들이 포인터(Pointer)로 연결되어 있는 자료구조 • 각 노드는 데이터를 저장하는 데이터 필드(data field)와 다음 노드를 가리키는 링크 필드(link field)로 구성되어 있다 단방향 연결리스트(Singly Linked List) : 각 노드가 다음 노드를 가리키는 링크 필드만을 갖고 있다. 이러한 구조로 인해 단방향으로 노드들이 연결되어 있다. 양방향 연결리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 링크 필드를 갖고 있다. 양방향으로 노드들이 연결되어 있기 때문에 양쪽 방향으로 노드를 탐색할 수 있다. 연결리스트의 ..
배열이란? 배열 : 동일한 데이터 유형의 요소들을 일렬로 나열한 것 • 논리적 저장 순서와 물리적 저장 순서가 일치한다. • 각 요소는 인덱스를 통해 접근할 수 있다. • 메모리 상에 연속적으로 할당된다. 배열의 장단점 장점 1. 빠른 접근 : 인덱스를 통해 요소에 빠르게 접근할 수 있다. 시간복잡도는 O(1)이다. 단점 1. 크기 제한 : 생성할 때 크기를 정해야 하며, 이 크기는 변경할 수 없다. 2. 메모리 낭비 : 미리 정해진 크기를 사용하기 때문에 요소가 모두 채워지지 않는 경우 메모리를 낭비할 수 있다. 크기를 크게 설정하면 필요 이상의 메모리를 사용하게 되고, 작게 설정하면 요소를 저장할 공간이 부족해질 수 있다. 또한, 빈 메모리 공간이 배열의 크기 보다 작으면 사용할 수 없다. 3. 삽입..
Queue란? 선입선출 (First In First Out; FIFO) 자료구조 먼저 들어온 데이터가 먼저 나가는 구조 입력 순서대로 데이터 처리가 필요할 때 사용 BFS (Breath-First Search) Queue 기본 구조 Queue 기본 연산 Queue 생성 큐는 배열기반의 컬렉션 클래스를 사용하면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터를 복사해야 하므로 LinkedList로 구현하는 것이 적합하다. import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkedList(); // Queue는 interface로 구현되어 있음. 따라서 바로 객체로 만들 수 없음. -> Queue queue = new Que..
스택 (Stack) 후입선출 (Last In First Out; LIFO) 자료구조 - 마지막에 들어온 데이터가 먼저 나가는 구조 - First In Last Out (FILO) 라고 하기도 한다. 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열 기반의 클래스를 사용하는 것이 적합하다. 스택의 기본 구조 스택의 기본 연산 push(item) - 스택의 Top에 요소 저장 pop() - 스택의 가장 마지막 요소를 반환하며 삭제 - 만약 스택이 비어있을 때 pop()을 한다면 EmptyStackException 발생 peek() - 스택의 가장 마지막 요소를 반환하지만 삭제는 하지 않는다. contains(item) - 스택 안에 요소가 있는지 확인 search(item) - 스택..
