[자료구조] 리스트, 스택, 큐

• 리스트
  • 배열 → random access 시 사용
    • k번째에 노드 추가/삭제: O(n-k) (n-k개의 값을 다 한 칸씩 밀어줘야 함)
    • 젤 앞이 오히려 큼 O(n-0)
    • random access가능 O(1)
    • • pointer
        • list에서 a=b를 하면 주소가 복사됨. → a = b.copy() 해야 값만 복사
  • 연결 리스트→ 삽입 삭제가 많을 때 사용
    • k번째에 노드 추가: O(k)
    • 젤 앞에 추가, 삭제: O(1)
    • k번째 값 acces 시 O(k)
• 스택 → 큐보다 자주 쓰임
  • Last in First Out 프링글스 - 추가&삭제 같은 곳
  • 삽입: push, 삭제: pop, 맨위의 값 보기: top
  • 아무것도 없는데 pop/top 하면 Underflow (오류)
  • 연결리스트로 구현 → 특정 쪽에서만 삽입,삭제 → push, pop, top : O(1)
  • DFS시 사용
  • ex) 올바른 괄호 문자열
  • 그냥 list 사용
• 큐
  • First in first out 셔틀콕통 - 추가&삭제 반대 편
  • 순서대로 일처리, BFS시 사용
  • 연결리스트로 구현 → 삽입,삭제 O(1)
  • from collection import deque → a = deque() 사용 ⇒ popleft 가 필요!
  • from queue import Queue → a = Queue()
  • 덱 (Deque)
    • 큐의 변형판 “Double-Ended-Queue”
    • 앞, 뒤 양쪽에서 삽입 & 삭제 가능