본 포스팅은 아래의 출처를 참고하여 정리한 것입니다.
https://www.youtube.com/watch?v=PIidtIBCjEg&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=1

1. 배열(array) vs 리스트(list)

• [매우 기본, 중요] 가장 기본적인 순차적인(sequential) 자료구조

C언어: 배열

• 배열에서는 원하는 위치의 주소를 이용해 O(1) 시간의 읽고 쓰기 가능
• 즉, index로 특정 위치의 값을 상수 시간에 읽고 쓸 수 있는 두 개의 기본 연산을 제공하는 자료구조 ➡️ 배열

Python: 리스트

• 특정 위치의 객체에 값을 변경(더하기)할 때, 새로운 객체를 가리키며 값이 변경되는 것
• 연산자 종류

  • A.append(value): 맨 뒤에 value 삽입

  • A.pop(): 맨 뒤의 값을 지우고 리턴

    • A.pop(1): A[1]을 제거하고 리턴 ➡️ 비어 있는 자리는 한칸씩 왼칸으로 이동하며 채워짐

  • A.insert(1,10): A[1]에 10을 삽입

  • A.remove(value): A에서 value 제거 ➡️ 비어 있는 자리는 한칸씩 왼칸으로 이동하며 채워짐

  • A.index(value): value가 있는 위치 리턴

  • A.count(value): value의 횟수 리턴

리스트; 용량 자동 조절 (dynamic array)

• = capacity; "몇 개의 값을 저장할 수 있느냐"
• C에서는 dynamic array 지원 X

import sys
A = [] # 빈 리스트
print(sys.getsizeof(A)) # 28 bytes
A.append(1) # A = [10]
print(sys.getsizeof(A)) # 44 bytes

알아서 모자라면 늘리고, 남으면 줄인다!

배열과 리스트

• index로 임의의 원소를 접근
• 연산자 []: $O(1)$
• 삽입 연산자(append, insert): $O(1), O(n)$
• 삭제 연산자(pop, remove): $O(1), O(n)$

---

2. stack, queue, dequeue

• 제한된 접근(삽입, 삭제)만 허용

• stack: LIFO(Last in First Out), 선입후출

  • push, pop

• queue: FIFO(First in First Out), 선입선출
  

• dequeue: stack + queue

  • 값을 삽입할 때도 위/아래, 삭제할 때도 위/아래 모두 가능한 구조

3. 연결 리스트(Linked List)

• 파이썬의 리스트(=배열, 연속된 공간)와 완전히 다른 것
• 연속되지 않은 메모리 공간에 독립적으로 존재하고, 이들이 연결되어있다.
• index로 접근 X