[Python] 기초적인 자료구조(feat. 배열, 연결 리스트)

우선, 자료구조란 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공하는 형태를 의미한다.

자료구조는 추상적 자료형(자료와 그 자료에 대한 연산을 개념적으로 정의만 한 것)을 구체적으로 구현한 결과라고 표현할 수도 있다.

즉, 리스트(파이썬의 자료 type 중 리스트와는 다름), 스택, 큐, 트리 등의 명칭과 그 구조의 개념은 추상적 자료형에 속하고, 이를 실제로 사용할 수 있도록 모듈, 클래스 등을 통해 구현한 것 또는 이를 구현하는 도구가 되는 것(배열, 연결 리스트 등)을 자료구조라고 생각하면 된다.

이 글에는 대표적인 자료구조(배열, 연결 리스트)의 구조 개념, 장단점과 함께 이를 구현한 코드를 정리했다.

 

1. 배열(Array)

자료를 추가하려고 할 때

자료가 추가된 후

배열은 절대적인 순서에서 인덱스(위치)를 통해 조회가 가능하기 때문에 인덱스를 알고 있다면 빠른 자료 탐색에서 연결 리스트보다 유리하다. 대신 삽입, 삭제 등의 연산을 할 때는 이후의 모든 인덱스가 밀려나거나 당겨지게 되기 때문에 연결 리스트에 비해 느리다.

배열은 파이썬에서 별도의 라이브러리나 구현 없이 리스트라는 type으로 구현되어 있기 때문에, 이를 이용하면 된다.

 

2. 연결 리스트(Linked List)

자료를 추가하려고 할 때

자료를 추가한 후

연결 리스트는 여러 개의 '노드'를 저장하는 방식으로 구현한다. 여기서 노드는 자료(값 자체)와 포인터(자신의 다음 순서의 노드)를 가진다. 특정 위치의 자료를 찾는 것(조회)은 번거롭다. 대신 상대적인 순서를 갖기 때문에 자료의 삽입과 삭제를 수행할 때 배열에 비해 유리하다는 장점이 있다.

이를 구현한 소스 코드(<Do it! 자료구조와 함께 배우는 알고리즘 입문> 참조)는 아래 깃허브 주소에 있다.

책을 참조한 연결 리스트: https://github.com/sjan137/my_useful_python_module/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/linked_list.py

 

3. 장단점 비교

즉, 배열과 연결 리스트의 장단점을 정리하면 아래와 같이 각각의 장점이 서로의 단점이 되는 관계를 가진다. 이를 잘 알고, 다른 추상적 자료형을 구현하거나 이용할 때 상황에 맞는 자료구조를 사용할 줄 알아야 한다. 설명의 오른쪽에는 시간 복잡도를 작성한 것이다.

	배열(Array)	연결 리스트(Linked List)
장점	특정 위치의 자료 탐색 - O(1)	자료의 삽입과 삭제 - O(1)
단점	자료의 삽입과 삭제 - O(N)	특정 위치의 자료 탐색 - O(N)

 

4. 참고

원래 리스트라는 자료형 자체는 일렬로 나열된 추상적 자료형을 의미한다. 이 자료형은 조회, 삽입, 삭제 등의 연산이 가능하며, 파이썬에서 의미하는 자료형 type인 리스트와는 다르다. 위의 배열, 연결 리스트 등이 리스트라는 추상적 자료형을 구현한 형태이다.