나상민의 TIL

# 자료구조의 구분

  • 비선형 자료구조
    • 그래프
    • 트리
  • 선형 자료구조
    • 리스트
    • 큐
    • 덱
  • 집합(Set)
  • 파일 자료구조
    • 순차파일
    • 색인파일
    • 직접파일

# 자바 컬랙션 프레임워크

javaCollectionFramework.png List, Queue, Set 이 3가지의 형태에 따른 자료구조들이 있다. 그리고 Queue와 Set에는 조금 더 구체화 되어 Deque과 SortedSet이라는 형태에 따른 자료구조가 있는 것이다. 그리고 이 형태에 따른 자료구조들은 각각 구현이 되어 class로 제공된다. 바로 녹색 부분이 구현된 자료구조라고 보면 된다. 자바에서 Interface를 class파일에서 쓰면 보통 구현한다라고 한다. 이러한 메커니즘에 기반하여 이해하면 될 것이다.

# List Interface

# List Interface를 구현하는 클래스

  1. ArrayList
  2. LinkedList
  3. Vector (+ Vector를 상속받은 Stack)

# List Interface에 선언된 대표적인 메소드

메소드 리턴타입 설명
add(E e) boolean 요소를 추가합니다
remove(Object o) boolean 지정한 객체와 같은 첫 번째 객체를 삭제합니다
contains(Object o) boolean 지정한 객체가 컬렉션에 있는지 확인합니다.있을경우 true, 없을경우 false를 반환합니다.
size() int 현재 컬렉션에 있는 요소 개수를 반환합니다.
get(int index) E 지정된 위치에 저장된 원소를 반환합니다
set(int index,E elements) E 지정된 위치에 있는 요소를 지정된 요소로 바꿉니다.
isEmpty() boolean 현재 컬랙션에 요소가 없다면 true를, 요소가 존재한다면 false를 반환합니다.
equals(Object o) boolean 지정된 객체와 같은지 비교합니다.
indexOf(Objeft o) int 지정된 객체가 있는 첫 번째 요소의 위치를 반환합니다. 만일 없을경우 -1을 반환합니다.
clear() void 모든 요소들을 제거합니다.

# 배열과 List의 공통점 및 차이점

# 공통점

  1. 동일한 특성의 데이터들을 묶는다.
  2. 반복문(loop)내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다.

# 차이점 - 배열

  1. 처음 선언한 배열의 크기(길이)는 변경할 수 없다. 이를 정적 할당(static allocation)이라고 한다.
  2. 메모리에 연속적으로 나열되어 할당된다.
  3. index에 위치한 하나의 데이터(element)를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.

# 차이점 - 리스트

  1. 리스트의 길이가 가변적이다. 이를 동적 할당(dynamic allocation)이라고 한다.
  2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고 각 데이터들은 주소(reference)로 연결되어있다. C에서의 포인터라고 생각하면 된다.)
  3. 데이터(element) 사이에 빈 공간을 허용하지 않는다.

# 배열의 장점

  1. 데이터 크기가 정해져있을 경우 메모리 관리가 편하다.
  2. 메모리에 연속적으로 나열되어 할당하기 때문에 index를 통한 색인(접근)속도가 빠르다.

# 배열의 단점

  1. 배열의 크기를 변경할 수 없기 때문에 초기에 너무 큰 크기로 설정해주었을 경우 메모리 낭비가 심해지고, 반대로 너무 작은 크기로 설정해주었을 경우 데이터를 다 못담을 수 있는 경우가 발생 할 수 있다.
  2. 빈 공간을 허용하지 않고 데이터를 삽입(add), 삭제(remove)를 하고자 한다면, 뒤의 데이터들을 모두 밀어내거나 당여주어야 하기 때문에 속도가 느려 삽입, 삭제가 빈번한 경우에는 유용하지 않다.

# 리스트의 장점

  1. 데이터의 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리가 편리해진다.
  2. 빈 공간을 허용하지 않기 때문에 데이터 관리에도 편하다.
  3. 포인터(주소)로 각 데이터들이 연결되어 있기 때문에 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입 삭제에 용이하다.(ArrayList는 예외)

# 리스트의 단점

  1. 객체로 데이터를 다루기 때문에 적은양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다. 간단히 예로들어 primitive type인 Int는 4Byte를 차지한다. 반면에 Wraaper class인 Integer는 32bit JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 '최소 16Byte를 차지한다. 거기에다가 이러한 객체데이터들을 다시 주소로 연결하기 때문에 16 + α 가 된다.
  2. 기본적으로 주소를 기반으로 구성되어있고 메모리에 순차적으로 할당하는 것이 아니기 때문에(물리적 주소가 순차적이지 않다) 색인(검색)능력은 떨어진다.

# ArrayList

ArrayList는 Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다. 우리가 흔히 쓰는 primitive 배열(ex int[])과 유사한 형태라고 보면 된다.

즉, 최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근(access elements)에서는 탁월한 성능을 보이나, 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적인 모습을 보인다.

# LinkedList

LinkedList는 데이터(item)와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 Node(노드)라고 하는데, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식인 것이다.(이중 연결 리스트라고도 한다.)

즉, 객체끼리 연결한 방식이다. 이렇다보니 요소를 검색해야 할 경우 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 모두 방문해야한다는 점에서 성능이 떨어지나, 해당 노드를 삭제, 삽입해야 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.

# Vector

Vector는 자바를 배울 때 그리 자주 보이지는 않는 클래스인데, 기본적으로 ArrayList와 거의 같다고 보면 된다. Object[] 배열을 사용하며 요소 접근에서 빠른 성능을 보인다. 근데 왜 Vector가 있는 것이냐?라고 한다면, 원래 Vector는 Collection Framwork가 도입되기 전부터 지원하던 클래스였다.

그리고 Vector의 경우 항상 '동기화'를 지원한다. (쉽게 말하면 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다.) 그렇다보니 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.

# Stack

Stack은 우리가 흔히 생각하는 것처럼 쌓아 올리는 것이다. 전문용어로 말하면 LIFO(Last in First out) 또는 후입선출이라고 하는데, 쉽게 생각하면 우리가 짐을 쌓는다고 생각하면 쉽다. 짐을 쌓아올릴 때 가장 마지막에 쌓은 짐이 가장 위에 있을 것이다. 그리고 짐을 뺄 때도 가장 위에 있는 짐부터 빼게 될 것이다. 가장 대표적인 예시로는 웹페이지 '뒤로가기'가 있다. 우리가 새로운 페이지로 넘어갈 때마다 넘어가기 전 페이지를 스텍에 쌓고, 만약 뒤로가기를 누른다면 가장 위에 있는 페이지부터 꺼내오는 방식이다.

참고로 Stack의 경우 Vector클래스를 상속받고 있고, java에서 지원하는 Stack 클래스의 메소드들도 뜯어보면 알겠지만, 모두 Vector에 있는 메소드를 이용하여 구현되고 있어 크게 다를 것은 없다

# Queue Interface

# Queue/Deque Interface를 구현하는 클래스

  1. LinkedList
  2. ArrayDeque
  3. PriorityQueue

# Queue/Deque Interface에 선언된 대표적인 메소드

인터페이스 메소드 리턴타입 설명
Queue/Deque add(E e) boolean 요소를 꼬리에 추가합니다. 만약 큐가 모두 찼을 경우 IllegalStateException 예외를 던집니다.
Queue/Deque offer(E e) boolean 요소를 꼬리에 추가합니다. 큐가 모두 차더라도 IllegalStateException을 던지지 않습니다.
Queue/Deque peek() E 헤드를 삭제하지 않고 검색하여 요소를 반환합니다.
Queue/Deque poll() E 헤드를 검색 및 삭제하면서 요소를 반환합니다.
Deque addLast(E e) void 요소를 꼬리에 추가합니다. 만약 큐가 모두 찼을 경우 IllegalStateException 예외를 던집니다 (= add(E e)와 같습니다)
Deque addFirst(E e) void 요소를 헤드에 추가합니다. 만약 큐가 모두 찼을 경우 IllegalStateException 예외를 던집니다.
Deque offerLast(E e) boolean 요소를 꼬리에 추가합니다. offer(E e)와 같습니다.
Deque offerFirst(E e) boolean 요소를 헤드에 추가합니다.
Deque peekFirst() E 헤드에 있는 요소를 삭제하지 않고 반환합니다. peek()과 같습니다.
Deque peekLast() E 꼬리에 있는 요소를 삭제하지 않고 반환합니다.
Deque pollFirst() E 헤드를 검색 및 삭제하면서 요소를 반환합니다. poll()과 같습니다.
Deque pollLast() E 꼬리를 검색 및 삭제하면서 요소를 반환합니다.
Deque size() int 요소의 개수를 반환합니다.

← Singleton 패턴 →