[3/26] TIL - 연결 리스트, 스택, 후위 표기식

Sangwon Jwa·2024년 3월 26일

데브코스

데브코스 TIL

목록 보기

2/54

📖 학습 주제

연결 리스트

양방향 연결 리스트

스택

후위 표기식

✏️ 주요 메모 사항 소개

추상적 자료구조 (Abstract Data Structure)
내부구현은 숨기고 외부만 제공.
데이터(정수, 문자열, 레코드 ...) + 연산( 삽입, 삭제, 순회, 정렬, 탐색 ...)

연결 리스트 (Linked List)

노드(Data + Link)로 이루어진 리스트, 노드 내의 데이터는 다른 구조로 이루어질 수 있고 링크는 다음 노드의 정보를 가짐. 일반적으로 처음 노드를 Head, 끝 노드를 Tail, 전체 노드의 개수를 기록해둔 변수등을 사용.

연결리스트의 0번째를 다른 용도(dummy node)로 사용하기 위해 연결 리스트의 첫번째 인덱스는 1로 하는게 좋다.
리스트 중간에서 삽입과 삭제가 빈번하게 일어나는 경우 연결 리스트의 사용을 고려해볼 수 있다.

<배열 vs 연결리스트>

저장공간 : 연속한 위치 vs 임의의 위치
특정 원소 탐색 : 매우 간편 O(1) vs 선형탐색과 유사 O(n)

<연결리스트 연산>

1. 특정 원소 참조 (k번째)

 def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    i = 0
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1
    return curr

2. 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while(curr.next):
        curr = curr.next
        result.append(curr.data)
    return result

3. 길이 얻어내기

def getLength(self):
    return self.nodeCount

4. 원소 삽입 (index)

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)

4-1. 원소 삽입 (node)

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

5. 원소 삭제 (index)

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError  
    prev = self.getAt(pos - 1)        
    return self.popAfter(prev)

5-1. 원소 삭제 (node)

def popAfter(self, prev):
    curr = prev.next
    if curr is None:
        return None
    if curr.next is None:
        if self.nodeCount == 1:
            self.tail = None
        else:
            self.tail = prev
    prev.next = curr.next
    self.nodeCount -= 1
    return curr.data

6. 두 리스트 합치기

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

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

연결 리스트에서 Link를 하나 더 추가하여 앞 뒤로 연결한 리스트. head 뿐만 아니라 tail에도 dummy node를 추가.

1. 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result

1-1. 리스트 역순회

def reverse(self):
	result = []
    curr = self.tail
    while curr.prev.prev:
    	curr = curr.prev
        result.append(curr.data)
    return result

2. 원소 삽입 (node)

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

2-2. 원소 삽입 (index)

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

3. 특정 원소 얻어내기

def getAt(self, pos):
	if pos < 0 or pos > self.nodeCount:
    	return None
	if pos > self.nodeCount // 2:
    	i = 0
        curr = self.tail
        while i < self.nodeCount - pos + 1:
        	curr = curr.prev
            i += 1
    else:
    	i = 0
        curr = self.head
        while i < pos:
        	curr = curr.next
            i += 1
	return curr

스택 (Stack)

자료를 보관할 수 있는 선형 구조, 단 데이터 입력과 출력이 한 쪽 끝에서만 수행된다(LIFO). 배열을 이용하여 구현하거나 양방향 연결 리스트를 이용하여 구현할 수 있다.

<스택 연산>

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

수식의 후위 표기법

중위 표기법 (infix) : (A+B) (C+D)
후위 표기법 (postfix) : AB+CD+

중위 표기를 후위 표기로 바꾸는 법

피연산자를 만날 경우 식에 추가

연산자를 만났을 경우 스택이 비어있을 경우 스택에 push 스택이 비어있지 않을 경우 스택의 연산자와 우선순위를 비교

스택의 연산자가 우선순위가 높을 경우 : 스택의 연산자를 pop, 추가된 연산자를 push
3-1. 추가된 연산자가 우선순위가 높을 경우 : 추가된 연산자를 push
3-2. 우선순위가 같을 경우 : 스택의 연산자 pop, 추가된 연산자 push

여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop

마지막에 스택에 남아 있는 연산자 모두 pop, 출력