Unsorted List (Linked Structure)

• Array vs Linked Structure

  • 일반적으로 array based structure이 linked structure보다 빠름
  • 다 O(1)인데, size, clear, destructor는 linked structure에서 O(N)

• Array vs Linked Structure (Memory Efficiency)

  • int type node는 8+바이트임
  • int는 4바이트 + 포인터는 4/8(x64)바이트
  • single int type data보다 8 byte 더 씀 → 비효율적
  • 노드 안에 저장된 데이터가 클수록 낭비되는 데이터 작음 (8 bytes for 1KB)

• Array vs Linked Structure (Scalability)

  • linked structure 장점 → Scalability (확장성)

  • 자료 구조의 사이즈가 변해서 array의 사이즈를 결정할 수 없을 때 사용 (ex. 카카오의 메시지 큐, 네트워크 트래픽 큐)

  • Linked structure는 computer에게 새로운 노드를 할당하고 delete하는 식으로 data의 size를 조절할 수 있게 함. → 메모리 관리에 효율적임

    → array가 좋은지, linked structure이 좋은지는 변동성과 저장되는 데이터의 사이즈에 따라 달라짐

• Linked Structure : Unsorted List

  • removeItem 할 때 삭제하는 노드 전 노드가 삭제하는 노드 다음 노드 가리키게 하고 싶을 때
    1. 한 아이템 앞에 꺼랑 비교
       1. (ex. (tempPtr→next)→value(7) != 3)
    2. tempPtr 이랑 deallocPtr 두 포인터를 만들어서 가리키게 함

Sorted List (Linked Structure)

• 나머지는 Unsorted list와 동일, insertItem, RemoveItem, findItem 만 다름

• findItem()

  • Linked structure에서 binary search 사용 불가 (index 문제)
  • linear search로 찾아야 함 → O(N)

• insertItem()

  • 들어갈 데 찾는 방법 : 넣을 아이템보다 큰 노드를 찾기

    → 한 아이템 앞이랑 비교하는 거