연결리스트는 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 물리적으로 메모리 상에 이곳 저곳에 흩어져있다

1. 연결리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함

다음 그림은 원소 A,B,C,D를 저장하는 연결리스트이다. 만약 D를 찾고 싶으면 A부터 차례대로 접근해서 D를 찾아야 한다. 배열과 다르게 연결리스트는 메모리 상에 연속적으로 위치하고 있지 않기 때문이다.

2. 임의의 위치에 원소를 추가/제거는 O(1)

하지만 배열과 다르게 임의의 위치에 원소를 추가/제거하기가 매우 용이하다.

3. 원소들이 흩어져 있기 때문에 Cache hit rage가 낮지만, 할당이 다소 쉬움

2. 종류

1. 단일 연결 리스트(Singly Linked List) : 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트이다.

2. 이중 연결 리스트(Doulby Linked List) : 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있다. 단일 연결 리스트에 비해 메모리를 더 사용한다. STL에 존재하는 연결 리스트인 list는 이중 연결 리스트로 되어있다.

3. 원형 연결 리스트(Circular Linked List) : 원소의 끝과 처음이 연결되어 있다.

3. 배열과 연결 리스트

4. 관련 문제

에디터
https://www.acmicpc.net/problem/1406

키로거
https://www.acmicpc.net/problem/5397

요세푸스 문제
https://www.acmicpc.net/problem/1158

5. 참고 사이트

https://blog.encrypted.gg/932?category=773649