[알고리즘] 링크드 리스트에 대해 알고가야 할 것.. 의견 나눠주세요

이 글은 '뇌를 자극하는 알고리즘 - 박상현 저', 이것만은 알고 갑시다에서 나온 내용입니다.

(문제가 된다면 바로 내리겠습니다.)

1. 링크드 리스트와 배열의 성능을 다음 세 가지 연산에 관해 비교하여 설명하세요.

• 삽입
  
• 삭제
• 탐색

- 링크드 리스트가 삽입/삭제 연산에서 보자면 배열보다 더 빠르다는 것에서는 장점이지만 역으로 특정 위치에 있는 노드를 찾는 것은 배열에 비해 느리다고 할 수 있다...

2. 환형 링크드 리스트의 장점은 헤더 노드를 이용하여 테일 노드의 위치를 바로 파악할 수 있다는 것입니다. 그럼 링크드 리스트나 더블 링크드 리스트에서 환형 링크드 리스트에서처럼 바로 테일 노드의 위치를 알아내게 할 수는 없을까요? 그 방법을 생각해보고 설명하세요.

- (아직 생각이 안 떠오르니... 좋은 생각이 있으신 분들은 답 달아주시길 바랍니다!)

3. 1장에서 구현한 리스트 예제 프로그램들은 노드 개수를 알아내는 방법이 굉장히 비효율적입니다. 노드의 수가 N개라면 N개의 루프를 수행해야 비로소 N을 알 수 있습니다. 노드의 수를 즉시 알아낼 수 있는 방법은 없을까요? 다음 사항을 중심으로 개선 방법을 생각해보고 설명하세요.

- (공백... ㅎ)