단일 연결 리스트
단일 연결 리스트 역시 배열과 마찬가지로 삽입, 삭제, 탐색이 모두 가능한 자료구조 입니다.
- 탐색: Head부터 Tail까지 일일이 확인해야 하므로 O(N) 이라는 시간이 소요됩니다.
- 삽입과 삭제: 단일 연결 리스트에서는 삽입, 삭제의 경우 인접한 곳의 선을 끊고 연결해주는 작업만 해주면 되므로 O(1) 이라는 시간이 소요됩니다.
- 단, 일방향으로만 진행되기 때문에 뒤로 돌아갈 수 없는 구조임에 유의합니다.
이중 연결 리스트
이중 연결 리스트는 단일 연결 리스트와 달리 각 노드가 이전 노드와 다음 노드에 대한 포인터를 모두 가지고 있는 자료구조입니다.
- 탐색: 단일 연결 리스트와 마찬가지로 탐색은 Head부터 Tail 또는 Tail부터 Head까지 일일이 확인해야 하므로 최악의 경우 O(N)의 시간이 소요됩니다.
- 삽입과 삭제: 특정 위치의 노드를 알고 있다면, 이전 노드와 다음 노드의 포인터를 재설정하기만 하면 되므로 O(1)의 시간 복잡도로 처리할 수 있습니다.
- 양방향 탐색: 이전 노드와 다음 노드에 대한 포인터를 모두 가지고 있기 때문에, 탐색 방향이 자유롭고, 뒤로 돌아가는 작업도 가능합니다.
- 메모리 사용량: 각 노드가 두 개의 포인터를 가지므로, 단일 연결 리스트에 비해 추가적인 메모리가 필요합니다.
