• 원소를 저장할 때 다음 원소의 위치를 포함하는 방식으로 저장하는 자료구조. 원소들은 이곳 저곳에 흩어져 있다.

연결 리스트의 성질

1. k번째 원소를 확인하기 위해선 O(k)의 시간이 필요함. (배열과 다르게 원소들이 연속해서 위치하고 있지 않다.)
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결 리스트의 종류

1. 단일 연결 리스트: 각 원소가 다음 원소의 위치를 알고 있는 연결 리스트
2. 이중 연결 리스트: 각 원소가 다음 위치의 원소와 다음 위치의 원소 둘다 알고 있는 연결 리스트
3. 원형 연결 리스트: 끝이 처음과 연결 되어 있는 연결 리스트

배열 vs 연결 리스트

• 배열과 연결 리스트 모두 선형적 자료구조이다.
• 트리, 그래프, 해쉬 등은 비 선형적 자료구조의 예시이다.
• 배열은 overhead가 필요없지만 연결리스트는 이전 원소, 다음 원소 등의 주소값을 저장하기 위해 O(N)만큼 필요하다.

STL list의 사용법

• header: #include <list>
• list<Type>::iterator t; 현재 LinkedList가 가리키는 곳 (auto t = LinkedList.begin() 등으로 선언하면 효율적)
• list<Type> L = {n, m}; LinkedList 선언 방식