python 자료구조 3. 리스트와 집합

목표

• 리스트는 가장 자유로운 선형 자료구조이다.
  -> 리슈트의 구조
  -> 리스트의 추상 자료형

• 리스트의 구현 방법
  -> 배열 구조 및 6단원의 연결된 구조로 구현가능하다.
  -> 리스트와 관련된 용어의 정리

리스트란?

• 리스트(list), 선형리스트(linear list)
  -> 순서(또는 위치)를 가진 항목들의 모임
  -> 집합: 항목간의 순서 개념이 없음

리스트 vs 스택,큐,덱의 차이점
: 리스트는 항목들이 순서대로 나열되어 있고, 각 항목들이 위치(인덱스)를 갖는다.
그러나 스택,큐,덱은 자료의 접근 위치가 다르다.

우리는 이 리스트를 배열이라 칭한다.

배열구조
1. 구현이 간단
2. 항목 접근이 O(1)
3. 삽입, 삭제시 오버헤드
4. 항목의 개수 제한

python list

• 파이썬 리스트는 스마트한 배열이다.

# 리스트 선언
A = [1,2,3,4,5]

# 항목의 수
print('리스트 항목의 수:',len(A))

# 항목 추가: 용량을 늘릴 수 있디.
A.append(6)
A.append(7)
A.insert(0,0)
print(A)

• 필요한 양보다 넉넉한 크기의 메모리를 사용!
  

• 남은 공간이 없으면 어떻게 삽입할까?
  : 연결리스트를 구현한다!

기존의 배열을 새로운 배열에 복사하면 이동연산이 발생한다.

파이썬 리스트의 시간 복잡도!

• append(elem) 연산: 대부분의 경우 O(1)
• insert(pos,elem) 연산 : O(n)
• pop(pos) 연산: O(n)

# 배열로 구현한 리스트(클래스)

class ArrayList:
    def __init__(self):
        self.items = []
    
    def insert(self,pos,elem):
        self.items.insert(pos,elem)
    
    def delete(self,pos):
        return self.items.pop(pos)
    
    def isEmpty(self):
        return self.size() == 0
    
    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.itmes.sort()
    
    def merge(self,lst):
        self.items.extend(lst)
    
    def display(self,msg='ArrayList:'):
        print(msg,'항목수=', self.size(),self.items)
        

집합이란?

• 특징

1. 원소의 중복을 허용하지 않음
2. 원소들 사이에 순서가 없음: 선형 자료구조가 아님

• 연산
  합집합, 교집합, 차집합

집합의 구현

# 리스트를 이용한 집합의 구현

class Set:
    def __init__(self):
        self.items =[]
    
    def size(self):
        return len(self.items)
    
    def display(self,msg):
        print(msg,self.items)
    
    def contains(self,item):
        return item in self.items
    
    def insert(self,elem):
        if elem not in self.items:
            self.items.append(elem)
    
    def delete(self,elem):
        if elem in self.items:
            self.items.remove(elem)
            
    def union(self,setB):
        setC = set()
        setC.items = list(self.items)
        for elem in setB.items:
            if elem not in self.itmes:
                setC.items.append(elem)
        return setC
    
    def intersect(self,setB):
        setC = Set()
        for elem in setB.items:
            for elem in setB.items:
                if elem in self.items:
                    setC.items.append(elem)
        return setC
    
    def difference(self,setB):
        setC = Set()
        for elem in self.items:
            if elem not in setB.items:
                setC.items.append(elem)
        return setC