[기초 알고리즘 #03][선형 자료구조] 배열 / 리스트

지난 포스트에서는 선형 자료구조 중 스택 / 큐 / 덱, 이 세 가지에 대해 알아보았습니다.

이번 포스트에서는 아래 이미지를 다시한번 참고해보면서,

선형 자료구조중 정적자료구조에 해당하는 배열(Array)과 동적자료구조에 해당하는 리스트(List)를 공부해보겠습니다.

그리고 Python 언어에서 어떻게 사용되고 있는지도 알아보구요 😶

( 이미지 출처 : https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS2832062046 )

1. 배열 (Array)

배열은 연속된 메모리 공간에 동일한 자료형의 데이터들이 나열되어 저장되는 정적자료구조입니다.

프로그램이 시작될 때, 담길 수 있는 데이터 타입과 크기가 정해져 있는, 고정된 자료구조라는 뜻이죠.

컴퓨터 메모리에 덩어리(Chunk)채로 공간이 할당되는 모습 덕에 ‘Chunk Data’라고 불리기도 합니다.

위 이미지는 int[5] arr = {1, 4, 7, 12, 3}이라는 코드(C언어)가 실행될 때의 모습입니다.

코드에서 정의한 size 값 5 그대로 메모리에 할당된 모습을 볼 수 있습니다.

좀 더 자세히 봐볼까요?

배열에 담긴 각각의 값은 요소(Element)라고 하며, 요소값을 가리키는 번호를 인덱스(index)라고 합니다.

이 때, 우리는 인덱스 번호를 통해 원하는 요소 값을 꺼낼 수 있습니다.

arr[1]은 1번 인덱스에 담긴 데이터 4를 뜻하게 되며, 이를 인덱싱(indexing)이라고 합니다.

2. 리스트 (List)

배열처럼 덩어리채로 메모리에 할당한다면, 데이터를 유동적으로 추가하고 삭제하기 어렵겠죠?

그래서 동적으로 데이터를 추가하고 삭제하기 위해 고안된 ADT가 리스트(List)입니다.

리스트는 선형자료구조이자 동적자료구조입니다.

“연속된 임의의 데이터들을 모델링한 추상자료형”이라고 정의할 수 있구요.

개념적으로 ADT이기 때문에 구현 방식이 다양할 수 있지만, 대부분 노드와 포인터의 개념을 활용해 연결리스트(Linked List)의 형태로 구현됩니다.

위 이미지에서 볼 수 있듯이, 데이터와 다음 노드의 메모리 주소(포인터)를 담은 데이터 덩어리를 노드라고합니다.

노드에 담긴 다음 노드의 메모리 주소를 통해 다음 노드와 마치 연결된 것 처럼 구조화한 자료구조이죠.

만약 중간에 다른 데이터를 끼워넣고 싶다면 위 이미지처럼 메모리 주소를 교체해주기만 하면 됩니다.

3. 배열과 리스트 정리

[배열]

1. 프로그램이 시작될 때(배열이 선언될 때), 고정된 크기의 연속된 메모리 주소 할당합니다.
2. 각 공간에 부여된 번호 인덱스를 통해 실제로 담긴 값 요소를 사용할 수 있습니다.
3. 이 덕분에 원하는 인덱스에 임의로 바로 접근 할 수 있는 Random Access가 가능하기 때문에 데이터를 획득 속도가 빠릅니다.
4. 같은 자료형의 데이터만 담길 수 있습니다.
5. 크기를 변경할 수 없기 때문에, 데이터 삽입과 삭제에 비용이 많이 소모 됩니다.

[리스트]

1. 연속적 임의 데이터들을 모델링한 추상자료형 입니다.
2. 노드와 포인터의 개념을 이용해 연결 리스트의 형태로 구현합니다.
3. 배열처럼 연속된 메모리의 집합이 아니기 때문에, Random Access가 불가능하므로 제일 앞 노드 부터 요소를 탐색 합니다.
4. 다양한 자료형의 데이터를 담을 수 있습니다.
5. 동적자료구조이기 때문에, 데이터 삽입과 삭제가 자유롭습니다.

4. 파이썬의 리스트

파이썬에서는 정적자료구조가 존재하지 않습니다.

대신 배열과 리스트의 장점을 섞은 파이썬 자체 동적자료구조인 리스트를 사용합니다.

배열처럼 연속된 메모리 공간을 사용하지만, 동적으로 데이터를 처리할 수 있도록 설계되어 있습니다. (참고자료 링크)

• 초기 선언시 크기를 지정하지 않아도 됩니다.
• 초기 선언시 저장할 변수의 자료형을 지정하지 않아도 됩니다.
• 서로 다른 자료형의 데이터를 섞어서 담을 수 있습니다.

그럼 한번, 파이썬의 리스트를 표현하고 사용하는 방법을 알아 볼까요?

# 리스트 정의
## 리스트명 = [요소1, 요소2, 요소3]
arr = [1, True, 7, "안녕", 3]

# 인덱싱
## 리스트명[인덱스값]
print(arr[0]) # 1
print(arr[1]) # True
print(arr[3]) # 안녕

비어있는 리스트는 아래처럼 표현할 수 있습니다.

arr = []
arr = list()

파이썬의 리스트는 인덱싱 외에도 범위와 스텝을 정해 리스트를 덩어리채 자를 수 있는 슬라이싱(slicing)기능도 제공합니다.

arr = [1, True, 7, "안녕", 3]

# 슬라이싱
## 리스트명[(시작):끝:(스텝)]
print(arr[3]) # [1, True, 7]
print(arr[1:3]) # [True, 7]
print(arr[1:4:2]) # [True, "안녕"]

객체지향언어인 파이썬의 특성상, 리스트는 자료는 모두 객체(Object)입니다.

이에따라, 인덱싱, 슬라이싱 외에도, 리스트 객체의 내장함수(built-in method)를 활용하여 다양한 기능을 구현할 수 있습니다.

⚫ 연습해볼 수 있는 문제

1. 백준 1546 평균 » 링크
2. 백준 10813 공바꾸기 » 링크

⚫ 참고 자료

1. 자료구조의 개념과 종류. 한빛출판네트워크. https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS2832062046

2. Array Data Dtructure Guide. geeksforgeeks. https://www.geeksforgeeks.org/array-data-structure-guide/

3. 자료구조 04 : 리스트ADT. LeeWonjin. https://velog.io/@yiwonjin/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-04-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8

4. listobject.c. CPython Github. https://github.com/python/cpython/blob/main/Objects/listobject.c

---