과목/자료구조 썸네일형 리스트형 파이썬 연결 리스트 singly linked list 1. 지정 노드의 왼쪽 또는 오른쪽에 삽입하는 것 구현 2. node 자체를 찾는 함수 3. node의 data를 찾는 함수 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.current = None def append(self, data): node = Node(data) if self.head is None: # 노드가 없는 경우 self.head = node self.current = node else: # 노드가 있는 경우 self.current = self.head while self.current.next: .. 해시 해쉬 해시테이블 해쉬테이블 Hash Hash Table 해쉬 함수에 검색하고자 하는 키 값을 넣으면 해쉬 알고리즘에 의해 해쉬코드가 나온다. 이 해쉬코드를 가지고 배열의 인덱스로 환산해서 값에 접근한다. 그렇기 때문에 해쉬코드만 알면 바로 값을 알 수 있어 검색 시 속도가 굉장히 빠르다. 키는 문자열, 정수, 파일값 등 다양한 입력 자료형이 올 수 있다. 해쉬코드는 항상 같은 길이의 값이 나오게 된다. collision??시간 복잡도 O(1)이지만 collision이 많을 경우 O(n)이다. collision은 동일한 인덱스 공간 안에 값이 여러 개가 있는 경우이다. 해쉬코드로 인덱스 접근을 했는데 보니까 n개의 값이 들어있다면 일일이 확인해야 하므로 최악의 경우 O(n)이다. 이런 문제를 해결하기 위해 값을 골고루 분산시키는 해쉬 알고리즘이 중요하다. 해쉬.. 이전 1 다음