5.4 Linked Structures- Unsorted and Sorted List

생성일: 2021년 10월 15일 오후 10:46

기존의 unsorted and sorted list를 Linked Structure로 구현

Unsorted List in Linked Structures

• Array로 구현한 list와 다르게 인덱싱이 힘들다.
• 바이너리 서치가 힘들다.
• 중간에 있는 아이템을 지울 때 (DeleteItem)
  • 다음 노드와 지울 아이템을 비교하여 찾는다.
  • 이중 포인터 접근을 통해 (location→next)→info 를 수정한다.
  • 이 과정은 list의 제일 첫 번째 노드는 확인하지 않으므로 첫번째 노드는 반복문 전에 직접 확인해 주어야 한다.
  • 구현한 코드의 단점 : 지우고자 할 아이템이 무조건 list안에 있어야 함

Array와 Linked로 구현한 Unsorted List 비교

Sorted List in Linked Structures

• Unsorted List와 유사
• RetrieveItem에서 Array로 구현한 Sorted List와 다르게 바이너리 서치 사실상 불가능
• 정렬을 하기 위해 반복문을 도는데 이때 다른 Linked Structures들과는 다르게 자신의 앞의 아이템을 가르키는 포인터 변수가 필요 함.
• 중간에 있는 아이템을 지울 때 (DeleteItem)
  • Unsorted List의 DeleteItem과 동일

Array와 Linked로 구현한 Sorted List 비교