단일 연결 리스트

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

    https://github.com/AeroCodeX/

단일 연결 리스트

데이터가 노드라는 작은객체에 저장되며,

다음 노드의 주소를 가지고 있지만,

이전 노드의 주소는 가지고 있지 않은 저장방식.

원형 단일 연결 리스트

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

단일 연결 리스트의 특성

• 데이터가 메모리 위에서 인접하지 않는다.
• 논리적 수용량의 제한이 없다.
• 어느 위치든 데이터를 빠르게 삽입/제거할 수 있다. (상수시간)
• 중간이나 마지막 위치의 데이터를 얻는것은 느리다.  (선형시간)
• 처음 위치에서 데이터를 얻는것은 빠르다.  (상수시간)

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

• 마지막 데이터를 조회하는데 시간이 오래 걸린다.

• 첫 부분만 조회할 것 이라면, 성능상 불이익이 많이 없다.

• 배열과 달리 수용량으로 인한 오버헤드가 거의 없다.
  

• 중간지점에서 데이터를 삽입/삭제 하더라도 오버헤드가 거의 없다.