Linked List
그림은 방 5개가 있습니다, 5번방에가려면 1번부터 5번까지 거쳐가야합니다, 왜냐하면 5번방의위치는 4번방의 주인이 알고있고 4번방의 위치는 3번방의 주인만 알고있기때문에 순서대로 물어물어 가야하기 때문입니다, 이 경우 1번방의 주인이 HEAD가 되고 5번방의 주인이 Tail 이 되는것입니다. 이러한 방식이
Linked list 입니다.
Property
Head : 첫 번째 노드를 지정하는 참조값
Tail : 마지막 노드를 지정하는 참조값
Method
addToTail : 마지막 번째 노드에 데이터를 삽입
removeHead : 첫 번째 노드를 삭제
contains : 연결 리스트가 주어진 값을 포함하고 있는지 확인
Hash Table
데이터관리 와 유지를 하는데 유용한 자료구조이다.
리소스를 포기하고 속도를 더 챙겼다.
규칙성이없는 집단이 있었는데 해쉬함수를 거쳐 규칙성있는 집단으로 바꾸어주었다 이것을 해싱 이라고하고, 규칙성이생긴 저 곳을 해쉬테이블이라 한다 해쉬함수의 규칙은 만들기 나름인것같다.
하지만 문제가 있는데 만약 1이란 숫자가 2개일경우에 한곳에 두개의1이 생긴다 그러하여 충돌이생기는데 이 충돌을 보완하고자 많은 방법등이 생겼는데 2가지를 얘기해보겠습니다.
Chaining
위에서 말한 linked list 처럼 값 뒤에 '슥' 하고 붙여나가는 방법이다. 1 - 2- ....7
Linear Probing
체이닝을 하다보니 리소스가 많이소모되고 다른테이블은 쓰지않게 되다보니 다른테이블을 소모하고자 나온 기법이다 만약 1번의자리를 들어가려는 데이터가있는데 그 자리가 차있다면 다른 빈자리를 들어가게끔 하는것이다.
Resizing
빈 자리로 넣는것도 한계가 있을것이다.그럴때 Table - Resizing 을 하게되는데 테이블의크기를 늘려준뒤 기존의 데이터들을 다시 해쉬함수로 보낸다 그리고 다시 늘려준 해쉬테이블의 재정렬 시켜주는 방법이다. 그렇게하면 다시 겹치는 테이블이 있어도 Linear Probing 기법을 쓰면 될 것이다.
Tree
노드가 하나 이상의 자식을 가지면 Tree 라고 한다.
비선형 자료구조로 계층적 관계를 표현한다. (디렉터리구조, 조직도)
대표적으로 HTML 구조에서 사용된다.
루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
Binary Search tree (이진 검색 트리)
노드가 하나 이상의 자식을 가지면 Tree 라고 하는데 최대 2개까지만 붙는 트리를 Binaty tree 라고 부른다.
이진 검색 트리는 위와 같이 생겼습니다, 숫자가 정렬된 형태를 가지고있는데 가장작은숫자는 가장왼쪽, 가장 큰 숫자는 오른쪽에 있습니다.
그러하여 만약 데이터를 기준으로 작은숫자를 찾고싶으면 왼쪽으로, 큰 숫자를 찾고싶으면 오른쪽 방향을 탐색하면 쉽게 찾을 수 있습니다,그러하여 이진검색트리 는 중복 데이터가 없다는 가정 하에 크다와 작다를 쉽게 구분할 수 있게됩니다.
Graph
Graph 는 상하위 개념이없이 각각의 node와 node들 간의 edge 을 하나로 모아놓은 자료구조이다.
Tree 는 Graph 의 한 형태라고 할수있다.
