<aside> 💡 자료구조란 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여주는 개념이다.

</aside>

자료구조 기본 개념

• 배열(Array)
  • 순차적 또는 연속적
  • 요소를 임의의 순서로 읽을 수 있다
  • 데이터 추가 및 삭제 시 다른 데이터들의 순서를 다시 매겨야 하므로 시간이 걸린다.
  • 특히 기존에 선언한 배열 크기 이상의 데이터를 추가하려 하면 그만한 크기의 데이터를 메모리상에 만들고 기존 배열을 복사한 후 추가 데이터를 입력하는 방식이라 비효율적이다.
• 리스트(List)
  • 요소들이 흩어진 상태로 메모리에 저장된다.
  • 데이터와 포인터(=참조)의 쌍으로 구성된다. 이 쌍을 노드라고 부른다.
  • 진입 지점이 있도록 구성되는데, 이 진입점을 헤드라고 한다.
  • 단방향, 양방향, 순환 구조가 있다.
• 큐(Queue)
  • FIFO방식
  • 우선순위 큐(Priority Queue)
    • 우선순위가 높은 순서대로 추출
    • 같은 우선순위일 경우 먼저 추가된 요소
• 스택(Stack)
  • LIFO방식
• 트리(Tree)
  • 최상단을 루트 노드라 한다.
  • 최하단 노드를 리프 노드(말단 노드)라 한다.
  • 한 노드를 부모 노드(상위 노드)로 한다면, 거기에 연결된 밑의 노드들은 자식 노드(하위 노드)라 한다.
  • 노드끼리 연결하는 선을 엣지라고 한다.
  • 이진 탐색 트리
    • 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.
    • 최하단 최좌측노드는 최솟값, 최하단 최우측노드는 최댓값을 갖는다.
    • B 트리
      • 이진 탐색 트리와 달리 자식 노드를 3개 이상 갖고 있다.
  • AVL(Adelsom-Velsky and Landis) 트리
    • 시간복잡도는 $O(logn)$ 이다.
    • 최악의 경우로 일자로 쭉 연결된 트리가 있는데, 이걸 이진 탐색트리처럼 재정렬한 트리를 AVL 이진 트리라고 한다.
    • 높이 차이를 감지하면 트리 회전 과정을 통해 균형을 조정하는 메커니즘을 가진 트리다.
    • RB(Red-Black) 이진 탐색 트리
      • AVL트리보다 균형 조정 과정에서 트리 회전수가 적어 효율적이다
      • 일반적으로 루트 노드는 검정을 갖고, 빨강 노드는 검정 노드를 자식으로 갖는 트리다.
• 힙(Heap)
  • 트리 기반 데이터 구조이다.
  • 우선순위 큐는 힙을 이용해 구현할 수 있다.
  • 루트 노드가 힙의 최댓값이고 노드 각각의 값이 부모 노드보다 작거나 같은 구조의 힙을 최대 힙이라고 한다.
  • 반대의 경우를 최소 힙이라고 한다.
  • 힙 데이터 구조는 힙 메모리와 전혀 다른 개념이다.
• 해시(Hash)
  • 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것이다.
  • 해시값을 출력하는 함수를 해시함수라고 한다.
  • 해시도 경우에 따라 다른 입력이 같은 해시값을 생성하는 해시 충돌 가능성이 있다. (나무위키 비둘기집 원리 참고)
  • 해시 테이블
    • 키와 값으로 구성된 검색 시스템
    • 해시 테이블을 이용한 탐색을 해싱이라고 한다.
    • $O(1)$ 의 시간복잡도를 갖는다.
    • 체이닝
      • 해시 충돌을 방지하기 위해 만들어진 방식이다.
      • 각 해시값마다 링크드 리스트를 만들어서 값을 연결시키는 방식이다.
      • 체이닝이 길어지면 시간복잡도가 증가할 가능성이 있기 때문에 해시값의 종류를 늘리는 것과 비교해 선택해야 한다.
• 그래프(Graph)
  • 노드 사이의 연결을 보여주는 것이다.
  • 트리와 달리 루트 노드가 없는 트리처럼 보인다. 일부 프로그래머는 트리를 최소화된 그래프로 여기기도 한다.
  • 노드를 객체(object) 또는 정점(vertex)라고 한다.
  • 정점을 연결하는 선을 엣지라고한다.
  • 유향 그래프(directed graph)
    • 엣지가 방향성을 가진 그래프를 뜻한다.
    • 방향성을 가진 엣지를 유향 엣지(directed edge) 또는 화살표(arrow)라고 한다.
    • 유향 그래프를 다이그래프(digraph)라고도 한다.
  • 방향성이 없는(양방향 이동 가능한) 그래프를 무향 그래프(undirected graph)라고 한다.
  • 정점에서 다른 정점으로 이동하는 엣지들을 합쳐 경로라고 한다
  • 첫 정점과 마지막 정점이 일치하는 형태를 루프라고 한다.
  • 가중치 그래프(weighted graph)
    • 엣지가 가중치를 갖는 그래프를 뜻한다.
    • 양방향 모두 같은 가중치를 가지면 무향 가중치 그래프라고 한다.
    • 각 방향이 다른 가중치를 가지면 유향 가중치 그래프라고 한다.

자바 자료구조의 모든것

API reference for Java Platform, Standard Edition

Java Development Kit Version 17 API Specification

Java Development Kit Version 17 API Specification

개요

https://medium.com/@dakota.lillie/javas-collections-framework-an-overview-86de12f4f622