본문 바로가기

# Foundation/자료구조

이중 연결 리스트

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

    https://github.com/AeroCodeX/

이중 연결 리스트

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




원형 이중 연결 리스트



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




이중 연결 리스트의 특성

  • 데이터가 메모리 위에서 인접하지 않는다.
  • 논리적 수용량의 제한이 없다.

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

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

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


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

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


'# Foundation > 자료구조' 카테고리의 다른 글

스킵 리스트  (0) 2019.02.03
벡터  (0) 2019.02.02
단일 연결 리스트  (0) 2019.01.31
배열  (0) 2019.01.31
자료구조와 추상적 자료형  (0) 2019.01.31