JAVA 대표적 자료구조

이명렬·2024년 1월 26일

Java

목록 보기

1/4

자료구조 (Data Structure)

프로그램 작성간 여러 데이터가 필요.
예): 100명의 학생 성적을 처리할때 각각의 성적 값을 변수에 할당시 100개의 변수필요 이런 경우 배열을 이용시 하나의 변수명으로 100개의 데이터를 처리할 수 있음

배열(Array)

배열은 가장 기본이 되는 자료구조 데이터를 순차적으로 저장해 (0부터 시작하는 인덱스를 통해 접근)

일반적으로 배열을 선언할때 크기가 고정됨

데이터를 순차적으로만 접근할 수 있음 위치를 모를 경우 효율 떨어짐

배열에 들어가는 데이터는 모두 동일한 자료형 이여야함

배열 중간에 값을 추가하려면 기존 데이터를 모두 이동 시켜야함

리스트(List)

배열과 유사한 순차적인 자료구조를 제공. 객체지향 프로그램언어에는 보통 List 자료구조가 기본적으로 제공되며 그렇지 않은 경우 직접 자료구조를 구현하거나 구현된 라이브러리를 사용해야함

데이터 접근을 위해 인덱스를 사용해야 하는 점은 배열과 같으나 배열의 모든 문제점을 해결 하고있음

데이터 크기가 고정되지 않음

데이터를 다루기 위한 여러 방법이 제공됨

리스트의 데이터는 서로 다른 타입일 수 있음 => 일관된 처리가 어려워 보통은 동일하게 처리함

배열 중간에 값을 추가하거나 삭제하기 쉬움

특정 데이터가 포함되어 있는지 확인은 가능하나 검색을 위해선 별도 구현이 필요

LinkedList는 현 데이터에 다음 데이터를 읽을 수 있는 정보를 추가한 것으로 불연속적으로 존재하는 데이터를 서로 연결할 수 있는 방법을 제공함.
Double LinkedList는 이전과 다음 데이터 정보를 모두 가지고 있는 형태이며 Java의 경우 LikedList 클래스가 제공되는 실제론 Double Circular LinkedList (순환구조가 추가 된 Double LinkedList 형태를 구현해 둔것)

List의 종류

ArrayList :
중간 인덱스의 요소를 특정해서 삭제하면 해당 요소보다 뒤에 인덱스를 가진 요소들이 한칸 씩 앞으로 당겨짐

Vector 스레드에 안전한 ArrayList 개념 :
ArrayList와 완전히 똑같이 작동하되 멀티 쓰레드를 통해 동시 호출하는 것이 불가

LinkedList 완전한 자료구조 연결리스트의 개념 링크 체인형태로 객체를 관리 :

먼저 중간 인덱스에서 삭제가 이루어지면

해당 링크(L)와 서로 바라보던 L-1번, L+1번 인덱스의 링크들과 연결을 끊고

-1, +1 번 인덱스가 서로 다시 링크를 연결한다

실질적으로 리스트와 요소 사이의 빈공간 없이 관리되지만. 원래 중간 링크가 가지고있던 인덱스 번호는 비어있게 된다. 이 특징 덕분에 높은 빈도의 삽입, 삭제가 이뤄질때 속도 측면에서 ArrayList보다 유리함

Set

Sset은 저장 순서를 보장하지않고 중복을 허용치 않음. 중복 금지에선 null도 해당됨. 두개 이상의 null값을 저장하지 않음.

Set의 종류

HashSet
객체들을 순서없이 저장하고 hashcode를 통한 중복을 방지함

TreeSet
Comparator 인터페이스를 이용해 삽입되는 값이 비교되며 정렬된 자리로 들어감

SortedSet
구현체가 없고 정렬된 Set을 다루기 위한 메소드들이 들어있는 인터페이스

TreeSet을 선언에 정렬된 리스트를 구성하고

headSet() : 가장 작은 값부터 인자로 넘긴값 직전까지의 요소들을 set으로 리턴함

tailSet() : 가장 큰 값부터 인자로 넘긴값 직전까지의 요소들을 셋으로 리턴함

subSet() : 인자로 넘긴 A와 B사이의 인자들을 셋으로 리턴함. A인자는 포함되고 B인자 직전까지의 요소들만 리턴됨

가장자리 요소의 접근은 first(), last()

맵(Map)

데이터를 Key Value(키,값)의 쌍으로 저장하는 방식. 실제 데이터가 저장되는 형태는 내부구조에 따르며 사용하는 쪽에선 내부구조에 대해 신경쓸 필요가 없는 형태

맵을 사용했을때 얻을 수 있는 가장 큰 장점은 원하는 데이터를 손쉽게 찾을 수 있다는 점

데이터를 저장할 때 해당 데이터를 찾기 위한 key를 부여

key값을 알면 언제든 쉽게 데이터를 찾을 수 있음

value에 객체형 이 들어갈 수 있어 복잡한 데이터 처리가 가능

예) 학생들의 성적을 관리하는 자료구조를 만들때 학생별 성적 List로 만들고 학번을 key로 하는 Map을 만들어 List를 저장하면 학번을 통해 쉽게 조회가능

이터레이터(Iterator)

이터레이터는 서로다른 자료구조(Vector, ArrayList, LinkedList)의 데이터를 동일한 방법으로 다음 데이터에 접근하는 방법을 제공하는 인터페이스로 자바 컬렉션 프레임워크의 일부

컬렉션 프레임워크 (Collection FrameWork)

컬렉션 프레임워크는 자바에서 데이터를 저장하는 클래스들을 표준화한 설계 구조를 말함. 이러한 구조를 바탕으로 자바의 기본 자료구조 클래스들이 구성되어 있으며 체계화되고 일관된 구조를 갖게 됨

Collection, Map, List, Set 인터페이스를 중심으로 다음과 같은 클래스 계층 구조를 형성함

[클래스 계층 구조도 .그림]

인터페이스 설명 특징 대표 구현 클래스
List 순서가 있는 데이터의 집합 데이터의 중복을 허용 ArrayList, LinkedList
Set 순서를 유지하지 않는 데이터의 집합 데이터의 중복을 허용하지 않음 HashSet, LinkedHashSet
Map 키(Key)와 값(Value) 순서유지 X, 키 중복X, 값 중복 O HashMap, LinkedHashMap, Properties

Collection 프레임워크는 크게 Collection 인터페이스와 Map 인터페이스로 나뉨
List 와 Set 인터페이스를 구현한 컬렉션 클래스들은 공통부분이 많기에, 공통된 부분을 모은 Collection 인터페이스로 상속 되어있음
Map 인터페이스 컬렉션들은 두개의 데이터를 묶어 한쌍으로 다루기 때문에
Collection 인터페이스와 따로 분리되어 있다
Collection 인터페이스
List 와 Set의 상위 인터페이스. 즉 List 와 Set를 구현한모든 클래스들은 Collection 인터페이스의 메소드를 사용할 수 있으므로 구현 클래스와 상관없이 동일한 방법으로 데이터를 다룰 수 있음

컬렉션안에 들어가는 데이터들은 모든 타입이 가능하지만 타입이 다른 경우 일관된 처리가 어렵기 때문에 타입 파라미터를 사용
Collection<String> c = new HashSet<>();
순서가 없고 데이터 중복을 허용치 않는 자료구조인 HashSet 객체 생성.

저장되는 데이터는 문자열로 한정

원래는 new HashSet<><String>(); 이지만 타입추론을 통해 생략 가능
컬렉션객체의 생성

모든 컬렉션 클래스들은 Java.util 패키지에 들어있음. 컬렉션 객체를 생성하는 방법은 참조변수 선언시 상위 인터페이스 타입을 사용하고 객체 생성은 필요에 따라 구체적인 클래스들을 사용하는 형식
ArrayList<String> list = new ArrayList<>(); //권장안됨
List<String> list = new ArrayList(); 		//권장됨
컬렉션 객체를 생성하는방법은 다양하며 상황에 따라 적절한방법을 사용.
Collection<String> c1 = new HashSet<>();
Collection<String> c2 = Arrays.asList("three","four");
Collection<String> c3 = Collections.singleton("five");
c1 빈 HashSet 객체를 생성. 데이터는 직접 add() 메소드를 통해 넣어야함

c2 두개의 데이터를 가지는 List객체를 생성

c3 데이터가 하나인 유일한 인스턴스를 보장하는 Set객체를 생성
컬렉션에 데이터 추가,삭제

데이터 추가는 add(), addAll() 메소드를 사용.
지정된 타입의 데이터를 하나씩 추가할땐 add();,
컬렉션 타입을 추가할땐 addAll()을 이용해 개별 원소를 꺼내어 추가하는 형식
c1.add("one");
c1.addAll(c2);
데이터의 삭제는 remove(), removeAll(), retainAll(), clear()등의 메소드를 사용.
retainAll()의경우 인자의 데이터를 제외한 나머지 데이터를모두 삭제 하는 메소드.
clear()는 모든 데이터를 삭제함
c1.remove("one");
c1.remove("c2");
c1.retainAll("four");
c1.clear();
컬렉션 데이터 확인 및 변환

특정 데이터가 컬렉션 안에 존재하는지 혹은 비어 있는지를 확인할 수있으며 크기를 구할 수있습니다
  c1.isEmpty();
  c1.contains("zero");
  c1.containsAll(c2);
컬렉션 데이터의 크기는 size() 메소드를 통해 구할 수 있음
데이터 변환은 toArray() 메소드를 이용해 배열형태로 변경할 수 있음 but Object 타입으로 리턴 되므로 특정 타입을 원할시 해당 객체 생성 코드를 넣어주어야함
int size = c1.size();
Object[] converted1 = c1.toArray();
String[] converted2 = c1.toArray(new String[c1.size()]);
컬렉션 데이터의 사용

컬렉션에 들어있는 데이터를 사용하기 위해선 다소 복잡한 과정을 거쳐야 함
컬렉션 자체는 구체적인 구현이 아니므로 직접적으로 데이터에 접근하는 방법은 포함되어 있지 않음

List나 Set 인터페이스를 이용해 처리하거나 Collection 인터페이스 타입으로 처리하려면 다음의 방법중 하날 사용할 수 있음
A. 배열로 변환하여 for문과 사용
특정 위치의 데이터를 직접 선택할 필요없이 순차적으로 모든 데이터를 사용하는 경우 단순하게 for문만 사용해도 됨
for(String s : c1){
	System.out.println(s);
}
그러나 특정 위치의 데이터를 직접 다루고자 한다면 앞에서 다룬 toArray() 메소드를 이용해 배열로 변환해 사용하는 방법을 사용해야함.
배열 데이터는 인덱스로 접근할 수 있으므로 각각의 데이터를 차례로 접근하거나 특정 위치 데이터를 직접 접근해 사용할 수 있습니다.
String[] converted2 = c1.toArray(new String[c1.size()]);
for(int i=0;i<converted2.length;i++) {
	System.out.println(converted2[i]);
}
B. Iterator를 사용
Iterator는 다음 데이터에 접근하는 방법을 제공하는 인터페이스임.
Collection 인터페이스는 Iterator 인터페이스를 상속받고있음
iterator() 메소드로 iterator 객체를 구할 수 있음

여기선 모두 데이터 출력을 예시로 살펴보고있으나 획득한 데이터를 조작하거나 다른 메소드의 인자로 전달하는 등 필요한 작업에 활용할 수 있음
Iterator iter = c1.iterator();
while(iter.hasNext()) {
	System.out.println(iter.next());
}
C. forEach() 사용
마지막으로 forEach() 메소드를 사용하는 방법
c1.forEach(s -> System.out.println(s));
c1.forEach(System.out::println);

인터페이스	설명	특징	대표 구현 클래스
List	순서가 있는 데이터의 집합	데이터의 중복을 허용	ArrayList, LinkedList
Set	순서를 유지하지 않는 데이터의 집합	데이터의 중복을 허용하지 않음	HashSet, LinkedHashSet
Map	키(Key)와 값(Value)	순서유지 X, 키 중복X, 값 중복 O	HashMap, LinkedHashMap, Properties