연결 리스트 (Linked list)
연결 리스트 구조는 앞에서 말한 세 가지 구조와 달리 메모리에 있는 데이터의 물리적 배치를 사용하지 않는 데이터 구조다. Index나 위치보다 참조 시스템을 사용한다. 각 요소는 노드라는 것에 저장되는데, 다음 노드 연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장된다. 모든 노드가 연결된 때까지 반복이 돼서 노드의 연결로 이루어진 자료 구조다. 그리고 이 구조는 데이터 추가 및 삭제 시 재구성이 필요 없어서 효율적이다.
연결 리스트에는 단일 연결리스트(Singly-Linked List), 이중 연결리스트(Doubly-Linked List)등의 종류가 있다.
장점
- 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다.
- 배열처럼 메모리에 연속적으로 위치하지 않는다.
- 배열처럼 구조의 재구성이 필요없다.
- 동적인 메모리 크기
- 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리에 적합
단점
- 배열보다 메모리를 더 사용한다.
- 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 검색/가져온다.
- 노드를 반대 방향으로 검색할 때 비효율적이다.(이중 연결리스트의 경우)
사용
- 메모리 크기가 정해져 있지 않을 때
- 데이터를 연속적으로 빠르게 삽입/제거가 필요할 때
- 이미지 뷰어, 갤러리
- 음악 플레이어
1. 단일 연결리스트(Singly-Linked List)
2. 이중 연결리스트(Doubly-Linked List)
3. 원형 연결리스트(Circular-Linked List)
