자바 자료구조

기본 개념

자료구조란?

데이터를 효율적으로 저장, 검색, 구성, 수정할 수 있도록 관리하는 방법을 말한다. 같은 데이터라도 저장하는 방법에 따라서 사용 시 효율이 달라질 수 있다.

시간복잡도와 공간 복잡도

두 개념 모두 알고리즘의 성능 분석 시 사용하는 개념이다.

시간복잡도
- 정의: 알고리즘의 수행 시간을 평가
- 중요: 수행 시간은 프로그램을 실행하는 환경마다 측정 시간이 다르기 때문에 수행되는 연산을 기준으로 실행 횟수를 평가한다.
공간복잡도:
- 정의: 알고림즘 시 수행 시 사용되는 메모리 양을 평가

표현/표기하는 방식은 여러 가지가 있지만 최악의 경우를 기준으로 평가한다. ⇒ 빅 O 표기법

선형 자료구조

자바에서 제공하는 기본 문법과 컬렉션 프레임워크를 사용하여 설명한다.

정의

데이터가 일렬로 나열되어 있을 뿐 아니라 각 데이터가 앞 뒤로 하나의 요소로만 연결된 구조를 말한다.

종류로는 선형 배열(일반 배열, 배열 리스트, 연결 리스트), 스택, 큐, 덱등이 존재한다.

배열

사용
int[] arr = new int[5];
특징
- 인덱스를 활용한다 ⇒ 특정 연산에서 속도가 빠르다.
- 자료구조의 크기가 고정적이다.
- 순서가 있고 중복을 허용한다.
연산
1. 배열의 첫번째 위치에 추가
2. 인덱스를 통하여 바로 접근할 수 있지만 기존 배열의 요소들을 이동시켜야 한다. 배열의 크기만큼 이동 연산이 수반된다. ⇒ O(N)
3. 배열의 마지막 위치에 추가
4. 인덱스를 통해서 해당 위치로 바로 접근할 수 있기 때문에 상수 시간 안에 연산이 가능하다 ⇒ O(1)
삽입: 삽입의 경우 위치에 따라서 시간 복잡도가 달라진다.

삭제: 삭제 연산도 삽입과 마찬가지이다.

삭제한 인덱스 위치를 기준으로 요소 이동 연산이 수반된다 ⇒ O(N)

조회: 

인덱스로 바로 접근을 할 수 있기 때문에 상수 시간에 연산이 가능하다 ⇒ O(1)

검색:  

선형 탐색(찾을 때까지 순회)을 통해서 접근해야 하기 때문에 최악의 경우 배열의 크기만큼 걸린다.  ⇒ O(N)

단점
- 자료구조의 크기가 고정이기 때문에 가득 차면 새로 배열을 생성해서 재할당을 해줘야 하는 문제가 발생한다. 이 문제를 해결하기 위해서 배열의 사이즈를 크게 설정한다면 메모리 공간을 많이 차지하는 문제가 발생한다.
- 삽입, 삭제, 검색의 연산의 시간 복잡도가 O(N) 으로 오래 걸린다.

배열 리스트

자바에서는 ArrayList 컬렉션 객체를 배열 리스트로서 제공한다.

사용
List<Object> container = new ArrayList<>();
특징
- 순서가 있고 중복을 허용한다.
- 크기가 동적으로 변한다. 자료구조의 크기는 1씩 증가하는 것이 아니라 이전 크기를 기준으로 몇 배로 증가한다. (이는 자바 버전마다 다를 수 있다. 제가 알고 있기로는 50%씩 증가하는 것으로 알고 있다.)
- 내부 구현에서 배열을 활용한다.
연산
삽입 시 데이터 이동이 필수적으로 발생하므로 최악의 경우 O(N)이 소모된다.삭제 시 데이터 이동이 필수적으로 발생하므로 최악의 경우 O(N)이 소모된다.특정 위치(인덱스)의 값을 조회시 시간복잡도는 O(1) 갖는다.선형 탐색을 통해서 데이터를 찾는다. ⇒ O(N)
검색: 배열의 문제점
조회: 배열의 장점
삭제: 내부 구현이 배열로 되어 있기 때문에 배열의 문제가 그대로 나타난다.
삽입: 내부 구현이 배열로 되어 있기 때문에 배열의 문제가 그대로 나타난다.
단점
- 동적 배열이라고 하더라도 실제 데이터의 공간보다 크게 확보해야 한다. ⇒ 낭비되는 메모리가 있다.
- 내부 구현으로 배열을 활용하기 때문에 삽입, 삭제, 검색 연산이 오래 걸린다. ⇒ O(N)

연결 리스트(Linked List)

자바에서는 LinkedList 컬렉션 객체로 연결 리스트를 제공한다.

사용
List<Object> container = new LinkedList<Object>();
특징
- 내부 구현이 배열이 아닌 노드 객체로 이루어진다. 노드는 데이터와 다음 노드의 참조값을 구성된다.(단일 연결 리스트 경우)
- 순서가 있고 중복을 허용한다.
- 데이터의 사이즈 만큼 공간을 할당된다.(낭비되는 공간이 없다.)
연산노드 객체를 생성하고 참조값을 갱신하면 되므로 O(1) 로 빠른 연산이다. 하지만, 삽입을 위해서 검색 과정이 필요하기 때문에 최악의 경우 O(N) 시간복잡도를 갖는다.뒤 쪽에 데이터 삽입: O(N)해당 노드 객체에 대하여 이전 노드 객체의 참조값을 다음 노드 객체를 가리키게 하면 되므로 O(1)로 빠른 연산이다. 하지만, 이 역시 삭제를 위해서 검색 과정이 필요하기 때문에 최악의 경우 O(N) 시간복잡도를 갖는다.뒤 쪽에 데이터 삭제: O(N)연결 리스트에는 인덱스라고 없기 때문에 특정 위치에 대한 조회는 검색 연산으로 이어진다.순차적으로 탐색해야 하므로 최악의 경우 O(N) 시간 복잡도를 갖는다.
검색
조회
앞 쪽에 데이터 삭제: O(1)
삭제
앞 쪽에 데이터 삽입: O(1)
삽입:

배열 리스트 VS 연결 리스트

자바의 ArrayList , LinkedList 를 비교한다.

ArrayList 특징

기본 CAPACITY 는 10이다. CAPACITY 를 넘어간다면 50% 씩 증가한다.
메모리 고속 복사 연산을 사용한다.
- for-loop 와 같이 하나씩 데이터를 복사하는 것이 아니라 메모리 블럭을 통째로 복사한다. System.arraycopy() 메서드는 자바 언어 수준이 아닌, 운영체제 및 하드웨어에 밀접한 네이티브코드(C/C++, 어셈블리 코드)로 구현되어 있다.

LinkedList 특징

이중 연결 리스트 구조라서 이전 노드를 참조할 수 있다.

비교

중간 삽입/삭제 연산의 LinkedList 가 ArrayList 보다 빨라 보이지만 실제로 그렇지 않다. 왜냐하면, 연산 자체 속도뿐만 아니라 메모리 접근, 할당, 해제 그리고 CPU 캐시 활용 등 다양한 요소에 의해 영향을 받을 수 있다.
ArrayList 의 경우 내부 구현이 배열로 되어 있다 보니 메모리에 연속적으로 배치되어 있어 메모리 접근 속도가 빠르고 CPU 캐시 활용도가 높다.
LinkedList 의 경우 노드 객체로 이루어져 있기 때문에 메모리 접근 속도가 느리고 캐시 활용도가 떨어진다.

⇒ 따라서, 실무에서는 ArrayList 를 주로 활용한다.

Stack

사용
Stack<Object> container = new Stack<>();
특징
- LIFO(후입 선출): 나중에 입력한 데이터가 먼저 출력되는 구조이다.
- 중복을 허용하고, 입력 순서가 보장된다.
연산
- push: 데이터 삽입 ⇒ O(1)
- peek: 데이터 조회(끝에 데이터만 조회할 수 있다.) ⇒ O(1)
- pop: 데이터 반환과 동시에 제거 ⇒ O(1)
주의할 점
- Vector 의 메서드를 그대로 호출할 수 있는데 Stack 의 연산과 먼 기능을 제공한다.
- Vector 의 메서드들이 synchronized (여러 쓰레드의 동시성 문제를 해결하기 위함) 설정이 되어 있기 때문에 싱글 쓰레드에서 사용하면 성능에 문제가 된다.
- ⇒ Deque 을 사용한다.
Stack 의 내부 구현이 Vector 을 상속하는 구조이기 때문에 사용하지 않는 것을 추천한다.

Queue

사용
Queue<Object> container = new ArrayDeque<>() 혹은 new LinkedList<>();
특징
- FIFO(선입 선출): 먼저 입력된 데이터가 먼저 출력되는 구조이다.
- 중복을 허용하고, 입력 순서가 보장된다.
연산
- offer: 데이터를 삽입한다.
- poll 데이터를 조회와 동시에 꺼낸다.(제거한다.)
- peek: 데이터를 꺼내지 않고 조회만 한다.
구현체두 구현체를 비교하면 ArrayDeque 이 더 빠르다. 왜냐하면, ArrayDeque 은 내부 구현이 배열로 되어 있고 LinkedList 는 노드 객체로 이루어져 있기 때문이다.
Queue 의 구현체로 ArrayDeque , LinkedList 를 제공한다.

Deque

사용
Deque<Object> container = new ArrayDeque<>() 혹은 new LinkedList<>();
특징
- 데이터를 앞, 뒤 모두 삽입 하고 삭제 할 수 있다. → LIFO, FIFO 특징을 모두 갖고 있다.
- 중복을 허용하고, 입력 순서를 보장한다.
연산
- offerFirst , offerLast
- pollFirst, pollLast
- peek

비선형 자료구조

해시

사용 이유

List 자료구조에서 검색 연산은 최악의 경우 O(N) 시간 복잡도를 갖는다. 단순 조회 연산의 경우 시간 복잡도는 인덱스를 통해 O(1)를 갖지만 검색 연산의 경우 그렇지 못하다. 인덱스는 위치를 기반으로 한 값이기 때문에 특정 위치 조회는 빠르게(O(1)) 된다. 이 아이디어를 바탕으로 인덱스가 위치가 아닌 값을 기반으로 이루어진다면 검색 연산도 빠르게 할 수 있지 않을까라는 생각에서 해시 라는 개념을 사용한다.

정의

해시, 곧 해시 함수는 가변 길이 데이터를 고정 길이 데이터로 변환할 때 사용하는 함수, 연산이다.

해시를 통한 검색 연산 최적화

데이터 값이 곧 인덱스 상황을 가정해보자. 그렇다면 메모리 낭비가 심할 것이다.

데이터가 1, 5000, 200000 이 있다면 배열의 크기는 최소 20만이어야 한다.

따라서, 특정 값의 해시 값을 인덱스로 활용한다면 메모리 낭비 문제를 해결할 수 있다.

해시 함수는 기본적으로 나머지 연산을 활용한다.

해시 충돌

해시 함수를 이용한다면 해시 충돌이 발생할 수 밖에 없다. 해시 충돌은 다른 데이터 값에 대하여 동일한 해시 값을 갖는 것을 의미한다.

해시 충돌의 해결은 인덱스에 해당하는 부분이 값이 아닌 자료구조를 참조한다면(ex: 리스트) 가능하다.

Set

자바에서는 Set 컬렉션 객체를 정리하기 앞서 기본적인 Set 자료구조에 대해 설명한다.

특징
- 순서가 없고 중복을 허용하지 않는다.
자바에서의 해시 인덱스를 구하는 방법Object 클래스에 정의되어 있는 hashcode를 들여다 보면 객체의 메모리 주소를 정수로 변환하여 반환하는 네이티브(native) 메서드(다른 언어로 구현됨) 이다.
데이터가 숫자라면 해시 함수를 직접 구성하는데 어려움이 없지만 데이터가 숫자가 아닌 다른 타입이라면 해시 함수를 직접 구현하는 것은 어려움이 있다. 따라서, 자바에서는 hashcode 메서드가 Object 클래스에 정의되어 있기 때문에 이를 이용하여 구현하면 된다.
해시 충돌⇒ 따라서, 객체를 저장하는 경우 오버라이딩은 필수이고 IDE 에서 제공하는 방법을 활용하면 쉽게 구현할 수 있다.
해시 충돌을 해결하기 위하여 인덱스 위치에 리스트가 구현되어 있다면 객체를 저장하는 경우 hashcode 와 equals 메서드를 오버라이딩 하지 않으면 문제가 생길 수 있다. Object 클래스에 구현된 hashcode 와 equals 는 메모리 주소를 기반으로 구현된다. 만약, 논리상 같아야 하는 객체의 경우 이 두 메서드를 오버라이딩 하지 않는다면 다른 것으로 연산되고 따라서 중복 저장되거나 저장되어 있지만 찾지 못하는 문제가 발생할 수 있다.

Map

특징
- 키-값 쌍을 이룬다.
- 키(Key)는 중복을 허용하지 않고 값(Value)는 중복을 허용한다.
- 순서를 보장하지 않는다.
구현배열 인덱스 위치에는 Node<K, V> 가 저장이 된다.
내부 인터페이스인 Entry (키-값 쌍을 가짐) 객체로 이루어진다.
자바의 구현체의 차이LinkedHashMap: 삽입 순서 보장, 연산(삽입, 삭제, 검색)의 시간복잡도 O(1)
TreeMap: 정렬, 연산(삽입, 삭제, 검색)의 시간복잡도O(logN)
HashMap: 순서 보장 X, 연산(삽입, 삭제, 검색)의 시간복잡도 O(1)

HashMap

사용
Map<Object, Object> containerMap = new HashMap<>();
특징
- 노드 배열로 이루어진다. 각 인덱스에 해당하는 값은 연결 리스트인 것이다.
- 해시 인덱스의 결정은 hashcode 의 결과를 내부 해시 함수의 입력으로 삼아 나온 결과를 사용한다.
- 해시 인덱스가 겹치면 해당 인덱스의 연결 리스트에 끝에 붙인다.
- 저장된 해시 인덱스가 배열의 75% 를 차지한다면 재해싱이 발생한다.
- 노드 연결 리스트에서는 equals 메서드를 통해 비교한다.

HashSet

사용
Set<Object> container = new HashSet<>();
특징
- 중복을 허용하지 않고 순서를 보장하지 않는다. (넣는 순서도, 정렬 순서도 없음)
- 내부 구현은 HashMap 으로 되어 있다.
- HashMap 의 키가 저장할 데이터이고 값은 HashSet 에서 정의하고 있는 Enum 값(PRESENT)을 활용한다.
연산
모든 연산이 O(1) 의 시간 복잡도를 갖는다. 물론 해시 충돌이 발생한다면 시간이 더 걸릴 수 있다.

LinkedHashSet

사용
Set<Object> container = new LinkedHashSet<>();
특징
- 중복을 허용하지 않지만 삽입 순서를 보장한다.
- 내부 구현 LinkedHashMap 으로 이루어진다.
- HashSet 보다 차지하는 메모리가 더 크다.

TreeSet

사용
Set<Object> container = new TreeSet<>();
특징
- 정렬 기준을 설정할 수 있다.
- 내부 구현은 TreeMap으로 되어 있다.
- 이진 탐색 트리를 보완한 레드-블랙 트리를 활용한다. (이진 탐색 트리의 경우 최악의 경우 리스트와 같은 형태를 가져 리스트의 연산의 시간 복잡도를 따라간다. 따라서, 이를 보완하기 위한 방법인 레드-블랙 트리를 사용한다.)
연산
- 모든 연산이 O(logN) 시간 복잡도를 가진다.

자바의 Set 비교

특수한 경우가 아니라면 연산의 시간복잡도가 O(1) 인 HashSet 을 주로 활용한다.

순회, 정렬 등

순회

자바의 자료구조들은 Iterable, Iterator 인터페이스를 제공한다.

이유
자바의 자료구조들는 순회를 하는 방식이 다르다. 배열의 경우 인덱스를 활용하고 노드로 이루어진 경우 다음 노드를 가리키는 참조변수를 활용한다. 그렇다면, 순회를 하기 위해서는 모든 자료구조의 구현을 정확히 알고 있어야 하는 문제가 존재한다. 따라서, 자바는 Iterable ,Iterator 인터페이스를 제공하고 자바의 자료구조들은 해당 인터페이스를 구현 혹은 상속하고 있다.
분석Iterable 인터페이스는 Iterator 를 반환하는 메서드를 제공하고 Iterator 는 다음 요소가 있는지를 확인하는 hasNext 와 다음 노드를 반환하는 next 메서드를 제공한다.
예를 들어, ArrayList 에 대해서 Iterable 을 구현하고 있고 ListItr 는 Iterator 를 구현하고 있따.
interface Iterable<T>{ Iterator<T> iterator(); } interface Iterator<E>{ boolean hasNext(); E next(); }
Iterator 를 활용한 향상된 for 문
```
 List<String> container = new ArrayList<>();
 for(String str: container){
 }
```
컴파일 이후 해당 코드는 아래 코드로 변경된다.
while(iterator.hasNext()){ String value = iterator.next(); }
자료구조가 Iteratable 을 상속하고 있기 때문에 다음과 같은 for 문이 가능해진다.
반복자 패턴
Iterator(반복자) 디자인 패턴은 컬렉션의 내부 구조를 노출하지 않으면서 순회를 가능하게 하는 디자인 패턴이다.

정렬

자바에서는 Comparable, Comparator 두 인터페이스를 제공하여 정렬 기능을 제공한다.

여기서 중요한 부분은 각 인터페이스에서 제공하는 메서드를 정의할 때 반환 값에 대한 이해하는 것이다.

반환 값

양수 ⇒ 앞의 값이 뒤의 값보다 크므로 뒤로 가야 한다.

0 ⇒ 동일

음수 ⇒ 앞의 값이 뒤의 값보다 작으므로 순서를 유지한다.

String 클래스 (0)	2024.09.09
Scanner VS BufferedReader (0)	2024.09.06