학점교류로 듣는 숙명여대 자료구조
day 5. 2021.12.28. 화요일
to be continued..... :D
linked stack and queue
linked stack
* isEmpty : 스택이 비어있는가?
linear list에서 top, front로 isEmpty를 체크하였다.
고정 크기가 아닌 경우, 함수 length와 같은 것을 활용할 수 있다.
head == None인 경우에 empty인 것이다 ~
비어있을 때랑 비어있지 않을 때 코드가 달라져야 한다.
* peek_front : 첫 원소를 본다(꺼내지 않음)
* add_front : push
* pop_front : pop
linked stack의 구조 LIFO
정적 배열과 달리.. (파이썬은 아니지만..) 문제는 size를 정하는 것
고정된 크기로 사용을 해주어야 한다.
연결 리스트는 개수를 정해주지 않아도 된다는 장점이 있다.
* isEmpty
def isEmpty(self):
return not self.head* peek_front
def peek_front(self):
if isEmpty():
print("List Empty")
else:
return self.head.data* add_front
def add_front(self, item):
node = Node(item)
if not self.head:
self.head = node
self.tail = node
else:
node.link = self.head
self.head = node노드의 링크가 잘 안되었다.
head가 참조한 링크를 노드가 참조한다.
* pop_front
def pop_front(self):
if not self.head:
print("List Empty")
return None
else:
temp= self.head
self.head = self.head.link
item = temp.data
del temp
return item
+ 과제 꿀팁 )
값은 당연하고, 코드 안에서 documentation을 해주어야 한다.
함수, 변수의 의미를 주석을 달아주기!
case를 빠뜨리지 말아야 한다.
Linked Queue
* isEmpty
* add_rear : add
* pop_front : del
뒤에 붙인다 / 앞에서 꺼낸다
* add_rear
노드를 만들어서 붙인다.
empty인 경우 / empty가 아니었던 경우로 나눈다.
def add_rear(self, item):
node = Node(item)
if not self.head:
self.head = node
self.tail = node
# tail이 none이면 error
# 발생하므로 이 부분 필요
elif self.tail:
self.tail.link = node
self.tail = node그리고 tail을 업데이트 해야한다.
연결 리스트는 케이스가 커버되었는지 보아야한다.
모든 일을 if-else로 생각한다.
if / else if / else
세상일은 fuzzy한 경우가 많다 -> AI가 처리함
기초가 튼튼해야 함
-> stack / queue / deque 데크
deque
* double ended queue
stack과 큐의 중간적인 자료 구조
stack : 앞에서 add / del
que : 앞에서 del / 뒤에서 add
deque : 앞에서 add / del, 뒤에서 add / del 되도록 만든 것이다.
따라서 함수가 총 네 개 필요하다.
* add_front -> 앞서 함
* add_rear -> //
* pop_front -> //
* pop_rear
head, tail 필요할 것임
딜레마가 존재하는데, 마지막 노드가 참조해왔지만, 직전 노드는 알지 못한다는 것이 문제다.
SLL에서는 단방향으로 연결되어있다. tail이 사라지기 때문에..
head부터 탐색해서 해준다.
(find가 해줌)
prev, temp를 같이 알려준다.
여기서부터는 어렵다 ㅠㅠ
def pop_rear(self):
if not self.head:
print("List Empty")
return None
else:
item = self.tail.data
prev, temp = self.find(item)
self.tail = prev
if prev:
prev.link = None
else:
self.head = None
del temp
return item- 노드가 1개인 경우 : 한 개를 삭제하면 empty list가 된다.
- 여러 개인 경우 : prev.link = None으로 업데이트 해준다.
-> 예습을 해와야한다 ㅠㅠ
linked polynomial
a = 5x^12 - 6x^8 + 13x^3b = 10x^15 + 4x^8 + 9
계수, 변수, 지수가 있다. 계수와 지수를 튜플로 출력한다.
a = [(5,12),(-6,8),(13,3)]
b = [(10,15),(4,8),(9,0)]
d = [(10,15),(5,12),(-2,8),(13,3),(9,0)]
생각해보자!
def del_list(self):
node = self.head
while node:
temp = node
node = node.link
del temp
print("List is deleted")
self.head = Nonenode는 움직이고,
temp가 가리키는 node를 바꾸어가면서
temp를 제거한다
node가 참조하는 대상이 바뀐다면?
* concatenate list
def concat(self, second):
if not self.head: # first list는 none
return second
elif second: # 두 리스트 모두 none 아님
temp = self.head # first 리스트의 헤드
while temp.link: # first list의 마지막 노드 찾기
temp = temp.link
temp.link = second
return self.head
# Time Complexity = O(n) (n= length of first)
# first.concat(second) 같은 형태
단, tail node가 있는 경우에는 tail.link로 second.head 이어주면 된다.
표로 그리면, case를 잘 찾는 것이 중요하다고 할 수 있다.
circular list
- chain
: a linked list whose the last node has a None link
- circular link
: a linked list whose last node is circularly connected with the first node
: easy to change the list pointer
: 전체 노드가 연결되어있어 시작 노드를 바꾸어도 계속해서 이어진다.
: chain의 경우 그렇지 않음
- length
complexity : O(length of list)
마지막 노드의 link가 head이다.
def length_list(self):
if not self.head: return 0
count = 0
temp = self.head
while True:
count += 1
temp = temp.link
if temp == self.head: break
return count코드가 어떻게 달라져야 하는가? (chain and circular) 결국 종료 조건(1바퀴를 다 돈)이 다르다.
- add_sort
add a node to circular list orderly
전 노드를 알고 있어야 한다. prev를 업데이트하면서 가야한다.
shorter [pass] / equal [duplicate] / longer [insert]
def add_sort(self, item):
node = Node(item)
if not self.head:
self.head = node
self.tail = node
node.link = self.head
return
temp = self.head
prev = None
while temp:
if item > temp.data: # 큼
prev = temp
temp = temp.link
elif item == temp.data: # 같음
print("Duplicate item")
return
else: # 작음
node.link = temp
if prev:
prev.link = node
else:
self.head = node
self.tail.link = node
return
if temp == self.head: break
# 최댓값 | 기존 노드보다 가장 큰 값이 들어온 경우
node.link = self.head
prev.link = node
reverse list
- reverse a list
[a,b,c,d,e]를 [e,d,c,b,a]로 바꿔준다.
case : empty list일 때
case : single node일 때
그대로 출력
case : 그보다 많을 때
reverse가 필요하다.
- time complexity
O(list length)
def reverse(self):
first = self.head
second = third = None
self.tail = self.head
while first:
third = second
second = first
first = first.link
second.link = third
self.head = second
return
역방향으로 링크가 재설정된다.
두 번 끝나면?
2 개의 node가 더 필요하다.
first, second, third가first를 역방향으로 이동시키면서, second/third가 순차적으로 따라가도록 했다.
doubly linked list