이중 연결 리스트

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

이중 연결 리스트

이전 노드의 정보도 갖고있는 연결 리스트.

원형 이중 연결 리스트

맨 마지막 노드가 다시 첫 노드를 가르킨다.

이중 연결 리스트의 특성

• 데이터가 메모리 위에서 인접하지 않는다.

• 논리적 수용량의 제한이 없다.

• 어느 위치든 데이터를 빠르게 삽입/삭제할 수 있다.  (상수시간)

• 중간에 위치한 데이터를 가져오는 것은 느리다.  (선형시간)

• 처음이나 마지막 위치에서 데이터를 가져오는 것은 빠르다.  (상수시간)

이중 연결 리스트로 구현한 인터페이스의 특성

• 중간지점의 데이터를 조회하는데 시간이 오래 걸린다.
• 처음 또는 마지막 부분만 조회할 것 이라면, 성능상 불이익이 많이 없다.
• 배열과 달리 수용량으로 인한 오버헤드가 거의 없다.
  
• 중간지점에서 데이터가 삽입/삭제되더라도 오버헤드가 거의 없다.