[Python] 코딩테스트를 위한 리스트(List) 정리

이번 포스팅은 코딩 테스트를 준비하며 공부했던 파이썬의 리스트에 대한 내용입니다.

---

| List

- 파이썬의 리스트는 항상 써왔지만 자세하게 알고 쓰는 게 아닌 집합으로 그냥 써왔던 것 같습니다. 하지만 코딩 테스트를 준비하며 리스트에 대해 자세히 정리해보고자 합니다.
- 리스트는 말 그대로 순서대로 저장하는 시퀀스이며 mutable 한 자료형입니다. 입력 순서가 유지되며 내부적으로는 동적 배열로 유지되어 있는데 C++의 std::vector나 java의 ArrayList와 같은 자료형입니다.
- 파이썬을 조금 더 파이썬스럽게 만들어주는 리스트 자료형은 다양한 기능들을 제공합니다. 특히 코딩 테스트에서 스택과 큐 사용에서 고민을 하지 않아도 되며 스택, 큐에서 사용하는 연산들을 모두 리스트에서 사용할 수 있으니 다른 언어에 비해 유리하다는 말이 여기서 나오지 않았나 생각합니다.

---

| List 연산의 시간 복잡도

- 리스트는 기능을 다양하게 제공하면서 시간 복잡도 O(1)에 실행 가능한 연산들도 있습니다.

- 이렇게 리스트의 다양한 연산과 시간 복잡도를 정리했습니다. a.pop(0)은 큐의 연산인데 전체 복사가 필요해 O(n)입니다. 큐 연산은 보통 deque를 사용하는 이유가 O(n)의 시간 복잡도 때문입니다.

---

| List 특징

- 파이썬의 리스트는 배열의 장점과 연결 리스트의 장점을 모두 가지고 있는 것처럼 강력한 기능을 제공합니다.
일반적으로 배열이라 하면 같은 자료형으로만 이루어진 값을 연속된 메모리에 저장하는 것을 뜻하는데 파이썬에서 리스트는 서로 다른 자료형을 같은 리스트에서 관리하는 게 가능한데 이는 파이썬의 리스트가 연결 리스트에 대한 포인터 목록을 관리하기 때문입니다.
- a = ['a'. 1. True] 이 처럼 정수, 문자, 불리언 모두 다른 자료형을 a라는 리스트에서 저장하는데 이런 특징은 강력하지만 각각의 자료형의 크기가 다르기 때문에 연속된 메모리에 할당하는 것은 불가능합니다. 결국 객체에 대한 참조로 구현할 수밖에 없습니다. 파이썬은 강력한 기능을 가지지만 속도에서 희생한 측면이 있는 게 바로 이런 면입니다.

---

코딩 테스트를 준비하며 리스트에 대한 조금 더 깊은 공부와 시간 복잡도에 대해 알아봤습니다.
평소 아무 생각 없이 리스트를 사용해 왔는데 확실히 좀 더 공부하니 모르는 내용도 많네요.
질문이나 틀린 점이 있으면 댓글로 남겨주세요

다음 포스팅으로 찾아오겠습니다

감사합니다 :)