• 데이터를 담는 그릇
  • 자료를 담는 구조
  • 각각의 목적에 맞춰 사용해야 최대의 효율
• 무수히 많은 자료구조 존재
  • 적절히 사용하면 효율적인 알고리즘 사용할 수 있게 함

1. 배열

• 데이터
  • 데이터를 연속적으로 저장 → Random Access 가능
  • 길이가 변하지 않음
  • 길이가 변하는 동적배열도 있음
• 명령
  • insert(i, v) = i번째 자리에 v값을 삽입 O(N)
  • delete(i) = i번째 자리에 있는 값을 삭제 O(N)
  • get(i) = i번째 자리에 있는 값을 조회 O(1)

2.연결 리스트(Linked list)

• 데이터
  • 데이터를 비연속적으로 저장 →Random Access 불가능
• 명령
  • insert(it, v) = it이 가리키는 곳에 v값을 삽입 O(1)
  • delete(it) = it이 가리키는 곳에 있는 값을 삭제 O(1)
  • get(i) = i번째 자리에 있는 값을 조회 O(N)
• 다른 자료구조들을 구현할 떄 많이 쓰임
• 파이썬은 직접 구현 해야함

3.스택(Stack)

• 데이터

  • LIFO 구조(선입후출)

• 명령

  • push(v) → 최상단에 v 값 삽입
  • pop() → 최상단 값 제거
  • top() → 최상단 값 조회

• 스택은 배열의 부분집합이다.

• 스택으로 불가능한 연산이 되면 스택이 아님