자료구조 중 리스트를 알아보자!
ArrayList
: 배열을 만들어 순서대로 저장한다
LinkedList
: 노드 형태로 원소를 저장한다.
Singly Linked List, Doubly Linked List(이중연결리스트), Circular Linked List(원형연결리스트), Circular Doubly Linked List가 존재
▶Singly Linked List
: 항상 Head부터 시작한다. 그래서 마지막 원소를 알고싶어도 처음부터 시작해야한다는 점! 그래서 Tail을 이용해 맨 마지막 원소를 가리키게 하기도 한다.(단 역방향 불가)
* python에서는 맨마지막원소가 가리키는 것을 None이라고하고 C에서는 Null이라고 한다.
▶Circular Linked List(원형연결리스트)
: 순환구조 리스트로, Tail이 있으면 진가를 발휘한다. 왜냐하면 Tail이 있다면 굳이 Head가 없어도 된다! Tail다음이 첫 원소이기 때문!
▶Doubly Linked List(이중연결리스트)
: 공간을 많이 차지하게 되어서 메모리가 비효율적이라는 단점있지만, 역방향이 가능하다
▶Circular Doubly Linked List
: 원형연결리스트와 이중연결리스트를 합친 것을 뜻한다.
파이썬에서 리스트는 ArrayList다.
※ 만약 파이썬에서 Linked List가 필요하면 deque를 사용한다!
from collections import
queue = deque()
queue.append(new_element)
value = queue.pop()
queue.appendleft(new_element)
value = queue.popleft()
스택과 큐
▶ 후입선출(LIFO or FILO) : 스택에 해당(항아리라고 생각! 위에서 넣고 뺀다)
▶ 선입선출(FIFO) : 큐에 해당(줄서는 개념과 비슷, 먼저 넣은 것 먼저 빠져나감)
파이썬 리스트를 이용한 스택 & 큐
list = [] 스택 : list = list + [new_element] 큐 : list = [new_element] + list 값 : list.pop() -----> 뒤에서부터 빠진다 |
list = [] list.append(new_element) 스택 : value = list.pop() 큐 : value = list.pop(0) -------->맨 앞에서 뽑는다 |
파이썬 리스트를 각각 Arraylist와 Linkedlist라고 가정해보자!
LinkedList | arrayList | |
list = [] | Head -> None | 기본 4크기의 배열을 만든다. |
list.append(10) | Head -> 10 -> None | 앞에 10이 채워진다. |
for i range(5): list.append(i) |
Head -> 10 -> 0 -> 1 ->..-> None | 더블링이 일어난다(8크기 배열을 만들고 4크기 배열을 복사한 후, 나머지 원소를 뒤에 추가 후, 4크기 배열은 없앤다. 1. allocation 2. memcopy 3. free |
list = [11] + list | Head -> 11 -> 10 -> .. -> None | 원소 갯수만큼 뒤로 밀어야 한다(11이 맨 앞에 와야하니까), 시간 오래 걸림 for i in range(len(list)): A[i+1] = A[i] |
list.pop(0) | Head다음 가리키는 노드를 삭제하고, 삭제된 노드가 가리켰던 노드를 Head가 가리킨다 | 맨 앞 원소를 삭제하고 나머지 원소들을 앞으로 다 땡겨와야 한다. |
list.pop() | 맨 뒤 노드를 삭제하고 맨 뒤노드가 None을 가리키고 있었기 때문에 삭제된 노드를 가리키고 있던 노드가 이제는 None을 가리킨다. | 맨 뒤 원소를 삭제한다 |
for i range(len(list)): print(list[i]) |
계속 순환해야한다(배열보다 비효율), 그래서 iterator개념이나온다. | list[0],list[1],list[2], ..... |
파이썬 리스트
- 파이썬에서 스택이 필요하면?
방법1 : 파이썬 리스트이용
방법2 : 큐 모듈(queue)의 LifoQueue클래스 사용
방법3 : 직접 클래스로 구현해서 사용
-파이썬에서 큐가 필요하면?
방법1: 큐 모듈의 Queue클래스 사용
방법2: 직접 클래스로 구현해 사용
import queue
q = queue.LifoQueue()
또는
q = queue.Queue()
q.put(new_element)
value = q.get()
size = q.size()
우선순위 큐(Priority Queue)
- 일반적인 큐는 먼저 집어넣은 데이터가 먼저나오는 FIFO구조이지만 우선순위 큐는 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옴( 보통 더 높은 우선순위를 더 낮은 값을 표현), 즉 넣은순서가 상관없다는 말!
import queue
q = queue.PriorityQueue()
q.put((priority,element))
value = q.get()
size = q.size()
- 선형 자료구조가 아님
- 힙이 가장 효율적인 구현 방법
- 파이썬에서 우선순위 큐가 필요하면?
방법 1: heapq모듈을 사용, 큐 모듈의 PriorityQueue
(파이썬에서 구현된 우선순위 큐는 낮은 순서가 우선임)
'개발일기 > Python' 카테고리의 다른 글
[Python] 기본적인 자료구조 - 그래프(Graph) (0) | 2023.04.24 |
---|---|
[Python] 알고리즘 효율성 분석 (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |
[Python] 알고리즘 - 최대값찾기 (0) | 2023.03.14 |
[Python] 리스트(List)관련 자주 쓰이는 기능 정리 (0) | 2023.03.14 |