NAIAHD

09-1 선형 리스트

리스트는 데이터를 순서대로 나열한 자료구조입니다

선형 리스트란?

가장 단순한 구조를 이루고 있는 리스트를 선형 리스트 또는 연결리스트라고합니다.

리스트의 데이터는 노드또는 요소라고 합니다.

배열로 선형 리스트 만들기

09-2 포인터로 연결 리스트 만들기

포인터로 연결 리스트 만들기

연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고 , 삭제할 떄 노드용 객체를 없애면

앞 페이지의 문제를 해결할 수 있습니다.

09-3 커서로 연결 리스트 만들기

포인터 역할을 하는 인덱스를 커서라고 합니다.

09-4 원형 이중 연결 리스트

원형 리스트 : 연결 리스트의 꼬리 노드가 머리 노드를 가리키면 원형 리스트라고 합니다.

이중 연결 리스트 연결 리스트의 가장 큰 단점은 노드는 찾기 쉽지만 압쪽의 노드는 찾을 수 

없다는 점입니다. 이 단점을 개선한 자료구조 

원형 이중 연결 리스트 : 앞에서 공부한 두가지의 개념이 합해진 원형 이중 연결리스트

10-1 트리

트리를 구성하는 요소는 노드와 가지입니다. 

루트: 트리의 가장 윗부분에 위치하는 노드

리프

안쪽노드 

자식 

부모

형제

조상

자손

레벨 : 루트로부터 얼마나 떨어져 있는지에 대한 값

차수: 노드가 갖는 자식의 수

높이

서브트리 : 자손으로 이루어진 트리

널 트리 : 가지가 없는 트리

 순서트리와 무순서 트리

순서 트리 검색

너비 우선 검색: 

깊이 우선 검색; 

전위순회 Preorder 노드 방문- > 왼쪽 자식 -> 오른쪽 자식

중위순회 Inorder 왼쪽 방문-> 노드 방문 -> 오른쪽 자식

후위순회 Postorder 왼쪽 자식->오른쪽 자식-> (돌아와 ) 노드 방문 

10-2 이진 트리와 이진검색 트리

이진트리 : 노드가 외쪽 자식과 오른쪽 자식을 갖는트리

완전 이진 트리 : 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리

이진 검색 트리: binary search Tree

11. 해시

11-1 해시법

해시법은 겁색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법입니다.

키-value

해시 테이블의 각 요소를 버킷이라고 합니다.

저장할 버킷이 중복되는 현상을 충돌이라고 합니다.

충돌에 대한 대처

1. 체인법: 같은 해시값을 갖는 요소를 연결 리스트로 관리합니다.

2. 오픈 주소법: 빈 버킷을 찾을 때 까지 해시를 반복합니다.

체이법: 같은 해시 값을 갖는 데이터를 쇠사슬모양으로 연결 리스트에서 연결하는 방법으로, 오프해시법이라고도 합니다.

오픈 주소법

또 다른 해시법인 오픈 주소법은 충돌이 발생했을 때 재해시를 수행하여 비어있는 버킷을 찾아내는 방법으로 , 닫히 해시법이라고도 합니다.

출처 : Do It !자료 구조와 알고리즘의 입문