[02] 주요 자료 구조

01. 자료구조의 정의와 필요성

데이터(Data)란 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값을 의미한다. 그리고 이러한 데이터를 분석하고 정리하여, 궁극적으로 목적에 맞춰 데이터를 효율적으로 활용하기 위해 데이터를 체계적으로 정리하여 저장하는 데이터 공간을 자료 구조라고 한다. 효율적인 자료 구조는 빠르고 정확한 데이터 검색을 가능하게 할 뿐만 아니라, 데이터의 삽입 / 삭제 / 수정 연산의 효율을 증가시키고 메모리와 처리 시간 자원의 효율성을 극대화 시킨다.

 

[그림 1] 자료 구조의 종류와 구조

 

---

 

02. 자료 구조의 분류 기준

1. 선형 구조 vs 비선형 구조

	선형 구조	비선형 구조
설명	데이터가 일렬로 순차적으로 나열된 구조 >> 이전 또는 다음 요소와 1:1로 연결	데이터가 계층적(Tree) 또는 복잡한 관계(Graph)로 연결된 구조
연결 방식	1:1 연결	1:N 또는 N:N
메모리 구조	메모리에 연속 또는 단순 연결로 저장	비연속적 메모리에 저장되며, 포인터로 관계 유지
탐색 방식	앞 → 뒤 또는 뒤 → 앞으로 탐색	DFS, BFS 등 다양한 그래프 탐색 알고리즘 필요
주요 예시	Array, List, Stack, Queue, Deque	트리(Tree), 그래프(Graph), 힙(Heap), 트라이(Trie)
활용 예시	대기열 처리, 함수 호출 스택, 브라우저 상태 보관	폴더 구조, 조직도, 경로 탐색, 데이터베이스 데이터 보관(인덱스)

 

2. 정적 구조 vs 동적 구조

	정적 구조	동적 구조
설명	자료구조의 크기나 형태가 프로그램 실행 전에 결정	실행 중 데이터 양에 따라 크기나 형태를 유동적으로 변경 가능
메모리 할당	컴파일 타임에 고정된 메모리 할당	런타임에 필요할 때마다 메모리 동적 할당
크기 조절	변경 불가능	가능
성능 특징	빠른 접근 속도(O(1)), 크기 초과 시 오버 플로우 위험	메모리 낭비는 적지만, 포인터 접근으로 인한 속도 저하
주요 예시	Array	LinkedList, ArrayList, HashMap, Tree
활용 예시	고정 크기 데이터 처리, 배열 기반 연산, 고정 길이 버퍼 등	실시간 입력 처리, 데이터 추가 / 삭제 빈번 시스템, 가변 길이 버퍼 등

 

---

 

03. 자료 구조 선택 시 고려사항

1. 데이터 특성에 따른 선택

데이터 특성	적합한 자료 구조
대용량 데이터 처리	ArrayList, LinkedList
고정 크기 데이터	Array
변경(삽입/삭제) 빈도 높음	LinkedList
정렬 상태 유지 필요	TreeMap, TreeSet
정렬 필요 없음	HashMap, HashSet

 

2. 연산의 종류 및 빈도

연산 유형	적합한 자료 구조
검색 연산이 빈번함	HashMap, TreeSet
삽입/삭제 연산이 빈번함	Stack, Queue, LinkedList

 

3. 메모리 사용량 비교

자료 구조	메모리 특징
배열 (Array)	데이터만 저장 →메모리 효율적
연결 리스트	데이터 + 포인터 저장 → 메모리 소모 큼
Hash 계열	빠른 검색 속도 제공 → 메모리 오버헤드 존재

 

---

 

04. List | ArrayList, LinkedList

1. ArratList의 내부 저장 방식

ArrayList는 내부적으로 연속적인 메모리 공간을 활용한 배열 구조를 활용한다. 이처럼 ArrayList 인스턴스를 생성하면 내부적으로 10칸짜리 배열을 생성하며, 인덱스를 활용한 빠른 접근 및 검색 연산을 지원한다.

[그림 1] ArrayList

2. ArrayList의 동적 크기 조정 원리

ArrayList는 내부적으로 고정된 크기의 배열을 유지하다가 배열의 크기를 늘려야 할 때 다음과 같은 메커니즘을 자동으로 수행한다.

메커니즘 순서
새로운 배열 생성	기존 배열의 크기를 약 1.5배로 늘린 새로운 배열을 생성
기존 데이터 복사	기존 배열에 있던 모든 데이터를 새로운 배열에 깊은 복사를 통해 복사 >> 내부적으로 System.arraycopy() 메서드 사용
참조 변경	기존 배열을 가리키던 참조 주소를 새로운 배열의 참조 주소로 변경

 

3. ArrayList의 동적 크기 조정 시 발생하는 성능 이슈

이러한 성능 비용을 줄이기 위해 인스턴스를 생성하는 시점에서 초기 용량을 설정할 수 있다.

 

ArrayList<String> list = new ArrayList<>(1000);

 

발생하는 비용 (Cost)
배열 복사의 성능 비용	새로운 배열을 만들 때, 기존 데이터를 깊은 복사하는 과정에서 시간 소모 >> 저장된 데이터가 많을수록 많은 시간이 소요
불규칙한 성능 발생 가능	배열이 가득 찬 경우에는, 자동 확장 메커니즘이 우선 실행되기 때문에 속도 지연 >> 성능의 spike
메모리 사용량의 일시적인 증가	깊은 복사가 이뤄지는 동안, 기존 배열과 새로운 배열이 동시에 메모리에 존재

 

4. 노드 (Node)

노드란 두 개 이상의 선 또는 가지가 이어질 수 있는 연결 지점을 의미하며, LinkedList는 데이터 항목을 노드라는 독립적인 객체로 관리한다. 헤드 노드(Head Node)의 자신의 값과 연결 리스트 전체 요소의 개수만 알 수 있을 뿐, 뒤에 오는 요소에 대해서는 알 수 없다. 즉, 연결 리스트의 각 노드에 어떠한 값이 있는지 파악하기 위해서는 반드시 헤드 노드부터 마지막 노드까지 순차적으로 탐색해야 한다. 따라서 연결 리스트의 검색 연산은 최소 O(1), 최대 O(n)의 시간 복잡도를 가진다.

 

[그림 2] 노드

 

5. 연결 리스트의 종류

연결 리스트는 데이터를 불연속적인 메모리에 저장한다. 따라서 ArrayList와 다르게 메모리 이동 없이 데이터 삽입 / 삭제 연산이 가능하다. 다만 다음 요소를 참조하기 위한 추가적인 메모리를 필요로 한다.

	단방향 연결 리스트 (Singly-Linked-List)	양방향 연결 리스트 (Doubly-Linked-List)
정의	요소들 사이를 단방향 포인터로 연결한 자료 구조	요소들 사이를 양방향 포인터로 연결한 자료 구조
순서	유지하지 않음	유지하지 않음
특징	요소의 저장 / 삭제 빈번하면 ArrayList보다 우수	스택, 큐, 양방향 큐 등을 구성하는데 용이

 

	시간복잡도	삽입 연산	삭제 연산
탐색	O(n)	삽입할 위치의 앞 / 뒤 노드 탐색	삭제할 노드 탐색
연결 조정 (Linking)	O(1)	새로운 노드 생성 >> 해당 노드의 참조가 앞 / 뒤 노드를 가리키도록 연결 조정	삭제할 노드의 앞 / 뒤 노드 참조를 서로 연결 >> 삭제 노드를 리스트에서 제외
추가 연산	O(1)	앞 / 뒤 노드의 참조 역시 새로운 노드를 가리키도록 조정	GC에 의해 삭제 노드가 메모리에서 자동으로 해체

 

 

6. 자료 구조 선택

	ArrayList	LInkedList
데이터 접근 패턴	랜덤 접근이 자주 필요한 경우 >> 데이터 조회 결과 캐싱	데이터의 빈번한 추가 / 삭제가 요구되는 경우 >> 쇼핑 카트 데이터 처리
메모리 사용량	데이터 저장에 집중한 최소 메모리 사용	추가적인 노드 참조 메모리 소모

 

---

 

05. Stack과 Queue

1. 스택 (Stack)

스택이란 리스트 계열 클래스인 Vector 클래스를 상속받아 구현된 자료 구조로, 탑(top)에 제일 나중에 들어간 데이터가 가장 먼저 나오는 후입선출(Last  Input First Out, LIFO) 구조로 되어 있다. 대표적으로 각각의 메소드는 호출될 때마다 해당 구조의 메모리에 올라가 역순으로 처리된다. 만약 스택 포인터가 스택의 경계를 넘어선 경우, 스택 오버플로우가 발생한다.

 

스택의 연산 종류
push()	데이터 삽입
pop()	데이터 삭제 및 반환
peek()	최상단 데이터 조회
isEmpty()	스택 빈공간 여부 확인

 

public static void main(String[] args) {
    Stack<Integer> integerStack = new Stack<>();

    integerStack.push(1);
    integerStack.push(2);
    integerStack.push(3);
    integerStack.push(4);
    integerStack.push(5);

    System.out.println(integerStack);

    System.out.println(integerStack.search(5));			// 1 반환

    System.out.println("peek() : " + integerStack.peek());	// 5 출력
    System.out.println(integerStack);
    
    System.out.println("pop() : " + integerStack.pop());
    System.out.println("pop() : " + integerStack.pop());
    System.out.println("pop() : " + integerStack.pop());
    System.out.println("pop() : " + integerStack.pop());
    System.out.println("pop() : " + integerStack.pop());
    System.out.println("pop() : " + integerStack.pop());	// EmptyStackException 발생
    System.out.println(integerStack);
}

 

2. 스택 적용 사례

스택 적용 사례
실행 취소 기능 (Undo)	문서 편집기에서 Ctrl+Z를 눌렀을 때의 작동 방식 >> 마지막으로 수행된 작업을 Stack에 저장하고, 역순으로 복원
브라우저 히스토리 관리	방문한 페이지를 Stack 구조로 관리하며, 뒤로 가기 기능을 제공
기타 활용 사례	재귀 호출 관리 (메소드 호출 스택) / 표현식 평가 (후위 표기법 / 괄호 검사)

 

3. 큐 (Queue)

큐란 스택과 달리 선입선출(First In First Out, FIFO) 구조로, 데이터의 삽입(Front)와 데이터 삭제(Rear)가 각각 다른 곳에서 수행된다.

 

큐의 연산 종류
offer() / add()	데이터 삽입
poll () / remove()	데이터 삭제 및 반환
peek()	가장 앞의 데이터를 조회
isEmpty()	큐의 빈공간 여부 확인

 

public static void main(String[] args) {
    Queue<String> que = new LinkedList<>();
    
    que.offer("first");
    que.offer("second");
    que.offer("third");
    que.offer("fourth");
    que.offer("fifth");

    System.out.println(que);


    System.out.println("peek() : " + que.peek());		// first
    System.out.println("peek() : " + que.peek());		// first

    System.out.println(que);
    
    System.out.println("poll() : " + que.poll());		// first
    System.out.println("poll() : " + que.poll());		// second

    System.out.println(que);
}

 

4. 큐 적용 사례

큐 적용 사례
작업 스케줄링	운영체제나 작업 관리 시스템에서 작업(Job)을 순차적으로 처리할 때 사용 >> 먼저 요청된 작업이 먼저 처리
버퍼 관리	데이터 전송 시 수신되는 데이터를 임시 저장하고, 수신 순서대로 처리할 때 사용 >> 스트리밍 서비스의 미디어 버퍼 / 메시지 큐(Message Queue)를 이용한 비동기 처리 시스템
기타 활용 사례	프린터 작업 관리 / 콜센터의 대기 고객 관리

 

5. 데크 (Deque)

데크란 양쪽 끝에서 데이터 삽입 / 삭제가 가능한 자료 구조로, Stack과 Queue의 기능을 모두 제공한다.

 

주로 웹 브라우저의 앞으로 가기 및 뒤로 가기 기능 구현, 작업 우선순위가 동적으로 변하는 작업 관리 시스템, 대기열 관리가 복잡한 콜센터 또는 서버의 요청 관리 시스템 등에 사용된다.

 

public static void main(String[] args) {

    Deque<Integer> deque = new ArrayDeque<>();

    deque.addFirst(1);     // 앞쪽에 추가
    deque.addLast(2);      // 뒤쪽에 추가
    deque.addFirst(0);     // 다시 앞쪽에 추가

    System.out.println(deque);

    System.out.println("peekFirst() : " + deque.peekFirst());		 // 0
    System.out.println("peekLast() : " + deque.peekLast());  		 // 2

    System.out.println("removeFirst() : " + deque.removeFirst()); 	// 0 제거
    System.out.println("removeLast() : " + deque.removeLast());  	// 2 제거
	
    System.out.println(deque);
}

public static void main(String[] args) {

    Deque<Integer> dequeAsStack = new ArrayDeque<>();

    // Stack처럼 사용 (LIFO)
    dequeAsStack.addLast(1);
    dequeAsStack.addLast(2);
    dequeAsStack.addLast(3);

    System.out.println(dequeAsStack.removeLast()); 		// 3
    System.out.println(dequeAsStack.removeLast()); 		// 2

    Deque<Integer> dequeAsQueue = new ArrayDeque<>();

    // Queue처럼 사용 (FIFO)
    dequeAsQueue.addLast(1);
    dequeAsQueue.addLast(2);
    dequeAsQueue.addLast(3);

    System.out.println(dequeAsQueue.removeFirst()); 		// 1
    System.out.println(dequeAsQueue.removeFirst()); 		// 2
}

 

 

---

 

06. Hash 기반 자료 구조

1. 해시 함수 (Hash Function)

해시 함수란 임의의 입력값(키)를 고정된 크기의 정수(해시값)으로 변환하는 함수를 의미한다. 변환된 해시값은 일반적으로 배열의 인덱스로 활용되며, 빠른 데이터 검색 / 저장 연산을 지원한다.

 

해시 함수의 특징
결정적 (Deterministic)	동일한 입력은 항상 동일한 출력 해시값을 생성함
빠른 계산 속도	해시 값은 계산이 빠르고 효율적이어야 함
균등한 분포	해시 값이 가능한 한 고르게 분포되어야 충돌을 줄일 수 있음

 

해시 함수의 역할 및 목표
빠른 검색 성능 제공	평균적으로 O(1) 시간 복잡도로 데이터 접근 가능
배열 기반 인덱싱 지원	해시값을 배열의 인덱스로 활용하여 접근 속도 향상
키 기반 접근 지원	키(Key)를 이용하여 값(Value)에 직접 접근 가능 >> HashMap 등

 

 

[그림 1] 해시 함수

 

2. 해시 함수의 종류

해시 함수의 종류	키 (Key) 값	특징
나눗셈 방법 (Division Method)	특정 소수(Prime Number)로 나눈 나머지 >> 테이블 크기보다 작되, 가능한 큰 소수	키가 특정 패턴을 가진 경우, 충돌 확률 상승
곱셈 방법 (Multiplication Method)	고정된 실수 A를 곱한 값의 소수점 이하를 배열에 매핑 >> 0 < A < 1 / 배열 크기: m	충돌 안정적 / 구현 복잡
문자열 해시 (Hashing for Strings)	문자열을 문자로 분할하여 특정 가중치(㎡)를 곱해 결합	문자열 키를 숫자로 변환하는 데 효과적 >> DJB2, 롤링 해시 등
비트 연산 기반 해시 (Bitwise Hashing)	비트 이동, XOR, AND 등의 연산을 조합	빠르고 충돌이 적은 해시
보안 해시 함수 (Cryptographic Hash Functions)	충돌 가능성을 극도로 낮춘 암호화 알고리즘 >> SHA-256 등	비밀번호 저장 / 디지털 서명 / 무결성 검사

 

// 1. 나눗셈 방법
hash(k) = k mod p

// 2. 곱셈 방법
hash(k) = floor(m * (k * A mod 1))

// 3. 문자열 해시
hash(s) = s[0] * aⁿ⁻¹ + s[1] * aⁿ⁻² + ... + s[n-1]

 

 

3. 해시 충돌 (Hash Collision / Hash Clash)

해시 충돌이란 서로 다른 두 입력값이 동일한 해시값을 생성하는 상황을 의미한다. 이러한 해시 충돌은 해시 함수가 유한한 크기의 해시값을 생성하므로 필연적으로 발생한다. 또한 해시 충돌을 해결하기 위한 메커니즘을 충돌 해결(Collision Resolution)이라 한다.

[그림 2] 해시 충돌

4. 해시 충돌 해결 방법

	체이닝 (Chaining)	오픈 어드레싱 (Open Addressing)
핵심 개념	충돌 발생 시, 해당 인덱스에 연결 리스트로 데이터 매달기	충돌 발생 시, 다른 빈칸 탐색
저장 위치	버킷 외부의 별도 리스트에 저장	해시 테이블(배열) 내부의 빈 공간 활용
구현 방식	연결 리스트(Linked List) 활용	선형/이차 탐사, 이중 해싱 등
장점	쉬운 구현 / 데이터가 많아져도 유연하게 대응 가능	추가 메모리 공간이 필요 없어 공간 효율이 좋음
단점	외부 노드 생성을 위한 추가 메모리 소요	데이터가 많아질수록 빈칸 찾기가 힘들어져 성능 저하

 

[그림 3] 체이닝 / 오픈 어드레싱

 

5. HashSet과 HashMap

HashSet이란 해시 테이블을 이용하여 데이터를 저장하는 구조이다. Set과 마찬가지로 순서를 보장하지 않되 중복된 값을 허용하지 않는다. 또한 키 값을 이용하여 데이터 접근 / 저장 연산을 수행한다.

 

HashMap이란 Key-Value 쌍으로 데이터를 저장하며, Value 값의 중복은 허용하지만 Key 값은 중복을 허용하지 않는다. 또한 데이터 저장 연산 속도는 느리지만 Hashing이라는 해시 함수를 이용해서 데이터를 저장하기 때문에 빠른 검색 연산 속도를 지원한다.

 

[그림 4] HashSet과 HashMap

 

 

6. HashSet vs HashMap

	HashSet	HashMap
정의	고유한 요소를 저장하는 컬렉션 클래스	키-값 쌍을 저장하는 컬렉션 클래스
데이터 저장 방식	값(value)만 저장	키(key)와 값(value)을 쌍으로 저장
중복 허용	중복 요소를 허용하지 않음	키는 중복 허용되지 않지만, 값은 중복 가능
Null 허용	단 하나의 null 값 허용	하나의 null 키와 여러 개의 null 값 허용
클래스 계층	Collection → Set → HashSet	Map → HashMap
동기화	비동기화됨	비동기화됨
성능	평균적으로 빠름 (O(1))	평균적으로 빠름 (O(1))
내부 구현	내부적으로 HashMap을 사용 (값은 더미 객체로 저장)	자체적으로 해시 테이블 구조 사용
주요 메서드	add(), remove(), contains() 등	put(), get(), remove(), containsKey() 등
사용 목적	고유한 요소들의 집합을 저장할 때 사용	키로 값을 효율적으로 조회/저장할 때 사용
예시	회원 ID, 유일한 태그 목록 등	상품ID → 가격, 사용자ID → 나이 등 매핑 구조

 

7. 해시 자료 구조 활용 최적화

해시 자료 구조 활용 최적화		특징
적절한 초기 용량 설정	내부적으로 배열을 기반으로 데이터를 저장하며, 자동으로 크기를 조절 >> 자동 확장 시, 전체 요소를 재해시하므로 성능 저하 발생	예상 데이터 수 / 부하율
부하율 조절 (load factor)	해시 테이블에서 요소 수 / 배열 크기를 의미하는 비율 >> 해시 테이블의 빈 공간을 측정하고 자동으로 크기를 확장하는 트리거	저장된 요소 수 / 버킷(배열) 수 >> 기본 부하율: 0.75
equals() 및 hashcode()	사용자 정의 객체를 키로 사용할 경우, 반드시 함께 오버라이드해야 함

	낮음 (0.5)	중간 (0.75)	높음 (0.9)
특징	배열이 빨리 가득 참	둘의 절충	많은 요소를 밀도 있게 저장
장점	충돌 적음 → 탐색 빠름	충돌을 억제하면서도 공간도 절약	공간 효율 좋음
단점	메모리 낭비 많음	적당히 빠르고 메모리 효율도 좋음	충돌 많아져 성능 저하