들어가며

이 글에선 python에서 주로 사용되는 자료구조인 List, Tuple, Set, Dictionary에 대한 기본 개념과, 장단점과 time complexity에 입각해 어느 상황에 사용하면 좋은지를 알아본다.

List

List는 python에서 가장 일반적으로 사용되는 자료구조이며, Dynamic Array 형태로 구현되어 있다.

l = [1,2,3]

주요특징 / 장단점

• ordered 되어 있다(순서가 있다).
• iterable 하다.
• mutable 하다.
• indexing이 가능하다.
• 순차적으로 저장이 가능하다.
• delete, remove 하는 cost가 비싸다.
  list의 중간에 존재하는 값을 지우게 될 경우 해당 값을 찾아 지우고, 나머지 값들을 앞으로 당겨야 하기 때문에 다른 구조에 비해 요소를 삭제하는 것이 느리다.
• resizing cost 또한 존재한다.

method

전체적으로 위와 같이 method의 time complexity를 띈다. 필요할 때 참고하자.

list를 선택하는 게 좋을 경우

요소가 중간에 추가 및 삭제가 자주 되지 않으며, 순서가 중요한 데이터의 경우! list를 사용하는것이 긍정적이다.

Tuple

Tuple은 list와 아주 비슷하며, 다만 immutable 하다.

t = (1, 2, 3)

주요특징 / 장단점

• ordered 되어 있다.
• iterable 하다.
• immutable 하다.
  다만 tuple에 들어있는 object는 mutable 하다.

method

앞서 나온 list의 method중 mutable하지 않은 method는 모두 사용 가능하며, time complexity 또한 동일하다.

Tuple을 선택하는 게 좋을 경우

보통 여러개의 값을 한번에 return 해 줄 때 그 형식으로 많이 이용한다.

Set

여러 distinct한 데이터를 담는 unordered 순열자료구조이다.

s = set{1,2,3}

주요특징 / 장단점

• unordered 되어 있다.
  따라서 들어오는 item이 순차적으로 저장되지 않는다
• iterable 하다.
• mutable 하다.
  그러나 set에 들어가는 object는 immutable 해야한다. 즉 list같은 mutable object는 들어갈 수 없다.
• 중복된 데이터가 존재하지 않는다.
• hash 기반으로 검색이 빠르다.

method

순서가 상관 없기에 O(1)인 method들이 list와 tuple에 비해 더 많다.

frozen set

a = fronzenset([])

immutable한 set을 frozenset method를 통해 만들 수 있다.

Set을 선택하는 게 좋을 경우

1차원적으로 중복된 값을 처리하기에 알맞다. 또, 자료구조의 lookup이 되게 빠르므로 검색이 자주 일어나는 경우에 사용하면 좋다.

Dictionary

unorder하게 mutable한 item을 저장하는 자료구조이며 key : value pair로 item을 저장한다.

d = {'a': 1, 'b': 3, 'c': 5}

주요특징 / 장단점

• unordered 이다.
• key : value pair
  가장 큰 특징이다. key에 value가 할당되는 형식으로 저장되며, 따라서 key를 통해 value를 얻는다.
• key는 중복되지 않는다.
• key는 immutable 객체여야 한다.
• hash를 사용하여 검색한다.

method

Dict를 선택하는 게 좋을 경우

key와 value mapping을 지속적으로 유지해야 할 때, 즉 해당 key에 대한 value를 각각 관리해야하는 경우 유용하다.

마무리

위 내용을 요약해서 하나의 표로 나타내면 다음과 같다.