자료구조를 공부하는 두번째 단계
배열과 리스트
파이썬의 리스트는 자료구조가 아닙니다
이 문장은 오늘 하루 나를 끊임없이 괴롭혔다. 하지만 결론부터 말하자면, 이 문장이 의미하는 바를 이해하려고 노력한 덕분에 '배열'과 '리스트' 에 차이가 있다는 것을 깊이 알게 되었고, c와 js, java 에서 각각 배열과 리스트를 다루는 방법이 다르다는 것까지 알게 되었다. 본래는 리스트의 종류와 정렬알고리즘 예시 한두개 정도까지 공부한 내용을 적으려고 계획했었지만, 고민이 깊어져서 진도는 많이 나가지 못했다. 그래서 오늘은, '파이썬의 리스트가 자료구조가 아닌 이유'에 대해 고민하는 과정에서 세운 3가지 추론과 마지막으로 얻은 결론에 대해 적어보겠다.
추론 1. 파이썬의 리스트 구조에는 리스트 객체가 아니라 배열만 있다.
네... 그것은 말이 되지 않는 것이구요? 파이썬 코드를 많이 만들어보지는 못했지만 당장 '파이썬 리스트' 라고 검색만 해봐도 파이썬의 리스트 자료형의 개념과 리스트에 자료를 넣고 수정하고 제거하기 위한 다양한 함수들이 소개되고 있었다.
https://wikidocs.net/14 (점프투 파이썬 리스트 자료형)
그래서 이 추론은 두말 할 것 없이 틀린 추론이었다. 오히려 파이썬의 리스트 자료구조에 배열은 없고 리스트만 있다고 했다면 모를까.
추론 2. 파이썬의 '리스트'라는 객체는 자료구조가 아니라, 엄밀히 말해서 자료형이다.
자료형과 자료구조는 동일한 의미가 아니기 때문에 이런 추론을 하게 되었다. 그러나 자료구조와 자료형을 구분하는 속성은 탐색, 삽입, 삭제연산이 내부 메소드로 구현되어있는지에 달려있는데, 파이썬의 리스트는이 이 세가지 연산을 메소드로 제공하는, 자료형이자 자료구조라는 것을 알게 되었다. 즉 이것도 아니었다.
https://wikidocs.net/33825 (파이썬 자료구조 알고리즘)
추론 3. 배열과 리스트가 파이썬에서는 동일하다.
결론적으로 이 추론이 가장 근접한 추론이었다. 파이썬에서는 리스트가 배열의 역할(기능)까지 가지고 있는 것이었다.
원래는 배열과 리스트는 이터러블한 속성을 갖는(범위를 갖는, 내부요소들을 반복할 수 있는) 유사한 객체이면서도 본질적으로나 쓰임 면에서나 차이가 명확하다. 칙칙폭폭 달려가는 기차를 떠올려보자. 첫번째 칸부터 쭉 길게 나열되어있는 숫자 기차(물론 기차에는 숫자가 아니라 문자를 태울 수도 있다. 배열이든 리스트든 내부요소는 문자와 숫자 모두 가능하다. 편의상 숫자기차라고 하겠다. )의 중간쯤, 가령 다섯번째 기차칸에 새로운 숫자를 넣는다고 할 때,
배열은 직접 원본을 훼손하면서라도 원하는 순서(index) 어디에든 자유롭게 숫자를 배치할 수 있다. 원래 다섯번째 칸에 주인이 있었든 없었든, 즉 메모리 공간이 비어있었든 차 있었든 배열에서의 숫자삽입은 원본을 대체하면서 이루어진다. 그 숫자가 내리면, 즉 배열에서 제거되면 그 메모리칸은 비게 된다. 각각의 숫자들에게 한번 부여된 순서(index)는 그대로 그 숫자가 할당된 고유한 순서값이 된다. 그래서 우리는 언제든 아주 빠르고 쉽게 원하는 숫자를 찾아 꺼내올 수 있다. "5번째에 타고 있는 숫자 100, 내려서 이리오세요." 라고.
반면 리스트에서는 원본 메모리를 유지하면서 빈 메모리를 찾아 새로운 숫자를 넣는다. 리스트에서는 기본적으로 빈공간을 전혀 만들지 않기 때문에, 즉 효율적인 메모리 관리를 중요시하기 때문에 이 기차에 빈칸은 없을 것이다. 그래서 새로운 숫자는 자연스럽게 맨끝칸에 타게 된다. 그러나 메모리 차원이 아니라 값으로서 다룰 데이터 차원에서 이들은 각자 '주소(포인터)'를 가짐으로써 내 다음 순서가 누구인지를 알고 있다. 첫번째 순서의 자료의 주소는 이들중 아무도 모르므로 미리 지정을 해주어야 한다. 새로운 숫자가 들어오면 이들이 알고있는 / 인지하고 있는 / 참조하고 있는(!) 주소(포인터)를 변경함으로써 이 새로운 숫자의 주소(포인터)가 5번째임을 4번째 주소를 가진 숫자에게 인지시켜주면 되는 것이다.
그렇기 때문에 자료를 꺼내오는 일이 빈번하다면 배열을, 삽입과 탐색과 삭제 등 수정을 빈번하게 해야 한다면 리스트를 활용하는 편이 낫다고 할 수 있다.
만들어진지 오래된 C언어는 리스트를 기본 내장 자료형으로 지원하지 않았고, 이후 만들어진 언어들은 사람들의 니즈를 반영하여 리스트와 배열을 기본 자료형으로 지원하기 시작했다. 다만 그 언어가 주로 쓰일 용도에 따라 리스트와 배열을 엄밀하게 구분하는지 여부는 언어마다 달랐다. 구글링해본 바에 따르면 자바에서는 배열과 리스트를 엄밀히 구분한다. 자바스크립트에서는 구분 없이 배열이라는 이름으로 리스트의 메소드를 대부분 지원한다. 파이썬은? 자바스크립트와 반대로 리스트 자료형을 제공하되, 리스트의 내부적으로는 배열 방식으로 메모리를 관리한다. 그렇기 때문에 '파이썬의 리스트는 자료구조가 아니다' 라는 설명이 붙어있었던 것이다.
책에 써있는 부연설명을 내가 이해한 대로 각색하면 다음과 같다.
파이썬의 리스트는 자료구조가 아닙니다.
(연결) 리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행할 수 있는 장점을 가진 자료구조를 의미합니다. 다만 리스트 자료구조는 메모리를 참조하는 속도면에서는 효율이 떨어진다는 단점이 있습니다.
그래서 파이썬의 리스트 자료형은 이러한 연결 리스트 방식 대신 배열 방식으로 내부에 원소들을 배치합니다.리스트의 메모리 관리방식과는 다르게, 실제 필요한 메모리보다 여유있게 미리 마련해두기 때문에 원소를 추가하거나 삽입할 때 메모리를 새로 확보하거나 해체하는 동작을 하지 않습니다.
이 책이 파이썬을 가지고 자료구조와 알고리즘을 설명하려다 보니, 자바에서의 배열과 리스트 개념을 클래스와 함수로 정의해서 구현하고 있기 때문에 이러한 오해가 빚어질 수 있는 것 같다.
매우 주관적인 생각으로, 파이썬에 남아있는 리스트의 흔적(?) 이라고 생각하는 부분이 있는데 그건 바로 기본메소드를 통해서는 list[5] = 100 이라고 직접 할당이 불가능하다는 점이다. list.push(100) 이라는 메소드를 통해 숫자를 넣어주는 것이 파이썬 리스트에서 요소를 삽입하는 기본 메소드의 동작 방식이다.
다음 주에는 이중연결리스트를 공부하고 정리해보겠다. :)
TMI.
스파이더맨은 내가 정말 좋아하는 영웅이다. 최근에 플레이스테이션 스파이더맨 게임을 선물받았는데 스틱과 버튼으로 뉴욕 상공을 속도감 있게 누빌 때 기분이 정말 좋다. 사실 이번 주말 내내 게임해서... 간신히 책상에 앉았다. 진도는 그래서 늦어졌는지도...
참고문헌
초보몽키의 개발공부로그 https://wayhome25.github.io/cs/2017/04/17/cs-18-1/
자료구조 제11-1강 연결리스트 - 개념과 기본 동작들 https://www.youtube.com/watch?v=eTwYE-ercNM
<자료구조와 함께 배우는 알고리즘 입문>
생활코딩 자료구조 - 리스트 https://opentutorials.org/module/1335/8636
점프투 파이썬 https://wikidocs.net/14
파이썬 자료구조 알고리즘 https://wikidocs.net/33825
Photo by Road Trip with Raj on Unsplash
