Post

Java[DataStructure]

Posted
By LeeJongWon
16 min read

자료구조

데이터를 효율적으로 구성하고, 저장하는 방법이나 데이터 간의 관계를 표현하는 방법을 말합니다.

프로그램이나 알고리즘이 작동하는 데 필요한 데이터를 조직화하고 다룰 수 있는 구조를 제공합니다.

이를 이용해, 데이터의 삽입, 삭제 등의 연산을 더 효율적으로 수행하는데 도와줍니다.

자료구조는 크게 3가지로 나뉩니다.

자료구조 종류

  1. 선형 자료구조
    1. 배열 : 데이터를 순서대로 나열한 구조로, 각 요소는 인덱스로 접근이 가능합니다.
    2. 연결리스트 : 노드들이 데이터와 다음 노드를 가리키는 링크로 이루어진 구조입니다.
      • 단일 연결 리스트와, 이중 연결 리스트가 존재합니다.
    3. 스택 : 데이터를 쌓아 올리는 형식의 자료구조로, 나중에 들어온 데이터가 먼저 나가는 구조입니다.
      • 후입선출(LIFO) 구조를 가지고 있습니다.
    4. 큐 : 데이터를 일렬로 나열한 형태로, 먼저 들어온 데이터가 나가게 됩니다.
      • 선입선출(FIFO) 구조를 가지고 있습니다.
  2. 비선형 자료구조
    1. 트리 : 노드들이 부모-자식 관계를 가지며, 계층적으로 구성된 자료구조 입니다.
      • 이진트리, 이진 탐색 트리, AVL 트리 등이 있습니다.
    2. 그래프 : 정점과 간선으로 이루어진 자료구조로, 두 정점 간의 관계를 나타냅니다.
      • 유향 그래프와, 무향 그래프가 있습니다.
  3. 해시 자료 구조
    1. 해시 테이블
      • 해시 함수를 사용하여 키와 값을 연결하는 자료구조로, 검색이 매우 빠르게 이루어지빈다.

Java Collection Framwork

java-collection-framework-png

자바에서 사용하는 컬렉션 프레임워크의 구조는 다음과 같습니다.

자료구조 정리

List

LinkedList

  • 데이터를 연결된 노드의 집합으로 표현하는 선형 자료구조 입니다.
  • 각 노드는 데이터 요소와 다음 노드를 가리키는 링크로 이루어져 있습니다.
    • 장점
      • 삽입 및 삭제가 빠릅니다.
      • 메모리 관리가 유연합니다.
    • 단점
      • 임의 접근이 느립니다.
      • 메모리 공간 낭비가 발생할 수 있습니다.
      • 캐시 지역성이 낮습니다.

ArrayList

  • 크기가 가변적인 배열로 구현된 리스트 자료구조입니다.
  • 데이터를 연속된 메모리 공간에 저장하여 인덱스로 사용하므로 요소에 빠르게 접근이 가능합니다.
    • 장점
      • 빠른 접근이 가능합니다.
      • 데이터 저장 및 읽기가 효율적입니다.
    • 단점
      • 크기 조정에 따른 성능 저하가 발생할 수 있습니다.
      • 삽임 및 삭제가 비효율적입니다.
      • 예상치 못한 크기의 요소가 저장될 경우 메모리가 낭비될 수 있습니다.

Vector

  • ArrayList처럼 크기가 가변적인 배열로 구현된 리스트 자료구조입니다.
  • ArrayList와 마찬가지로 데이터를 연속된 메모리 공간에 저장하여 인덱스로 사용하므로 요소에 빠르게 접근이 가능합니다.
  • ArrayList와 유사한 특성이지만, 스레드 안전성이 필요한 경우에 사용됩니다.
    • 장점
      • 멀티 스레드 환경에서 여러 스레드가 동시에 접근하더라도 안전하게 데이터를 읽고 쓸 수 있습니다.
      • 동기화를 제공하여, 여러 스레드가 동시에 Vector를 수정할 수 있도록 합니다.
      • 요소의 추가나 삭제가 필요할때 배열의 크기를 조절할 수 있습니다.
    • 단점
      • 단일 스레드 환경에서는 오버헤드가 발생하여 성능이 느릴 수 있습니다.
      • 동기화를 제공하여 모든 연상이 동기화되어 있어야해서 단일 스레드 환경에서 성능 저하를 가져올 수 있습니다.
      • 요소를 추가할 떄마다 배열의 크기를 조절해야합니다.

Stack

  • 후입 선출을 가지는 선형 자료구조 입니다.
  • 한쪽 끝에서만 데이터의 삽입,삭제가 일어나는 자료구조로, 최근에 삽입된 데이터가 가장 먼저 삭제됩니다.
  • 재귀 알고지름, 깊이 우선 탐색, 백트래킹등의 알고리즘에 사용됩니다.
    • 장점
      • 간단한 구조로, 구현이 쉽습니다.
      • 여산이 상수 시간(O(1))에 이루어집니다.
      • 메모리 관리가 간단하고, 스택 내부에서 삽입, 삭제가 일어나므로 메모리의 공간 낭비가 적습니다.
    • 단점
      • 스택의 크기는 제한적이며, 정적 배열로 구현된 경우에는 미리 크기를 지정해야합니다.
      • 동적 배열로 구현할 경우, 데이터가 추가될 때마다 배열의 크기를 조정해주어야 합니다.
      • 중간에 있는 데이터에 접근하기 위해서는 모든 데이터를 순차적으로 Pop 해야 합니다.

Set

HashSet

  • 헤시 테이블 기반으로 구현되어 있으며, 중복된 요소를 허용하지 않습니다.
  • 내부적으로 해시 버킷 배열을 사용하여 요소를 저장합니다.
    • 장점
      • 중복 요소를 제거할 수 있습니다.
      • 검색 속도가 빠릅니다.
      • 데이터 삽입 및 삭제가 빠릅니다.
    • 단점
      • 순서가 보장되지 않습니다.
      • 해시가 충돌할 수 있습니다. 이로인해 성능 저하가 발생할 수 있습니다

TreeSet

  • 이진 검색 트리를 기반으로 구현 되어 있습니다.
  • 요소를 정렬된 순서로 저장합니다.
  • 이진검색 트리
    • → 각 노드가 최대 2개의 자식 노드를 가지며, 부모 노드보다 작은 값은 왼쪽 자식 노드에, 큰 값은 오른쪽 자식 노드에 저장합니다.
    • 장점
      • 정렬된 순서를 유지합니다.
      • 검색 속도가 빠릅니다. [ O(log n) ]
      • 중복된 요소를 제거할 수 있습니다.
    • 단점
      • 메모리 사용량이 큽니다
        • 요소의 개수에 따라 메모리 사용량이 증가할 수 있습니다.
      • 삽입 및 삭제 작업의 비용이 높습니다.
        • 이진 검색 트리를 사용하므로, 삽입 및 삭제에 대한 비용이 높을 수 있습니다.
      • 순회 속도가 느립니다.
        • O(n)의 시간 복잡도를 가집니다.

Map

HashMap

  • 해시 테이블을 기반으로 하는 키-값 쌍의 자료구조 입니다.
  • 해시 맵을 사용하여 데이터를 저장하며, 각 키는 고유해야 합니다.
    • 장점
      • 검색 속도가 빠릅니다.
        • 해시 함수를 사용하여 데이터를 저장하므로 검색 속도가 빠릅니다.
        • O(1)
      • 데이터 삽입 및 삭제가 빠릅니다.
        • 해시 함수를 사용하여 데이터를 저장하므로 검색 속도가 빠릅니다.
        • O(1)
      • 다양한 종류의 데이터를 저장하고 관리가 가능합니다.
    • 단점
      • 순서를 보장하지 않습니다.
      • 충돌이 발생할 경우 성능이 저하됩니다.
      • 많은 양의 데이터를 저장하는 경우 메모리 사용량이 증가할 수 있습니다.

TreeMap

  • 이진 검색트리를 기반으로 한 자료구조 입니다.
  • 키 - 값 구조로 이루어져 있습니다.
    • 장점
      • 정렬된 순서를 유지합니다.
      • 검색 및 조회가 빠릅니다. ( O(log N) )
      • 중복을 허용하지 않습니다.
    • 단점
      • 포인터를 유지해야 하므로, 메모리 사용량이 크게 증가할 수 있습니다.
      • 요소의 삽입 및 삭제 작업이 복잡하고, 최악의 경우 O(log N) 시간이 소요됩니다.

HashTable

  • 키와 값을 연결하는 자료구조입니다.
  • 키를 기반으로 값에 대한 접근을 제공하고, 해시 함수를 사용하여 데이터를 저장하고 검색하는데 사용됩니다.
    • 장점
      • 해시 함수를 사용하여 데이터를 저장하므로 검색독도가 매우 빠릅니다. ( O(1))
      • 해시함수를 사용하여 데이터를 분산 저장하므로 메모리를 효율적으로 사용합니다.
    • 단점
      • 해시 함수는 서로 다른 입력에 대해 동일한 해시값을 반환할 수 있으며, 이로 인해 충돌이 발생할 경우 성능이 저하될 수 있습니다.
      • 데이터 순서를 보장하지 않습니다.
      • 다중 스레드 환경에서 동시에 접근할 경우 도익화 처리가 필요합니다.

결론

1. 배열(Array) vs. 연결 리스트(Linked List)

  • 배열(Array):
    • 장점:
      • 빠른 임의 접근(인덱스로 요소 접근).
      • 크기가 정해져 있고 연속된 메모리 공간에 저장되므로 캐시 지역성이 좋음.
    • 단점:
      • 크기가 고정되어 있고 중간에 요소를 삽입/삭제할 경우에 비효율적.
      • 삭제 후 메모리를 유지하기 위해 요소를 이동해야 함.
  • 연결 리스트(Linked List):
    • 장점:
      • 삽입/삭제가 빠름(O(1)).
      • 메모리 관리가 유연함.
    • 단점:
      • 임의 접근이 느림(O(n)).
      • 메모리 공간 낭비가 발생할 수 있음.

2. 스택(Stack) vs. 큐(Queue)

  • 스택(Stack):
    • 장점:
      • 구현이 간단하고 빠른 연산(삽입/삭제가 상수 시간).
      • 메모리 관리가 간단.
    • 단점:
      • 중간에 있는 요소에 접근하기 어려움.
      • 크기 제한이 있을 수 있음.
  • 큐(Queue):
    • 장점:
      • 선입선출(FIFO) 구조를 가지므로 순서를 보장.
      • 구현이 간단하고 빠른 연산(삽입/삭제가 상수 시간).
    • 단점:
      • 중간에 있는 요소에 접근하기 어려움.
      • 크기 제한이 있을 수 있음.

3. 이진 트리(Binary Tree) vs. 해시 테이블(Hash Table)

  • 이진 트리(Binary Tree):
    • 장점:
      • 데이터가 정렬되어 있어 탐색이 빠름.
      • 중복된 요소를 허용하지 않음.
    • 단점:
      • 메모리 사용량이 큼.
      • 삽입/삭제가 비효율적(O(log n)).
  • 해시 테이블(Hash Table):
    • 장점:
      • 검색 속도가 매우 빠름(O(1)).
      • 메모리를 효율적으로 사용함.
    • 단점:
      • 충돌이 발생할 경우 성능이 저하됨.
      • 데이터 순서를 보장하지 않음.
Java, DataStructure
DataStructure Java
This post is licensed under CC BY 4.0 by the author.