Data Structure(Linked List, Hash Table, Graph, Tree, Binary Search Tree)

자료구조(Data Structure)란?

자료를 어떻게 효율적으로 조직, 관리, 저장 할 것인지
데이터 값의 모임 또는 데이터 간의 관례, 그리고 데이터에 적용할 수 있는 함수

어떤 자료구조를 가지고 있는지 파악을 해야 내가 코드를 짤 때 어떻게 짜야하는지 결정할 수 있다.

---

1. Linked List

list라는 어떤 기능을 가지고 있는 데이터 스트럭쳐를 만드는 여러가지 방법 중 하나.

Linked란 무엇인가?
어떻게 표현하는가?

CPU : 생각하고 계산하고 연산하는 일을 담당하고 있는 부품. 가장 속도가 빠르다.
MEMORY메모리(RAM) : 컴퓨터에서 기억을 담당하고 있는 부품. 속도↑ 용량↓ 가격↑ 전원 차단시 데이터가 사라진다.
STORAGE스토리지(HDD, SSD) : 컴퓨터에서 저장소를 담당하고 있는 부품. 속도↓ 용량↑ 가격↓ 전원 차단해도 데이터가 남아있다.
데이터는 기본적으로 스토리지에 저장이 된다.

스토리지는 정보를 처리하는 능력이 매우매우 느리므로 CPU에서 바로 스토리지로 연결하지 않고, 스토리지에 저장되어있는 정보들을 메모리로 옮겨 CPU가 읽을 수 있게 한다.

데이터 스트럭쳐의 대상은 메모리이고
데이터 스트럭쳐의 미션은 메모리의 효율적 사용이다.

메모리를 건물에 비유했을 때, 건물에는 각각의 주소를 가지고 있는 여러 사무실들이 있다. 메모리는 그 각각에 주소에 접근할 때 걸리는 시간이 동일 하다. 걸리는 시간을
Random Access Memory : RAM 이라고 한다.
즉, 주소만 알고 있다면 우리는 그 정보에 매우 빠르게 접근할 수 있다.

Array List : 연속적으로 붙어있는 성격을 가진다.
Linked List : 각각의 엘리먼트들이 따로 흩어져 있지만 각 엘리먼트들은 연결되어있다.

Linked List 구조

LL은 연결되어 있는 특성이 있어 내부적으로 엘리먼트 대신에 node(마디, 교점) or vertex(정점, 꼭지점)라고 지칭한다.

구조를 설명하기 위한 표현
객체를 이용하여 노드를 표현한다. 노드안에는 두가지의 필드가 있다. 1데이터필드라는 변수에 실제값이 담겨있고 2링크필드라는 변수에 다음노드가 무엇인지 담겨있다.
첫번째 노드가 무엇인지 알아야한다.(첫번째 노드를 나타내는 데이터를 head에 담는다.)

데이터 추가하기

• 첫번째위치에 추가하기

1. 추가할 새로운 노드 생성
2. 신규노드 다음노드(.next)를 기존첫번째노드로 지정. head 시작지점을 나타내는 변수
3. 신규노드에 head를 가져온다.

Vertex vtx = new Vertex(v) 
vtx.next = head 
head = vtx

• 중간위치에 추가하기 - 5번째 자리(인덱스 4)에 노드를 추가한다.

1. 임시변수 하나를 선언한다.
2. head를 시작으로 4번째 인덱스까지의 값를 임시변수에 정보를 옮겨 담는다.(for or while)
3. 또다른 변수에 5번째 인덱스의 노드를 옮겨 담는다.
4. 새로운 노드를 만든다.
5. 2에서 멈춘 변수 다음에 새로운 노드를 지정하고 그 다음 노드를 3의 걸로 지정한다.

Vertex pre = head 
for (k = 0; k < i-1; k++)
  pre = pre.next 
Vertex aft = pre.next 
Vertex vtx = new Vertex(v) 
vtx.next = aft 
pre.next = vtx 

배열의 경우 중간에 있는 엘리먼트를 추가하거나 삭제할 경우 해당 엘리먼트 뒤에 위치한 모든 엘리먼트가 자리를 변경해야했다. 그래서 속도가 느리다. 하지만 ll의 경우 변경될 엘리먼트의 이전/이후 노의 참조값(.next)만 변경하면 되서 속도가 비교적 빠르다.

• 마지막위치에 추가하기

1. 새로운 노드선언
2. 꼬리 다음에 오는 노드로 신규노드를 지정.
3. 붙인 신규노드에 꼬리표를 붙인다.

Vertex vtx = new Vertex(v) 
tail.next = vtx 
tail = vtx

데이터 제거하기

2. Hash Table

데이터를 관리하거나 유지하는 자료구조이다. 리소스보다는 속도를 중요시한다. 기본 작동원리는 데이터를 해시함수를 커쳐 해시테이블에 넣는 것이다.
똑같은 데이터가 올 때 마다 똑같이 분류하는 규칙성이 필요한데,
그 규칙성이 해시함수다.

• 용어정리
  해시함수 : 데이터를 보고 규칙적으로 뿌려준다.
  해시테이블 : 해시함수가 뿌린 정보들이 담기는 곳. 인덱스or키와 해시값or벨류로 나뉘어져있다. 인덱스의 기준을 버켓이라고 하고 버켓안에 들어가는 값을 엔트리라고 한다.
  해싱 : 데이터가 해시함수에 들어가서 해시테이블에 뿌려지는 과정 전체를 의미한다.
  충돌 : 하나의 인덱스에 두개 이상의 값이 들어가려고 하면서 일어난다.

• 충돌 대처 하기

1. Chainig체이닝
   : 해당 인덱스에 이미 값이 있을 경우 기존 값과 신규값을 체인(list등의 자료구조 이용)으로 연결시킨다.
2. Linear Probing리니어 프로빙(선형탐사)
   : 원래 인덱스가 아닌 다른 빈 인덱스에 일단 집어넣는다. 다만, 이렇게 하면 인덱스가 빨리 다 차게 된다. 그러면 테이블 리사이징을 해서 테이블의 크기를 늘여서 기존값들을 다시 해싱한다.

해시테이블은 기본적으로 키와 값으로 이루어져있기 때문에 만들 때에도 키와 값을 선언해주어야한다.

Hashtable<key, value> hashtable = new Hashtable<key, value>();

//key와 value는 Integer(정수), String(문자) 등의 형식으로 작성

메소드

put : 키와 값, 한쌍 넣기.

hashtable.put(key, value);
hashtable.put("a", 1);
hashtable.put("b", 2);
//이때 키가 동일할 경우 기존값이 신규값으로 대체되는 충돌이 일어난다.
hashtable.put("c", 3);
hashtable.put("c", 4);
hashtable.c // 4

get : 값 얻어오기

hashtable.get(key); // value
hashtable.get("a"); // 1
hashtable.get("b"); // 2

3. Graph

그래프란 상하위의 개념없이 각각의 노드와 노드 사이의 간선을 하나로 모아 놓은 자료구조이다. 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph) 두가지로 나뉜다.
방향 그래프 : 노드 사이 간선에 방향성이 있는 그래프.
무방향 그래프 : 노드 사이 간선에 방향성이 없는 그래프.

• 용어정리
  노드(Node) : 정점(Vertex)이라고도 한다.
  간선(Edge) : 정점을 이어주는 선.
  차수(Degree) : 하나의 정점에 닿는 간선의 수.
  인접 노드(Adjacent Node) : 간선을 통해 한 번만에 이동할 수 있는 경우.
  인접 리스트
  인접 행렬

그래프를 표현하는 방법에는 이차원 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다. 이차원 배열은 간단하지만 공간을 많이 차지하고 연결 리스트는 복잡하지만 공간을 적게 차지한다.

새로운 Graph {
   그래프 생성자{ 비어있는 노드 리스트 }
   
   노드 생성자 {
      노드 이름;
      노드와 연결된 노드 리스트[];   //edge
   }
   노드 입력 {
      data = new 노드;
      while(edge수){
         연결되는 노드에도 edge 추가
      }
      return graph;
   }
}

4. Tree & Binary Search Tree

• 용어정리
  Root : 트리의 최상위 노드
  leaf: 자식 노드가 없는 노드(=마지막 노드)
  내부 노드 : Root와 leaf을 제외한 노드들을 내부 노드라고 한다.
  Child: 자식 노드
  Parent: 부모 노드
  ancestor: 조상 노드
  descendant: 자손 노드
  sibling: 형제 노드
  branch, edge : 노드와 노드 사이를 이어준다.

Path(경로) : Root부터 leaf까지 가는 길.
시작점은 반드시 root 하나여야한다.

트리구조는 계속 트리구조가 이어진다는 점을 유의해야한다. 루트의 노드가 없어져도 하위노드가 루트역할을 할 수 있다. 그래서 재귀함수를 사용해야한다.

이진 탐색 트리(Binary Search Tree)

: 한 노드당 최대 두개의 자식 노드만을 가지는 트리구조. 각 노드의 키가 왼쪽 하위 트리의 키보다 크거나 같고 오른쪽 하위 노드의 키보다 작거나 같아야한다.