본문 바로가기

# 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