Java로 구현하는 자료구조

Java로 구현하는 자료구조

2025. 3. 6. 11:22ㆍBackend/자료구조&알고리즘

0. 자료구조란?

0-1. 자료구조의 정의

자료구조란 데이터를 효율적으로 저장하고 관리하기 위한 방법과 규칙을 의미한다.
- 일련의 자료들을 조직하고 구조화하는 것
- 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법
- 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법등을 연구 분석하는 것
효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다.

0-2. 자료구조의 분류

원시형/비원시형
- 원시형: 기본형, 내장형 자료구조
- 비원시형: 원시형을 묶어서 만든 자료구조
선형/비선형 구조

	선형구조	비선형구조
데이터 저장 구조	순차적	계층적, 비순차적
데이터간 관계	명확, 데이터가 메모리 상에 연속적으로 저장되거나 포인터로 연결	복잡, 특정키를 통해 데이터를 검색하거나 계층 구조를 표현할 때 사용
예시	배열, 리스트, 스택, 큐, 데크	트리, 그래프

1. 배열 (Array)

1-1. 개념

같은 타입을 여러 변수를 하나의 묶음으로 다루는 것
동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
메모리에서 물리적으로 연달아서 저장된다
사용한 첨자의 개수에 따라 n차원 배열이라 부른다.
장점
- 접근 속도가 빠름. 반복적인 처리 작업에 적합.
- 첨자(index)를 이용하여 데이터에 바로 접근하므로 요소마다 동일한 이름의 변수를 사용하여 처리가 간편하다.
단점
- 정적인 자료구조로 기억장소를 고정하므로 생성 이후 추가가 어렵다 (가변성이 없음)
- 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생한다.

1-2. 자바에서 사용

int[] arr;                            //선언 (배열을 다루기 위한 참조변수 선언)
int[] arr = new int[5];               //선언+생성 (실제 저장공간을 생성)
int[] arr2 = new int[5] {1,2,3,4,5};  //선언+생성+초기화 (배열 생성할 때만 가능)
int[] arr3 = {1,2,3,4,5};             //생략가능

int[0] = 10;    //값 넣기 
int a = int[0]; //값 가져오기 

//향상된 for문
for(int i : arr) {..}

2. 리스트 (List)

2-1. 개념

순서가 있는 데이터의 집합으로, 인덱스나 포인터로 접근할 수 있는 자료구조
자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킴
장점
- 연결리스트는 노드의 삽입과 삭제 작업이 용이하다
- 메모리를 효율적으로 사용 가능
단점
- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
- 연결을 위한 링크(포인터)부분이 필요하기 때문에 순차리스트에 비해 기억공간을 많이 차지한다.

2-2. 자바에서 사용

1) List 인터페이스

List 컬렉션은 객체를 일렬로 늘어놓은 구조로 이루어져 있다.
순서가 있는 데이터의 집합으로 같은 데이터의 중복 저장을 허용한다.
List 컬렉션 인터페이스에는 객체를 추가(add), 검색(contain, get, size), 삭제(remove, clear) 기능의 메서드가 선언되어 있다. 그러므로 List 컬렉션 인터페이스를 상속해서 구현하는 클래스는 해당 기능을 오버라이드 해야한다.
구현한 클래스: ArrayList, LinkedList, Vector, Stack, Queue..

2) ArrayList

ArrayList는 인스턴스를 생성하게 되면 내부적으로 10칸짜리 배열을 생성해서 관리한다.
일반 배열과 ArrayList는 인덱스로 객체를 관리하는 공통점이 있지만, 크기를 동적으로 늘릴 수 있는 차이가 있다.
배열의 단점을 보완하기 위해 만들어졌기 때문에 크기 변경, 요소 추가/삭제/정렬 기능들을 메소드로 제공하고 있다. 단, 기능적으로 수행되는 것이지 속도가 빨라지는 것은 아니다.
ArrayList 장점: 인덱스가 있으므로 객체 검색, 맨 마지막에 객체 추가 등에서 좋은 성능을 발휘한다.
ArrayList 단점: 객체 삭제와 삽입이 빈번하게 일어나는 곳에서 ArrayList보다 LinkedList를 사용하는 것이 좋다.
(배열처럼 ArrayList에서 특정 인덱스의 객체를 제거하게 되면, 제거한 객체의 인덱스부터 마지막 인덱스까지 모두 앞으로 1칸씩 앞으로 이동함

3) LinkedList

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 저장되는 데이터들이 연속된 공간에 저장되는 것이 아니라 각 데이터를 링크(Link)를 연결하여 구성한다.
스택, 큐, 양방향 큐 등을 구성하기 용이하다.
장점: 데이터의 삽입, 삭제가 빈번할 경우 연결되는 링크 정보만 수정하면 되기 때문에 ArrayList보다 더 적합하다.
(특정 인덱스의 객체를 제거하게 되면, 제거되는 인덱스의 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. ArrayList는 제거되는 인덱스를 기준으로 뒤에 있는 객체가 한칸씩 이동 했었던 점과 차이가 있다.)
LinkecdList의 종류
- 단일 연결 리스트: 저장한 요소가 순서를 유지하지 않고 저장되지만 이러한 요소들 사이를 링크로 연결하여 구성하며 마치 연결된 리스트 형태인 것 처럼 만든 자료구조이다. 요소의 저장과 삭제 시 다음 요소를 가리키는 참조 링크만 변경하면 되기 때문에 요소의 저장과 삭제가 빈번히 일어나는 경우 ArrayList보다 성능면에서 우수하다.
- 이중 연결 리스트: 단일 연결 리스트는 다음 요소만 링크하는 반면 이중 연결 리스트는 이전 요소도 링크하여 이전 요소로 접근하기 쉽게 고안된 자료구조 이다.

public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();
        //다형성 적용하여 선언 가능
        List list = new ArrayList();
        Collection clist = new ArrayList();

        //1. add(): 요소 추가 
        arrayList.add("apple");
        //arrayList.add(123); //제네릭 에러
        linkedList.add("apple");

        //원하는 인덱스에 값 추가도 가능
        arrayList.add(1, "banana");
        linkedList.add(1, "banana");

        //2. toString() 메소드가 오버라이딩 되어 있음
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + arrayList);

        //3. get(): 인덱스에 해당하는 값을 가져옴
        System.out.println(arrayList.get(0));
        System.out.println(linkedList.get(1));

        //4. size(): 저장된 요소의 개수 확인
        System.out.println(arrayList.size());
        System.out.println(linkedList.size());

        //5. remove(): 요소를 제거, 제거된 요소 인덱스 리턴
        linkedList.remove(0); //인덱스로 가능
        arrayList.remove("apple"); //값으로 가능
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + linkedList);

        //6. set(): 요소 수정
        arrayList.set(0, "fineapple");
        linkedList.set(0, "fineapple");
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + linkedList);

        //7. clear(): 리스트 내 요소를 모두 제거
        arrayList.clear();
        //linkedList.clear();

        //8. isEmpty(): list가 비어있는지를 확인
        System.out.println(arrayList.isEmpty()); //true
        System.out.println(linkedList.isEmpty()); //false

        //9. 향상된 for문 사용도 가능하다
        for(String a : arrayList) System.out.println(a);
        for(String s : linkedList) System.out.println(s);
    }

리스트 생성 시 변수 타입 선택에 따른 차이점 (다형성)

LinkedList<String> linkedList = new LinkedList<>();	List<String> linkedList = new LinkedList<>();
LinkedList 고유 메서드 사용 가능 addFirst(), removeLast() ..	List 인터페이스의 메서드만 사용 가능 add(), remove() ..
단, LinkedList 전용이므로 다른 구현체로 바꾸기 어려움	ArrayList 등 다른 List 구현체로 쉽게 변경 가능한 유연한 코드

3. 스택

3-1. 개념

한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
LIFO(Last In First Out) 방식으로 자료를 처리한다.
메소드가 호출될 때 해당 구조로 메모리에 올라가게 된다.
Top/Bottom
- Top: 스택의 할당된 기억공간에서 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
- Bottom: 스택의 가장 밑바닥
오버플로/언더플로
- 오버플로(Overflow): 스택의 모든 기억공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 발생
- 언더플로(Underflow): 더이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 발생

3-2. 자바에서 사용

리스트 계열 클래스인 Vector 클래스를 상속받아 구현됨
하지만 Java에서 Stack이 Vector를 상속한 것은 설계적으로 최선은 아니라고 평가받는다.
Vector는 동기화를 지원하는 옛날 List 구현체라서, 성능상 불필요한 오버헤드가 발생할 수 있기 때문에 요즘은 Deque(특히 ArrayDeque)을 사용해서 Stack을 구현하는 게 더 추천된다.

import java.util.Stack; //import
Stack<Element> stack = new Stack<>(); //int형 스택 선언

stack.push(값);    // 값 추가
stack.pop();       // stack의 첫번째 값을 반환하고 제거, 비어있다면 null
stack.peek();      // stack의 가장 상단의 값 반환만하고 제거X
stack.clear();     // stack의 전체 값 제거 (초기화)

stack.size();      // stack의 크기 출력
stack.empty();     // stack이 비어있는지 check (비어있다면 true)
stack.contains(1)  // stack에 1이 있는지 check (있다면 true)

4. 큐 (Queue)

4-1. 개념

큐는 Front 포인터와 Rear 포인터를 정하고 한 곳에는 삭제만, 다른 한 곳에서는 삽입 연산만 처리한다.
FIFO(First In First Out) 방식으로 자료를 처리한다 .

4-2. 자바에서 사용

Queue 인터페이스를 상속받는 하위 인터페이스 들은 Deque, BlockingQueue, BlockingDeque, TreansferQueue 등 다양하지만 대부분의 큐는 LinkedList를 이용한다.
LinkedList는 List와 Queue 둘 다 지원하는 클래스.
- LinkedList는 내부적으로 연결 리스트(Linked List) 구조를 사용해서 요소를 저장
- List 인터페이스를 구현해서 get(index), add(index, element) 같은 인덱스 기반 접근이 가능
- Queue 인터페이스도 구현해서 offer(), poll(), peek() 같은 FIFO 방식 접근이 가능하다.
Priority Queue
- 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함
- 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Element> queue = new LinkedList<>() //큐 선언

queue.offer(값);  // 값 추가
queue.poll();     // queue에 첫번째 값을 반환하고 제거, 비어있다면 null
queue.peek();     // queue의 첫번째 값 반환만하고 제거X
queue.clear();    // queue 초기화

queue.size();     // queue의 크기 출력
queue.isEmpty();  // queue가 비어있는지 check (비어있다면 true)

//우선순위큐 
PriorityQueue<Integer> queSmall = new PriorityQueue<>(); //작은 수가 우선
PriorityQueue<Integer> queBig = new PriorityQueue<>(Collections.reverseOrder()); //큰 수가 우선 
queBig.offer(1);
queBig.offer(9);
queBig.offer(7);
System.out.println(queBig.poll()); //9
System.out.println(queBig.poll()); //7
System.out.println(queBig.poll()); //3

add()와 offer()의 차이 ▼

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

5. 데크 (Deque)

양쪽 끝에서 삽입과 삭제 작업이 가능하도록 구성한 자료구조
스택과 큐를 혼합시킨 형태
두 개의 bottom포인터가 존재한다. (L-bottom, R-bottom)
종류: 입력 제한 데크(스크롤), 출력 제한 데크 (쉘프)

<비선형구조>

그래프 : 엉망진창 리스트

트리: 그래프 + 형태 상의 규칙

힙: 그래프 + 내용 상의 규칙

6. 그래프 (Graph)

정점(Vertex)와 간선(Edge)들로 이루어진 자료구조
트리와 달리 루트 노드 개념이 없으며 정점 간의 부모 자식관계가 없다.
그래프의 간선은 방향성을 가지거나, 가지지 않을 수 있다. (방향/무방향 그래프)
그래프는 자기 자신을 잇는 간선을 가질 수 있다.
구현: 인접행렬, 인접리스트
종류: 방향/무방향 그래프, 다중/단순 그래프, 가중치 그래프, 이분 그래프, 희소/밀집 그래프, 완전/부분 그래프

7. 트리 (Tree)

7-1. 개념

정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 "사이클을 이루지 않도록 구성한" 그래프의 특수한 형태
트리는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합
종류: 이진트리, 이진탐색트리

7-2. 용어

노드: 하나의 기억공간, 링크: 노드와 노드를 연결하는 선
루트노드: 트리 맨 위에 있는 노드, 단말노드: 자식이 하나도 없는 노드
부모, 자식, 형제 노드
차수: 각 노드에서 뻗어나온 가지의 수 (트리의 차수는 노드들의 차수 중 가장 많은 수)
깊이: 트리의 최대 레벨

7-3. 종류

이진 트리: 모든 노드들의 자식 노드가 두 개 이하인 트리, 배열이나 연결리스트로 구현 가능
이진 탐색 트리
- 이진 트리이면서, 중복 값을 갖는 노드가 없는 트리.
- 데이터의 삽입, 삭제, 탑색들리 자주 발생하는 경우에 효율적인 구조이다.

8. 힙 (Heap)

완전 이진 트리 형태로 구성된 비선형 자료구조
주로 우선순위 큐(priority queue)를 구현하는 데 사용된다.
특성: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작다.
- 최대 힙(Max Heap): 부모 노드가 자식 노드보다 값이 크거나 같은 구조 (최대값이 루트에 위치).
- 최소 힙(Min Heap): 부모 노드가 자식 노드보다 값이 작거나 같은 구조 (최소값이 루트에 위치).
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
힙의 주요 연산은 삽입(Insert)과 삭제(Delete)이며, 둘 다 O(log n)의 시간 복잡도를 가진다.

9. 셋 (Set)

9-1. 개념

Set이란 집합처럼 중복되지 않는 데이터를 저장하는 자료구조
데이터 저장 순서가 보장되지 않는다.
Set 사용 사례
- 유일한 값을 저장하고 싶을 때
- 중복 데이터 제거가 필요할 때

9-2. 자바에서 사용

HashSet: 해시 테이블을 이용하여 데이터를 저장하는 구조, 중복X 순서X
LinkedHashSet: HashSet과 동일한 구조를 가지지만 데이터 삽입 순서대로 출력된다.
TreeSet: 데이터가 정렬된 상태로 저장되는 이진 검색 트리의 형태로 요소를 저장한다.

//HashSet (순서 보장X)
HashSet<Integer> set = new HashSet<Integer>(); 

set.add(1);    //값 추가
set.remove(1); //값 1 제거
set.clear();   //모든 값 제거
set.contains(1); //boolean 리턴 

//출력	
Iterator iter = set.iterator();	// Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
    System.out.println(iter.next()); //순서 보장되지 않음 
}

//LinkedHashSet: 등록 순서대로 저장 
LinkedHashSet<String> lhset = new LinkedHashSet<>();
lhset.add("banana");
lhset.add("orange");
lhset.add("apple");
System.out.println("lhset : " + lhset); //banana, orange, apple 

//TreeSet : 자동 오름차순 정렬
TreeSet<String> tset = new TreeSet<>();
tset.add("banana");
tset.add("orange");
tset.add("apple");
System.out.println("tset : " + tset); //apple, banana, orange

10. 맵 (Map)

10-1. 개념

Map은 키와 값을 하나의 쌍으로 저장하는 자료구조
- 키(Key) : 키를 통해 값에 접근할 수 있다, 키는 고유한 값으로 중복 불가
- 값(Value) : 값에 매핑된 데이터, 값은 중복될 수 있다.
데이터 저장 순서가 보장되지 않는다.
장점: 엑세스가 빠르면서(배열), 추가 삭제가 편함(리스트)
단점: 메모리를 많이쓴다 (배보타 배꼽이 커질수있다)
사용사례
- 데이터의 매핑 관계를 표현할 때 (예: 학생 ID와 이름).
- 빠른 검색, 삽입, 삭제가 필요한 경우.
Map과 Set의 차이점 요약

	Map	Set
데이터 구조	키-값(Key-Value) 쌍	고유한 요소의 집합
중복 허용 여부	키는 중복 불가, 값은 중복 가능	중복 요소 불가
주요 사용 목적	키로 값에 빠르게 접근	중복 제거 및 고유 값 관리
주요 구현체	HashMap, TreeMap, LinkedHashMap	HashSet, TreeSet, LinkedHashSet

10-2. 자바에서 사용

Map은 Collection 인터페이스와는 다른 저장 방식을 가지고 있기 때문에 하위 인터페이스에 포함되지 않는다.
- Collection은 단일 값을 저장하는 자료 구조이고, Map은 키-값의 쌍을 저장하는 자료구조 이다.
- 따라서 Map은 Collection의 하위 클래스가 아니고 독립적인 구조로 존재
종류: HashMap, HashTable(-Properties), TreeMap 등
HashMap
- Map 인터페이스를 구현하고 있는 클래스 중에 가장 자주 쓰이는 클래스
- 저장은 느리지만 Hashing 이라는 해시 함수를 이용해서 데이터를 해시 테이블에 저장하기 때문에 검색 측면에서 뛰어나다.
- 중복된 키 값에 값을 저장하면 기존의 값에 새로운 값이 덮어 씌어진다.

HashMap<Integer,String> map = new HashMap<>();   //HashMap 선언 및 생성
map.put(1,"사과");   //값 추가
map.put(1,"바나나"); //키 중복 저장 안됨 -> 값 갱신 
map.put(2,"바나나"); //값 중복 저장 가능  
map.get(1);          //key값 1의 value얻기 : 바나나 
map.remove(1);       //key값 1 제거
map.clear();         //모든 값 제거

map.size();                  //개수 리턴 
map.containsKey(1)           //key값 1 검색 -> true
map.containsValue("바나나");  //value값 "바나나" 검색 -> false

//getOrDefault(map에서 찾을 key값(있으면 key값의 value 리턴), map에 해당하는 key값이 없으면 리턴할 디폴트값);
map.getOrDefault(1, "없음");  // map의 key값으로 1이 있으면 "사과" 리턴, 없으면 "없음" 리턴   
 
// map 출력
for (String key : map.keySet()) {
        String value = map.get(key);
        System.out.println("[key]:" + key + ", [value]:" + value);
}

//keySet()을 이용해서 키만 따로 set으로 만들고,
Iterator<String> keyIter = map.keySet().iterator();

while(keyIter.hasNext()) {
    String key = (String)keyIter.next();
    String value = (String) hmap2.get(key);
    System.out.println(key + " = " + value);
}

저작자표시 (새창열림)

알고리즘 효율 분석 | 시간 복잡도, 빅오 표기법 2025.03.12

Archive