2. 리스트 추상 자료형(List ADT) 파이썬(with Python)

매일 하나씩 40일에 완성하는

파이썬 자료구조 & 알고리즘

추상 자료형 (Abstract Data Type, ADT)

추상 자료형이란 추상화 된 자료형이겠죠? 그럼 자료형이 뭘까요?

 

프로그래밍 언어마다 약간의 차이는 있지만 보통 정수, 실수, 불린, 문자, 문자열 등을 자료형이라 합니다.

C언어에서는 구조체(https://dojang.io/mod/page/view.php?id=407)까지도 자료형에 포함합니다. 
파생형(derived type)으로 분류하죠. 

 

추상 자료형은 (class 등을 이용해서) 추상적으로 자료형을 표현했다 정도로 간단히 이해하고 넘어가겠습니다. 

더 자세한 것은 위키 백과를 참고하시구요. 

 

자료형: 

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C%ED%98%95

추상 자료형: 

https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95

List ADT

리스트 ADT를 만들기 위해서 먼저 설계를 해야합니다. 
설계를 하려면 리스트의 정의, 사용할 프로퍼티, 리스트가 수행하는 동작, 리스트에 의해 수행될 동작 등을 생각해둬야겠죠?

 

리스트는 순서가 있는 연속적인 데이터 집합입니다. 

리스트에 저장된 각각의 데이터들을 요소element라고 부릅니다. 

요소가 없는 빈 리스트도 가능합니다. 

리스트에 저장된 요소의 갯수를 리스트의 길이라고 하는데 size 변수에 저장합시다.

리스트 뒤에 요소를 추가하는 것을 append,
리스트의 요소를 찾아 지우는 것을 remove,
리스트 전체를 비우는 것을 clear라고 정의합시다. 

...
등등등
...

탐색에 관련된 부분도 생각해 두죠.

 

설계가 끝났으면..
그 다음엔 코딩이죠. 

 

파이썬의 list를 이용해 코딩합시다. 

 

그런데 뭔가 이상한 느낌이 들지 않습니까? 리스트를 이용해서 리스트를 코딩한다니 ...
프로그래밍 언어에서 제공되는 기능을 다시 코딩한다는 건 큰 삽질입니다만 공부를 위해서 이런 삽질을 하는 거죠.
게다가 보통, ADT를 만드는 것보다 언어에서 제공되는 기능을 그대로 쓰는 게 속도가 더 빠릅니다. 

class List:

    def __init__(self):
        self.list = []
        self.pos = 0
        self.size = 0

    def append(self, element):
        self.list.append(element)
        self.size += 1

    def length(self):
        return self.size

    def find(self, element):
        for i in range(self.size):
            if self.list[i] == element:
                return i
        return False

    def insert(self, element, after):
        insert_pos = self.find(after)
        if insert_pos:
            self.list.insert(insert_pos + 1, element)
            self.size += 1
            return True
        return False

    def remove(self, element):
        found_at = self.find(element)
        if found_at:
            del self.list[found_at]
            self.size -= 1
            return True
        return False

    def clear(self):
        self.list.clear()
        self.size = 0
        self.pos = 0

    def tostring(self):
        # return self.list
        return '[' + ', '.join([str(each) for each in self.list]) + ']'
        # return f"[{', '.join(list(map(str, self.list)))}]"


nums = List()
nums.append(1)
nums.append(2)
nums.append(3)
nums.append(4)
print(nums.tostring())

 

실제 프로젝트에서는 다음 파이썬 공식 문서에 나와 있는 것처럼 이미 구현된 리스트의 메소드들을 이용하시면 됩니다. 

파이썬 자료구조: https://docs.python.org/ko/3/tutorial/datastructures.html

여담이지만, 파이썬의 공식 문서의 한글화 수준이 상당히 좋네요. ^^

 

tostring 메서드 대신 __str__ 메서드를 정의해 두면 print(num)을 바로 쓸 수 있습니다. 

def __str__(self):
    return f"[{', '.join(list(map(str, self.list)))}]"

# print(nums.tostring())
print(nums)

length 메서드 대신 __len__ 메서드를 정의해 두면 len(num)을 바로 쓸 수 있습니다. 
깔끔하네요. 

 

class List:

    def __init__(self):
        self.list = []
        self.pos = 0
        self.size = 0

    def append(self, element):
        self.list.append(element)
        self.size += 1

    def find(self, element):
        for i in range(self.size):
            if self.list[i] == element:
                return i
        return False

    def insert(self, element, after):
        insert_pos = self.find(after)
        if insert_pos:
            self.list.insert(insert_pos + 1, element)
            self.size += 1
            return True
        return False

    def remove(self, element):
        found_at = self.find(element)
        if found_at:
            del self.list[found_at]
            self.size -= 1
            return True
        return False

    def clear(self):
        self.list.clear()
        self.size = 0
        self.pos = 0

    def __len__(self):
        return self.size

    def __str__(self):
        return f"[{', '.join(list(map(str, self.list)))}]"


nums = List()
nums.append(1)
nums.append(2)
nums.append(3)
nums.append(4)
print(nums)
print(len(nums))