1. 연결리스트, linked list란?
각 노드가 데이터와 포인터를 가지고 떨어져 있는 데이터를 연결하는 형식으로 데이터 관리를 하는 구조. 도식으로 보면 아래와 같다.
2. 종류
- 단일연결리스트
- 이중연결리스트
3. Time Complexity
- 삽입과 제거는 데이터가 가지고 있는 포인터를 끊어주고 연결해주면 되기 때문에, O(1)의 시간복잡도를 가지지만, access와 search에는 모든 노드를 다 돌아봐야 하기 때문에 O(n)의 시간복잡도를 가진다.
4. 배열과의 차이점
- 배열은 메모리 사용량을 미리 정해주어야 하는 반면에 연결리스트는 동적으로 메모리를 사용할 수 있다.
- 데이터 재구성이 용이하다. 배열의 경우는 데이터 삽입 위치에 따라 indexing을 다시 해주어야 하는 경우가 있지만, 연결리스트는 데이터를 포인터로 연결만 해주면 됨.
always 2B#