[자료구조] 리스트 - List

728x90

 

 

 

 

🙆‍♂️ List

---

class ArrayList:
    def __init__(self):
        self.items=[]
    #O(n)
    def insert(self,pos,elem):
        self.items.insert(pos,elem)
    #O(n)
    def delete(self, pos):
        self.items.pop(pos)
    def isEmpty(self):
        return self.size == 0
    #O(1)
    def getEntry(self,pos):
        return self.items[pos]
    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,elem):
        self.items[pos] = elem
    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)

이런식으로 파이썬 list를 사용해서 자료구조 list를 만들 수 있습니다.

 

리스트란 순서가 있는 항목들의 나열!

리스트를 만들 수 있는 방법은 2가지가 있는데

1. 배열 구조를 이용

2. 연결된 구조를 이용

배열 구조를 이용하면 구현이 간단하고 인덱스로 항목을 활용하기에 항목 접근의 시간 복잡도는 O(1)이지만 삽입 삭제시 오래걸립니다. 그리고 항목의 개수 제한도 있습니다.

 

연결된 구조를 이용하면 구현이 복잡합니다. 주소로 항목에 접근하여 항목 접근의 시간 복잡도는 O(n)입니다. 그러나 삽입 삭제가 효율적 이고 크기가 제한되지 않습니다.