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 !자료 구조와 알고리즘의 입문
'책 > Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편' 카테고리의 다른 글
07. 집합 08. 문자열 검색 (0) | 2020.09.13 |
---|---|
06. 정렬 (0) | 2020.08.30 |
04. 스택과 큐 05. 재귀 알고리즘 (0) | 2020.08.27 |
03. 검색 (0) | 2020.08.25 |
02. 기본자료구조 (0) | 2020.08.23 |