📚Computer Science/Data structure

TreeMap이란? TreeMap은 이진트리를 기반으로 한 Map 컬렉션이다. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면, TreeMap은 키와 값이 저장된 Map, Entry를 저장한다는 점이다. TreeMap에 객체를 저장하면 자동 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 타입이 숫자일 경우 값으로, 문자열일 경우 유니코드로 정렬한다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키값이 낮은 것은 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다. TreeMap은 일반적으로 Map으로써 성능이 HashMap보다 떨어진다. TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 Has..

HashMap 이란? HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. Map은 키와 값으로 구성된 Entry 객체를 저장하는 구조를 가지고 있는 자료구조이고 여기서 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. HashMap은 이름 그대로 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다. HashMap은 해시 함수를 통해 '키'와 '값'이 저장되는 위치를 결정하므로, 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어 있는 위치 또한 관계가 없다. HashMap 사용법 HashMap 선언 Ha..

TreeSet이란? TreeSet은 HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다. 하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리(BinarySearchTree)구조로 이루어져 있다. 이진 탐색 트리는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조이다. 그렇기에 HashSet보다 데이터의 추가/삭제는 시간이 더 걸리지만 검색과 정렬에는 유리하다. 레드-블랙 트리(Red-Black Tree) TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리(Red-Black Tree)로 구현되어 있다. 일반적인 이진 탐색 트리는 트리의..

HashSet이란? HashSet은 Set 인터페이스의 구현 클래스이다. 그렇기에 Set의 성질을 그대로 상속 받는다. Set은 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있다. 또한 저장 순서가 유지되지 않는다. 만약 요소의 저장 순서를 유지해야만 한다면 LinkedHashSet 클래스를 사용하면 된다. Set 인터페이스를 구현한 클래스로는 HashSet과 TreeSet이 있는데 HashSet의 경우 정렬을 해주지 않고 TreeSet의 경우 자동정렬을 해준다는 차이점이 있다. Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 점이다. 만약 한 편의점에서 오늘 방문한 손님의 총 숫자를 계산하고 싶을 경우도 있을 것이다. 이럴 경우 오늘 하루동안 편의점을 여러 번 방문한 손님은 한..

Vector란? Vector는 ArrayList와 동일한 내부구조를 가지고 있다. ArrayList와 마찬가지로 Vector내부에 값이 추가되면 자동으로 크기가 조절되며 그 다음 객체들은 한 자리씩 뒤로 이동된다. 하지만 Vector와 ArrayList의 한 가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있다. Vector의 단점 (ArrayList와의 비교) 벡터는 항상 동기화되는 장점이자 단점을 가지고 있다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어진다...

LinkedList란? 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다. 결론 : 검색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경..

ArrayList란? ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트이다. 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점 등이 유사하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량을 초과한다면 자동으로 부족한 크기만큼 저장 용량이 늘어난다는 특징을 가지고 있다. ArrayList 사용법 ArrayList 선언 ArrayList list = new ArrayList();//타입 미설정 Object로 선언된다. ArrayList members = new ArrayList();//타입설정 Student객체만 사용가능 ArrayList num = new ArrayList();//타입설정 ..

위 사진을 보면 알 수 있듯 ArrayList는 index가 있고, LinkedList는 각 원소마다 앞,뒤 원소의 위치값을 가지고 있다. 이러한 각각의 특징은 조회, 삽입, 삭제시에 성능의 차이를 발생시킨다. references : devlog-wjdrbs96.tistory.com/64 ArrayList ArrayList는 기본적으로 배열을 사용한다. 하지만 일반 배열과 차이점이 존재한다. 일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만, ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다. 조회 ArrayList는 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한번에 가져올 수 있다. 데이터 삽입과 삭제 ..

스택 (Stack)이란? 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 가장 위에 있는 자료(top)는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다. 따라서 스택은 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 갖게 된다...

배열(Array)과 ArrayList의 차이점 Array ArrayList 사이즈 초기화시 고정 int[] arr = new int[3]; 초기화시 사이즈를 표시하지 않음. 크기가 가변적임 ArrayList arrList = new ArrayList(); 속도 초기화시 메모리에 할당되어 ArrayList보다 속도가 빠름 데이터 추가 삭제시 메모리를 재할당하기 때문에 속도가 Array보다 느림 크기 변경 사이즈 변경 불가 추가, 삭제 가능 add(), remove() 다차원 int[][][] multiArr = new int[3][3][3]; 불가능 import java.util.ArrayList; import java.util.Arrays; public class ArrayListTest { public..