• Array(List) <a1, a2, … , an> head tail
    • implementation

      • Array - based Insert, delete, locate : O(n)

        Untitled

      • Pointer-based Linked List(One-way) Insert, delete: O(1) locate, retrieve: O(n)

        Untitled

      • Cursor-Based Cursor=simulated pointer: indicating positions Insert, delete: O(1) retrieve: O(n)

        Untitled

  • Stack Special type of list LIFO: Last in First Out(후입선출) Properties: Top, Push, Pop
    • Implementations

      • Array based

        Untitled

      • Linkded stack ex) Call stack(함수 호출 스택)

  • Queue FIFO: First in First Out(선입선출) Properties: Front, Rear, Enqueue, Dequeue
    • Implementations
      • Array-Based Enqueue, Dequeue: O(1) or O(n) *Problem: Drifting queue problem: 한칸씩 전부 움직여야 함
      • Array-Based Circular Queue Connect last element and first element →Drifting Queue solved *Problem: How to recognize empty Queue? →Count elements
      • Linked Queue Pointer Front, Rear indicates first and last element Use dummy Header Node