[바킹독의 실전 알고리즘] 0x04강 - 연결리스트
·
Computer Science/자료구조 | 알고리즘
연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조 ex. 메모장 성질 k번째 원소를 확인 / 변경 -> O(k) 필요 첫 번째부터 순차적으로 방문해야 함 (첫 번째 원소의 주소만 알고 있음) N개의 원소 -> 평균적으로 2/N 시간 => O(N) 임의의 위치에 원소 추가 / 임의 위치의 원소 제거 -> O(1) 다음 원소의 주소만 변경해주면 됨 (추가하고 싶은 위치의 주소를 알고 있는 경우) 원소들이 메모리 상에 연속 X -> Cache hit rate ↓ But, 할당 다소 쉬움 배열 vs. 연결리스트 -> 선형 자료구조 vs. 비선형 자료구조: 트리, 그래프, 해쉬 종류 단일 연결 리스트(Singly Linked List) 각 원소가 다음 원소의 주소를 들..
