[Algorithm] 선형구조-리스트/스택/큐/데크

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

아래에서 설명할 자료구조는 파이썬에서 리스트를 이용하면 대부분 구현 가능하다.

 

순차 리스트 (> static)

: 배열과 유사하게 동일한 유형의 자료를 연속적으로 나열하기 위해 사용되는 추상 데이터 구조(ADT)

* ADT(추상화 자료 구조): 프로그램의 대상이 되는 무엇인가를 추상화하여 표현하는 것으로 유지보수가 용이

 

- 특정 위치에서의 삽입/삭제 = O(n)

- i번째 노드 탐색 수행 시간 = O(1) > 각 배열의 위치를 알고 있기 때문에

---

연결리스트 (> dynamic)

: 자료의 연결을 위해 포인터 사용, 각 노드는 다음 노드를 가리키는 포인터를 가짐

단일 연결리스트

이중 연결리스트

- 특정 위치에서의 삽입/삭제 = O(1)

- i번째 노드 탐색 수행 시간 = O(n)

 

---

배열을 이용해 stack과 queue 구조로 사용할 수 있다.

 

스택 (Stack)

: Last In First Out, 즉 선입후출의 구조를 가지는 자료구조. 한쪽 끝에서만 자료를 넣고 뺄 수 있음

값을 입력할 때 PUSH, 값을 뺄 때 POP를 사용하며 스택에 가장 최근에 입력된 데이터를 가리키는 포인터를 SP(Stack Pointer)라고 함

스택

- 특정 위치에서의 삽입/삭제 = O(1)

  (스택의 삽입삭제는 항상 SP에서만 일어나므로 / but, remove를 사용하는 경우 O(n))

- i번째 노드 탐색 수행 시간 = O(n)

 

---

큐 (Queue)

: First In First Out, 즉 선입선출의 구조를 가지는 자료구조

큐 맨 뒤에 데이터를 추가할 땐 Enqueue, 큐 맨 앞의 데이터를 삭제할 땐 Dequeue를 사용

큐의 가장 앞에 위치한 자료는 Front(데이터가 나가는 곳), 가장 마지막에 위치한 자료는 Rear(데이터가 들어오는 곳)로 가리키며 큐가 비어있는 경우 두 값은 -1을 가짐

큐

- 특정 위치에서의 삽입/삭제 = O(1)

  (큐의 삽입은 front에서만, 삭제는 rear에서만 일어나므로 / but, remove를 사용하는 경우 O(n)

- i번째 노드 탐색 수행 시간 = O(n)

 

* python에서 deque 모듈을 이용해서 편하게 큐를 구현할 수 있음

from collections import deque

queue=deque([1,2,3])	# queue라는 변수명으로 큐 생성
queue.append(4)			# queue의 맨 뒤에 값 추가 = [1, 2, 3, 4]
queue.appendleft(0)		# queue의 맨 처음에 값 추가 = [0, 1, 2, 3, 4]
queue.pop()				# queue의 가장 마지막 값을 pop = 4
queue.popleft()			# 리스트에서 pop(0)과 같은 코드로 queue의 가장 왼쪽 값을 pop = 0
# deque([1,2,3])

list(queue) 			# queue를 리스트로 변환
# [1,2,3]

 

---

데크 (Double Ended Queue)

: 큐의 양 끝이 front이면서 rear인 자료구조, 즉 양쪽 끝에서 데이터의 삭제와 삽입 모두 가능데크에 데이터를 추가할 땐 append, 큐 맨 앞의 데이터를 삭제할 땐 pop 사용

데크의 가장 앞에 위치한 자료는 Front, 가장 마지막에 위치한 자료는 Rear

 

- 특정 위치에서의 삽입/삭제 = O(1)

  (but, remove를 사용하는 경우 O(n)

- i번째 노드 탐색 수행 시간 = O(n)