Linked List

Linked List(연결 리스트)란 데이터들을 가지고 각 데이터의 node(위치)가 연결되어 있는 선형구조를 말한다. 원하는 데이터를 찾기 위해서는 무조건 처음(head)부터 데이터를 검색해서 다음노드로 넘어가야 한다. tail을 넘어가는 값은 Null이 나온다. 선형구조로 이루어져 있어 데이터를 삽입하기 유용하지만, 검색시간이 오래 걸린다.

Linked List Methods

• find(): 들어오는 position의 노드를 찾아 들어있는 데이터를 반환한다.
• add(): 마지막 노드에 새 노드를 연결해 데이터를 삽입한다.
• Remove(): 삭제하려는 노드의 주소값 전후의 노드를 연결해주어 삭제한다.

Linked List property

• head: 첫번째 데이터
• Pointer: node와 node를 연결해줌
• tail: 마지막 데이터

Graph

Graph란 node와 node를 연결하는 간선(edge)을 하나로 모아 놓은 Data Structure이다. 하지만 모든 노드들이 전부 서로 연결되어 있는 것은 아니다.
양방향으로 통행이 가능한 무방향 그래프와, 일반통행만 가능한 방향 그래프가 있다.무방향 = 양방향 통행

Graph Methods

addNode(): 노드와 노드를 연결시켜 준다
removeNode(): 노드와 노드 사이의 연결을 해지한다

Graph property

edge: 위치 간의 관계(노드와 노드를 연결)

Graph Pseudocode

Tree

가계도 처럼 맨 처음의 Root노드가 있고 그 아래로 자식노드들이 생기는 구조. 오른쪽으로 뻗은 가지들은 부모노드보다 값이 크고 왼쪽으로 뻗은 가지들은 부모노드보다 값이 작다(그림에서는 G가 가장 큰 노드, H가 가장 작은 노드)

Binary Search Tree

각 노드가 최대 두 개의 자식을 갖는 트리

Tree property

Root: 노드의 시작점, 조상 노드
Child Node: 자식노드, 왼쪽으로 뻗을시 부모노드보다 값이 작고, 오른쪽으로 뻗을 시 그 반대
Sub-tree:
Leaf Node: 자식노드가 없는 노드
Siblings: 같은 부모를 가진 노드

Hash Table

해시테이블은 key와 value를 가지고 있다. 만약 key 'john smith'라는 key를 넣었을 떄 hash function(hash code)이라는 함수가 key의 값을 임의의 index인 02로 변환한다. 하지만 이렇게 임의로 index를 변환하면 다른 key값이 같은 index를 가지게 되 충돌 형상이 일어난다. 따라서 index값에 다른 장소의 주소값, 공간을 만들어 같은 index에 다른 값이 나올 수 있도록 설정한다. 이렇게 데이터를 저장하다 보면 같은 index가 나올수록 공간이 커지는 단점이 있다.