[자료구조] 리스트와 집합

1. 리스트의 개념과 동작 원리

 (1) 리스트의 개념

  - 리스트(선형리스트) : 순서를 가지는 항목들의 모임

   * 집합과는 다름 집합은 항목간의 순서의 개념이 없음 (집합은 1,2,3 이나 2,1,3이나 똑같다)

  - 항목들은 순서대로 나열되며, 각 항목은 자신의 위치가 있음

  - 스택, 큐, 덱과는 자료의 접근 위치가 다름

   * 스택, 큐, 덱은 전단 후단에서만 삽입 삭제가 가능하지만 리스트는 어디서든 가능 중간(l[2] 삭제, l[2])로 삽입도 가능

  - 리스트의 Data : 같은 유형의 요소들의 순서 있는 모임

  - 연산

list()	비어있는 새로운 리스트를 만듦 items = []	O(1)
insert(pos, e)	pos 자리에 e 요소를 삽입	O(n)
delete(pos, e)	pos 자리의 e 요소를 삭제하고 반환함 == return items.pop(pos)
isEmpty()	리스트가 빈 상태인지 검사 len() == 0
getEntry(pos)	pos 자리의 e 요소를 반환함
size()	리스트 안의 요소의 개수를 반환 len(items)
clear()	리스트를 초기화함 (함수로 만든 경우 전역변수로 호출해서 사용해야 함) globa items  items = []
find(item)	리스트에서 item이 있는지 찾아 인덱스를 반환함 items.index(item)
replace(pos, item)	pos 자리의 항목을 item으로 변환
sort()	리스트의 항목들을 정렬함 items.sort()
merge(lst)	다른 리스트인 lst을 리스트에 추가함 items.extend(lst)
display()	리스트를 화면에 출력함 print(items)
append(e)	리스트의 맨 뒤에 항목을 추가함	O(1)
len()	항목 수
pop(pos)	pos 자리의 요소를 삭제하고 반환함 (기본은 0)	O(n)

  - 리스트 구현 방법

항목	배열 구조	연결된 구조
구현방식	간단	복잡
항목 접근 복잡도	O(1)	O(n)
삽입 삭제	오버헤드	효율적
항목 개수	개수 제한	크기 제한 없음
리스트	[ 15, 9, 3, 32,12 ]  0 > 1 > 2 > 3 > 4	[ 15, 9, 3, 32,12 ] 15 > 9 > 3 > 32 > 12

  - 파이썬 리스트 : c언어의 배열이 진화된 형태로 자료구조를 구현하기 위한 하나의 방법

  - 연결 리스트 : 자료가 일렬로 나열된 배열 구조

  - 자료 구조 리스트 : 추상적 의미, 리스트 ADT(추상 자료형)를 구현하기 위해 배열 구조나 연결 구조 사용

 (2) 파이썬 리스트의 특징

  - 스마트한 배열

  - 항목 추가로 용량 증대 가능

  - 동적 배열의 특성 : 필요량보다 더 큰 메모리를 사용함

    * 크기 = 용량인 상황에서 항목 삽입 시

     용량을 확장한 새로운 배열 할당 > 기존의 배열을 새로운 배열에 복사 > 항목을 삽입 > 기존 배열 해제, 리스트로 새 배열 사용 

 (3) 배열 리스트

  - 자료 구조 리스트 ADT 구현 = 전역 변수와 함수로 구현

2. 집합의 개념과 구현 방법

 (1) 집합의 개념

  - 원소의 중복을 허용하지 않음

  - 원소들 사이에 순서가 없음 (선형 자료 구조가 아님)

   S = {1,2,3}

  - 집합의 데이터 : 같은 유형의 유일한 요소들의 모임, 원소들은 순서가 없지만 서로 비교할 수 있어야 함

  - 집합 연산

set()	비어있는 새로운 집합을 만듦	items = []
size()	집합의 원소의 개수를 반환함	len(items)
contains(e)	집합이 원소 e를 포함하는지 검사하고 반환함	e in items
insert(e)	새로운 원소 e를 삽입하고 e가 이미 있다면 삽입하지 않음	if e not in items : items.append(e)
delete(e)	원소 e를 삭제하고 반환함	remove(e)
equals(setB)	setB와 같은 집합인지 검사함	items == setB
union(setB)	setB와의 합집합	setA = items for x in setB :      if x not in items :         setA.append(e)
intersect(setB)	setB와의 교집합	setA = [] for x in setB :      if x in items :         setA.append(e)
difference(setB)	setB와의 차집합	setA = [] for x in setB :      if x not in items :         setA.append(e)
display()	표현	print(items)