[지식/이론][python] 리스트(list)

개요

컴퓨터 과학에서 배열(array)은 여러 요소(element)들이 연속된 메모리에 순차적으로 저장되는 간단한 구조를 일컫는다.

연결 리스트(linked list)는 독립적으로 분리된 여러 개의 노드(node)가 서로 연결되어 있는 구조이다. 배열과 연결 리스트 모두 어떤 요소 또는 노드에 직접 접근할 때 시간적 측면에서 모두 효율적이나, 배열의 시간복잡도(time complexity)는 O(1), 연결 리스트는 O(n)이다. (시간 복잡도라는 개념은 나중에…) 연결 리스트는 특정 노드에 접근하려면 처음부터 순회하여 검색해야하기 때문이다.

그러나 어떤 노드를 삽입하고자 할 때 삽입하고자 하는 위치를 정확히 안다면 노드 수에 관계없이 시간복잡도는 O(1)이다. 반면, 배열에서 특정 위치에 요소를 삽입하고자 한다면 그 위치에 있는 기존 요소와 그 오른쪽에 있는 모든 요소들을 한 칸씩 오른쪽으로 옮겨야 하기에 시간복잡도는 O(n)이다.

즉, 어떤 요소(또는 노드)에 직접 접근, 즉 검색하고 읽어오는 것은 배열이 좀 더 효율적이나, 데이터를 입력하는 측면에서는 연결 리스트와 배열이 똑같이 효율적이거나 아니면 연결 리스트가 더 효율적일 수 있다.

파이썬에서 배열과 유사한 객체는 리스트(list)이다. 파이썬에서의 리스트는 그 크기를 동적으로 조절할 수 있는 배열이다. 즉, 처음 정의한 크기를 그대로 유지해야만 하는 것은 아니라는 것이다. (처음에는 [1, 2, 3]이었다가 나중에는 [1, 2, 3, 4, 5]로 변경 가능한 것처럼) 파이썬에서의 리스트는 연결 리스트와 전혀 다르다.

리스트는 가변형 객체이다.

리스트 끝에서 요소 추가 또는 제거 시 사용되는 메서드인 append(), pop()의 시간복잡도는 O(1)이며, 리스트 내 요소 검색이 필요한 remove(), index() 메서드와 멤버십 테스트 in 등의 시간복잡도는 O(n)이다. insert() 메서드는 지정된 인덱스에 요소를 삽입하고, 기존에 있던 요소들은 모두 한 칸씩 오른쪽으로 옮겨야 하므로 시간복잡도는 O(n)이다. → apppend()는 그냥 무조건 리스트의 맨 오른쪽에 요소를 삽입하면 되지만 insert()는 지정된 위치에 삽입해야해서 시간복잡도에서 차이가 발생하는 것 같다.

검색 또는 멤버십 테스트 시 빠른 작업 속도를 원하면 set, dictionary와 같은 컬렉션 자료형이 더 적합할 것이다. (컬렉션 자료구조는 다음에 언급)

리스트에서 요소들을 순서대로 정렬하면 좀 더 빠르게 검색할 수 있다.

파이썬에서, del문 또는 리스트의 remove() 메서드 등으로 객체 참조를 삭제하고, 더 이상 어떤 객체도 특정 데이터를 참조하지 않으면 파이썬에서는 해당 데이터를 가비지 컬렉터(garbage collector)에 수집한다. 여기서 컴퓨터 과학에서의 garbage는 더 이상 참조되지 않으면서도 메모리 공간을 차지하는 객체를 의미한다. garbage collection은 이러한 메모리를 자동으로 관리하는 기능이다.

리스트 메서드들의 시간복잡도

다음은 리스트 메서드 및 리스트에 적용할 수 있는 각종 연산들의 시간복잡도를 나타낸 테이블이다.다음 테이블에서 n은 리스트 내 총 요소의 수 (len(list))이고, k는 연산(조회 및 추가) 항목 수다.

메서드	시간복잡도
인덱싱 접근. ex) list[3])	O(1)
인덱스 할당. ex) list[3] = ‘hi’)	O(1)
append()	O(1)
pop()	O(1)
pop(idx)	O(n)
insert(idx, element)	O(n)
del .ex) del list[2])	O(n)
in .ex) element in list)	O(n)
슬라이스 조회. ex) list[a:b]	O(k)
reverse()	O(n)
두 리스트 연결. ex) alist + blist	O(k)
sort()	O(n log n)

---

Reference

[1] 지은이: 미아 스타인, 옮긴이: 최길우, “파이썬 자료구조와 알고리즘”, (2019, 한빛미디어)

This content is licensed under CC BY-NC 4.0