[자료구조] 리스트 (List)

리스트: 항목들이 나열되어 있는 자료구조.
굉장히 자유로운 선형 구조이며 우리가 일상생활에서 가장 흔히 접할 수 있는 구조이다.
간단하게 생각하면, 여러 요소들을 마구잡이로 하나로 모아 놓은 구조라고 생각하면 될 듯...?

 

리스트의 기능

• insert(pos, e): pos 위치에 새로운 요소 e를 삽입한다.
• delete(pos): pos 위치에 있는 요소를 삭제하고 반환한다.
• isEmpty(): 리스트가 비어있으면 True를, 아니면 False를 반환한다.
• getEntry(pos): pos 위치에 있는 요소를 반환한다.
• size(): 리스트의 요소 개수를 반환한다.
• clear(): 리스트를 초기화한다.
• find(e): 리스트에서 e를 찾아 인덱스를 반환한다.
• replace(pos, e): pos에 있는 요소를 e로 바꾼다.
• sort(): 리스트의 요소들을 기준에 따라 정렬한다.
• merge(lst): 리스트 lst를 현재 리스트에 병합시킨다.
• display(): 리스트를 출력한다.
• append(e): 리스트의 맨 뒤에 새로운 항목을 추가한다.

---

리스트의 구현

class List:
    def __init__(self):
        self.items = []
        
    def insert(self, pos, e):
        self.items.insert(pos, e)

    def delete(self, pos):
        self.items.pop(pos)

    def getEntry(self, pos):
        return self.items[pos]

    def isEmpty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def clear(self):
        self.items = []

    def find(self, item):
        return self.items.index(item)

    def replace(self, pos, e):
        self.items[pos] = e

    def sort(self):
        self.items.sort()

    def merge(self, lst):
        self.items.extend(lst)

    def display(self, msg='ArrayList:'):
        print(msg, self.size(), self.items)

 

시간복잡도
append(): O(1)
insert(), pop(): O(n)

파이썬의 배열은 타 언어와는 다르게 동적 배열이기 때문에, 리스트의 크기가 자동으로 확장된다.
C언어나 자바 같은 경우에는 처음 선언한 크기 만큼밖에 사용하지 못하는데, 파이썬에는 그런 제약이 없다.(정확하게는 제약이 있지만 자동으로 크기가 더 큰 배열으로 이동시켜주는 방식)

 

작성일자: 2023-02-21