각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 메모리가 연속적일 필요가 없으므로 메모리 낭비가 적음
- 포인터만 수정하면 되기 때문에 데이터의 추가와 삭제가 빠름
- 데이터를 조회할 때 포인터들을 따라 앞에서부터 순회하기 때문에 느림
- array list와 linked list의 관계는 trade-off이기 때문에 특징에 따른 선택이 중요함
- 가장 단순한 형태의 연결 리스트
- 단방향이기에 중간의 Head 주소가 잘못 되면 뒤쪽 자료들을 찾을 수 없음
- 다음 노드의 주소와 이전 노드의 주소를 모두 가지고 있는 연결 리스트
- 단일 연결 리스트보다는 손상에 강하지만 삽입이나 정렬의 경우 작업량이 더 많다는 단점이 있다.
- 단순 연결 리스트에서 마지막 원소가 Null이 아닌 첫 원소를 가리키는 연결 리스트
- 스트림 버퍼나 큐를 사용하는데 사용
- 배열과 연결 리스트의 장점을 합친 것
- 연결 리스트의 원소가 배열
- 청크 리스트의 발전형이 B+tree