[Python] 기본적인 자료구조 - 리스트(list), 스택, 큐

자료구조 중 리스트를 알아보자!

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

(파이썬에서 구현된 우선순위 큐는 낮은 순서가 우선임)