오늘의 학습 주제
- 연결 리스트(Linked Lists)
- 양방향 연결 리스트(Doubly Linked Lists)
- 스택(Stacks)
- 수식의 후위 표기법
- 후위 표기 수식 계산
1.연결 리스트(Linked Lists)
-
추상적 자료구조(Abstract Data Structures)
자료구조의 내부구조는 숨겨두고, 추상적으로 보여주는
data 예:정수, 문자열, 레코드 ...
A set of operations
삽입, 삭제, 순회 ...
정렬, 탐색 ... -
연결 리스트
앞에 있는 것이 뒤에 있는 것을 가리키도록
각각의 item을 node라고 부름,
node 는 data, link(next)를 담고 있음
node 내의 데이터는 다른 구조로 이루어질 수 있음
예. 문자열, 레코드, 또 다른 연결 리스트 등
리스트의 맨 앞 = Head
리스트의 맨 마지막 node = Tail
of nodes: node가 몇 개 있는지
node(data, link),
class Node :
def init(self, item):
self.data = item
self.next = None
class LinkedList :
def init(self):
self.nodeCount = 0 #of nodes:0
self.head = None
self.tail = None
연산 정의
1. 특정 원소 참조(k 번째)
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기
예제. 첫 번째 index에 1을 지정
그렇게 하는 이유 : 0을 다른 목적에 이용하기 위함
def getAt(self, pos):
if pos <= 0 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
- 배열과 비교한 연결 리스트(배열/연결 리스트)
저장 공간 : 연속한 위치 / 임의의 위치
특정 원소 지칭 : 매우 간편 O(1) / 선형탐색과 유사 O(n)
선형 배열 : "번호가 붙여진 칸에 원소들을 채워넣는" 방식
연결 리스트 : "각 원소들을 줄줄이 엮어서" 관리하는 방식
연결리스트에서는 원소들이 링크(link)라고 부르는 고리로 연결
가운데에서 끊어 하나를 삭제하거나, 가운데를 끊고 그 자리에 다른 원소를 삽입하는 것이 쉽다
(=빠른 시간 내에 처리할 수 있다)
그래서 원소의 삽입'삭제가 빈번히 일어나는 응용에서는 연결 리스트가 많이 이용
운영체제(operating system)의 내부에서도 이러한 연결 리스트가 여러 곳에서 이용
선형 배열에 비해서 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다.
'k 번째의 원소' 를 찾아가는 데 선형 배열보다 시간이 오래 걸린다.
선형 배열에서는 데이터 원소들이 번호가 붙여진 칸들에 들어가 있기 때문에, 번호를 이용하여 특정 번째의 원소를 찾아갈 수 있기 때문이다.
연결 리스트에서는 단지 원소들이 고리로 연결된 모습을 하고 있기 때문에, 앞에서부터 하나씩 링크를 따라가면서 찾아야 한다.
연결 리스트 연산 - 원소의 삽입
def insertAt(self, pos, newNode):
pos가 가리키는 위치에 (1<=pos<=nodeCount+1)
newNode를 삽입하고 성공/실패에 따라 True/False를 리턴
L.inswerAt(pos, newNode)
pos 번째에 newNode를 삽입하기 위해서는
pos-1 번째와 p 번쨰의 Node 사이에 삽입해야한다.
그렇게 하려면 pos-1번째의 next에 newNode를 연결해야 하고,
newNode의 next에 pos를 연결해야한다.
따라서, pos-1번째 노드를 prev라고 한다면
newNode 의 next link 가 prev.next를 가리키도록(newNode -> prev.next,
newNode를 pos-1 번째의 next link가 가리키도록
마지막으로 nodeCount 를 1 증가시킨다.
코드 구현
def insertAt(self, pos, newNode):
if pos<1 or pos>self.nodeCount+1:
return False
if pos==1:
newNode.next = self.head
self.head = newNode
else :
prev = self.getAt(pos-1)
newNode.next = prev.next
prev.next = newNode #순서를 지켜야함.
if pos == self.nodeCount+1:
self.tail = newNode
self.nodeCount += 1
return True
주의사항
(1)삽입하려는 위치가 리스트 맨 앞일 때
prev 없음
head 조정 필요
(2)삽입하려는 위치가 리스트 맨 끝일 때
tail 조정 필요
(3)빈 리스트에 삽일할 때
위 두 조건에 의해 처리됨
삽입하려는 위치가 리스트 맨 끝일 때,
즉 pos == nodeCount+1인 경우?
맨 앞에서부터 찾아갈 필요가 없음
코드 구현
def insertAt(self, pos, newNode):
if pos<1 or pos>self.nodeCount+1:
return False
if pos==1:
newNode.next = self.head
self.head = newNode
else :
if pos == self.nodecount+1:
prev = self.tail
else :
prev = self.getAt(pos-1) #tail로 바로간다.
newNode.next = prev.next
prev.next = newNode #순서를 지켜야함.
if pos == self.nodeCount+1:
self.tail = newNode
self.nodeCount += 1
return True
연결 리스트 원소 삽입의 복잡도
맨 앞에 삽입하는 경우 : O(n)
중간에 삽입하는 경우 : O(n)
맨 끝에 삽입하는 경우 : O(1) - tail을 가지고 있기 때문에
연결 리스트 연산 - 원소의 삭제
def posAt(self, pos):
pos가 가리키는 위치의 (1<=pos<nodeCount)
node를 삭제하고
그 node의 데이터를 리턴
r=L.popAt(pos)
prev(=pos-1)
curr=pos
prev.next<- curr.next
nodeCount -= 1
(1)삭제하려는 node가 맨 앞의 것일 때
prev 없음
head 조정 필요
(2)리스트 맨 끝의 node를 삭제할 때
tail 조정 필요
(3)유일한 노드를 삭제할 때?
삭제하려는 node가 마지막 node일 때,
즉 pos == nodeCount인 경우?
하지만 한 번에 처리할 수 없다 (prev를 찾을 수 없으므로)
앞에서부터 찾아와야 함
연결 리스트 원소 삭제의 복잡도
맨 앞에서 삭제하는 경우 : O(1)
중간에서 삭제하는 경우 : O(n)
맨 끝에서 삭제하는 경우 : O(n)
연결 리스트 연산 - 두 리스트의 연결
def concat(self, L):
연결 리스트 self 뒤에 또다른 연결 리스트인 L을 이어붙임
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
연결 리스트가 힘을 발휘할 때
삽입과 삭제가 유연하다는 것이 가장 큰 장점
새로운 메서드들을 만들자.
insertAfter(prev, newNode) > 맨 앞에는 어떻게?
popAfter(prev) > 맨 앞에서는 어떻게?
조금 변형된 연결 리스트
맨 앞에 dummy node를 추가한 형태로
dommy node에 0을 붙인다.
class LinkedList:
def init(self):
self.nodeCount = 0
self.head = node(None)
self.tail = None
self.head.next = self.tail
연결 리스트 연산 - 리스트 순회
def traverse(self):
result = []
curr = self.head
while curr.next :
curr = curr.next
result.append(curr.data)
return result
연결 리스트 연산 - k번째 원소 얻어내기
def getAt(self, pos)
if pos<1 or pos>self.nodeCount:
return None
i = 0
curr = self.head
while i < pos:
curr=curr.next
i +=1
return curr
getAt(0) > head
연결 리스트 연산 - 원소의 삽입
def insertAfter(self, prev, newNode):
prev가 가리키는 node의 다음에
newNode를 삽입하고
성공/실패에 따라 True/False 리턴 - 위에서의 내용과 동일
newNode.next = prev.next
if prev.next is None:
self.tail = newNode
prev.next = newNode
self.nodeCount += 1
return True
tail의 뒤에 삽입하는 경우도 고려
메서드 insertAt()의 구현
def insertAt(self, pos, newNode):
이미 구현한 insertAfter()를 호출하여 이용하는 것으로
(1) pos 범위 조건 확인
(2) pos == 1인 경우에는 head 뒤에 새 node 삽입
(3) pos == nodeCount +1 인 경우는 prev < tail
(4) 그렇지 않은 경우에는 prev < getAt(...)
def insertAt(self, pos, newNode):
if pos<1 or pos>self.nodeCount+!:
return False
if pos != 1 and pos == self.nodeCount+1:
prev=self.tail
else:
prev.self.getAt(pos-1)
return self.insertAfter(prev,newNode)
연결 리스트 연산 - 원소의 삭제
def popAfter(self, prev):
prev의 다음 node를 삭제하고
그 node의 data를 리턴
r=L.popAfter(prev)
코드 구현 주의사항
(1) prev가 마지막 node일 때 (prev.next == None)
삭제할 node 없음
return None
(2)리스트 맨 끝의 NODE를 삭제할 때 (curr.next == None)
Tail 조정 필요
연결 리스트 연산 - 두 리스트의 연결
L1.concat(L2)
def concat(self,L):
self.tail.next = L.head.next
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
양방향 연결 리스트(Doubly Linked Lists)
ex.task switching
한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
앞으로도 (다음node) 뒤로도 (이전node)진행 가능
Node의 구조 확장
class Node:
def init(self, item):
self.data = item
self.prev = None
self.next = None
리스트 처음과 끝에 dummy node를 두자!
데이터를 담고 있는 node 들은 모두 같은 모양
파일 참고
리스트 순회
리스트 역순회
원소의 삽입
연습문제 - 양방향 연결 리스트 메서드 구현
3. 스택(Stacks)
자료(data element)를 보관할 수 있는 (선형) 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 푸시(push) 연산
꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 팝(pop) 연산
후입선출(LIFO) 특징을 가지는 선형구조
스택에서 발생하는 오류
비어 있는 스택에서 데이터 원소를 꺼내려 할 때 : 스택 언더플로우(stack underflow)
꽉 찬 스택에 데이터 원소를 넣으려 할 때 : 스택 오버플로우(stack overflow)
스택의 추상적 자료구조 구현
(1) 배열(array)을 이용하여 구현
python 리스트와 메서드들을 이용
(2) 연결 리스트(linked list)를 이용하여 구현
양방향 연결 리스트 이용
연산의 정의
size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() - 현재 스택이 비어 있는지를 판단
push(x) - 데이터 원소 x를 스택에 추가
pop() - 스택의 맨 위에 저장된 데이터 원소를 제거 (또한, 반환)
peek() - 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)
배열로 구현한 ㅡㅅ택
class ArrayStack:
def init(self):
self.data = [] 빈 스택으로 초기화
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self) :
return self.data.pop() 데이터 원소를 삭제(리턴)
def peek(self):
return self.data[-1]
연습문제 - 수식의 괄호 유효성 검사
알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서:
여는 괄호 - ( 또는 { 또는 [ - 를 만나면 스택에 푸시
닫는 괄호 - ) 또는 } 또는 ] - 를 만나면:
스택이 비어 있으면 올바르지 않은 수식
스택에서 pop, 쌍을 이루는 여는 괄호인지 검사
맞지 않으면 올바르지 않은 수식
끝까지 검사한 후, 스택이 비어 있어야 올바른 수식
- 수식의 후위 표기법
중위 표기법과 후위 표기법
중위 표기법(infix notation) : 연산자가 피연산자들의 사이에 위치
(a+b)x(c+d)
후위 표기법(postfix notaion) : 연산자가 피연산자들의 뒤에 위치
ab + cd + x
중위 표기식을 후위 표현식으로 바꾸는 방법
중위 : (a+b)x(c+d)
후위 : ab+cd+*
중위 : (a+(b-c))xd
후위 : abc-+d*
중위 : ax(b-(c+d))
후위 : abcd+-*
알고리즘의 설계
연산자의 우선순위 설정
중위 표현식을 왼쪽부터 한 글자씩 읽어서
피연산자이면 그냥 출력
'('이면 스택에 push
')'이면 '('이 나올 때까지 스택에서 pop, 출력
연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
그리고 이 연산자는 스택에 push
스택에 남아 있는 연산자는 모두 pop, 출력
코드의 구현 - 힌트
스택의 맨 위에 있는 연산자와의 우선순위 비교
스택의 peek() 연산 이용
스택에 남아 있는 연산자 모두 pop() 하는 순환문
while not opStack.isEmpty() :
_ 5.후위 표기 수식 계산
후위 표현식을 왼쪽부터 한 글자씩 읽어서
피연산자이면 스택에 push
연산자를 만나면 스택에서 pop > (1), 또 pop > (2)
(2) 연산 (1)을 계산, 이 결과를 스택에 push
수식의 끝에 도달하면 스택에서 pop > 이것이 계산 결과
