연결 리스트(Linked Lists)와 스택(Stack)

추상적 자료구조(Abstract Data Structures)

Data : 정수, 문자열, 레코드 등
A sete of operations : 삽입, 삭제, 순회, 정렬, 탐색 등

연결리스트(linked lists) : 각 원소들을 줄줄이 엮어서 늘어 놓은 것 

배열과 연결리스트의 차이
저장공간 : 배열 - 연속한 위치, 연결리스트 - 임의의 위치
특정 원소 지칭 : 배열 - 매우 간편 O(1) , 연결리스트 - 선현탐색과 유사 O(n)

 

연결리스트의 원소 삽입

def insertAt(self, pos, newNode) :
if pos < 1 or pos
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)
newNode. next = prev.next
prev.next = newNode

if pos = self.nodeCount + 1:
self. tail = newNode

self. nodeCount += 1
return True

 

연결 리스트 원소 삽입의 복잡도
맨 앞에 삽입하는 경우 : O(1)
중간에 삽입하는 경우 : O(n)
맨 끝에 삽입하는 경우 : O(1)

 

연결리스트의 원소 삭제

연결 리스트 원소 삭제의 복잡도
맨 앞에 삭제하는 경우 : O(1)
중간에 삭제하는 경우 : O(n)
맨 끝에 삭제하는 경우 : O(n)

 

두 연결리스트의 연결

def concat(self, L) :
self.tail.next = L.head
if L.tail :
self.tail=L.tail
self.nodeCount +=L.nodeCount

 

연결리스트의 장점 : 삽입과 삭제가 유연하다.

dummy node(0번)을 추가하여 삽입과 삭제를 더 유연하게 가능하다.

 

def insertAfter(self, prev, newNode):
newNode.next = prev.next
if prev.next is None:
self.tail = newNode
prev.next = newNode
self.nodeCount += 1
return True



def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos != 1 and pos == self.nodeCount + 1:
prev = self.tail
else:
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)

 

연결리스트의 단점 : 되돌아 갈 수 없다.

양방향 연결리스트(Doubly Linked Lists) :

연결리스트의 단점인 뒤로 돌아갈 수 없는 점을 보안하여 양쪽으로 연결되어 앞으로도, 뒤로도 자유롭게 진행이 가능하다. 코딩이 편해진다.

리스트의 처음과 끝에 더미노드를 둔다 !
=> 데이터를 담고 있는 노드들은 모두 같은 모양이 된다.
선형시간 알고리즘인것은 변함이 없다.

스택(stack)

자료를 보관할 수 있는 (선형) 구조
후입선출(LIFO - Last-In First-Out) 특징을 가지는 선형 자료구조이다.
push - 스택에 원소 추가
pop - 스택에서 원소 제거

size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() - 현재 스택이 비어 있는지를 판단
push(a) - 원소a를 스택에 추가
pop() - 스택의 맨 위에 저장된 데이터 원소를 제거
peek() - 스택의 맨 위에 저장된 데이터 원소를 반환(제거하지는 않음)

수식의 후위 표기법

중위표기법(Infix notation) - 연산자가 피연산자들의 사이에 위치
ex) (A+B)*(C+D)

후위표기법(Postfix notation) - 연산자가 피연산자들의 뒤에 위치
ex) AB+CD+*