알고리즘
연결 리스트/Linked list
연결 리스트란?연결 리스트란 쉽게 말해 원소를 저장할 때, 그 다음 원소의 위치를 같이 저장하는 선형 자료구조이며, 이때 원소들은 붙어있지 않고 흩어져있다. 연결 리스트를 사용했을때의 주요 시간 복잡도는 다음과 같다.k번째 원소를 확인/변경하기 위해서는 O(k)가 필요함=> 해당 연산을 반복 수행해야하는 경우, 연결 리스트보다 배열이 효율적(배열은 O(1))임의의 위치에 원소를 추가/제거는 O(1)이 필요함=> 해당 연산을 반복 수행해야하는 경우, 배열보다 연결 리스트가 효율적(배열은 O(N)) 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원..
2023. 11. 2. 02:20