(23.04.11) 자료구조/알고리즘2 - 연결리스트, 스택

TIL은 그날 하루 본인이 어떤 공부를 하였는지 파악하기 위함입니다.
상세하게 기록하여 이후 본인이 어떤 공부를 어떻게 하였는지 파악할 수 있도록 하는 것이 중요합니다.

 

학습 주제

1. LinkedList와 DoublyLinkedList 의 ADT를 구현해본다

- position 정보을 받아 *단방향 LinkedList 를 구현

- dummy head Node를 추가하고, Node 정보를 받아  단방향 LinkedList를 개선

- dummy head/tail Node를 추가하여 양방향 LinkedList 를 구현

 

2. Stack의 ADT와 응용 알고리즘을 구현해본다

- Stack은 Array (Python의 List) 혹은 LinkedList 로 구현 가능하다

- Stack을 응용하여 중위 표기식을 후위 표기식으로 변형하고 연산한다 

 

 

*Head Node 의 인덱스를 1로 구현 하면 편하다 ⇒ 개선시 Dummy Node를 위해 0을 비움

---

주요 메모 사항 

추상적 자료구조 (Abstract data type, ADT)

- 데이터를 저장하고 조작하기 위한 연산의 모음 (자료구조의 추상적 특징)

- 내부구현은 명시하지 않음

 

연결리스트(Linked List)

- 데이터들이 선처럼 일렬로 늘어선 형태

- 선형배열과 유사하나 번호칸이 아닌, 원소를 엮어서 관리하는 형태

- 원소의 삽입/삭제가 용이하다

- 선형배열 대비 메모리 요구량이 크고, 특정 원소를 참조하는데 오랜 시간이 걸린다

 

연결리스트 ADT의 연산	시간 복잡도 (*단방향)
특정원소 참고	O(n)
리스트 순회	O(n)
길이 얻어내기	-
원소삽입	맨앞 - O(1) 중간 - O(n) 맨끝 - O(1)
원소삭제	맨앞 - O(1) 중간 - O(n) 맨끝 - O(n)
두 리스트 연결	-

class Node:
	def __init__(self,item):
			self.data = item
			self.next = None

class LinkedList:
	def __init__(self):
			self.nodeCount = 0
			self.head = None
			self.tail = None

# 개선된 LinkedList
class LinkedList:
	def __init__(self):
			self.nodeCount = 0
			self.head = Node(None)
			self.tail = None
			self.head.tail = self.tail

 

 

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

- 다음 Node , 이전 Node 로 진행할 수 있는 연결 리스트

- 처음과 끝에 Dummy node를 두면, 모든 노드는 같은 모양을 가져 연산을 구현하기 편리하다

class Node:
	def __init__(self, item):
		self.data = item
		self.prev = None
		self.next = None

class DoublyLinkedList:
	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None)
		self.tail = Node(None)
		self.head.prev = None
		self.head.next = self.tail
		self.tail.prev = self.head
		self.tail.next = None

- 리스트 마지막에 원소를 삽입할 때 head 순차적으로 조회하지 말고 tail 에서 접근하여 개선할 수 있다

• 노드의 위치가 절반보다 작으면 앞에서 부터
• 노드의 위치가 절반보다 크면 뒤에서 부터

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)

스택의 ADT	설명
push(x)	- 한쪽 끝에서 데이터 x를 추가함 - stack overflow
pop()	- 맨 위에 저장된 데이터 원소를 제거 및 반환 - stack underflow
size()	현재 스택에 들어 있는 원소의 수를 구함
isEmpty()	스택이 비어있는지 확인
peek()	맨 위에 저장된 데이터 원소를 확인

- Stack 이 구현된 라이브러리

from pythonds.basic.stack import Stack
s = Stack()

스택의 응용 - 수식의 후위 표기법

• 목표
  • 중위 표현식 을 후위 표현식으로 바꾼다
  • A * B + C → A B * C +
  • A + B * C → A B C * +
• 방법
  • 중위 표현식을 한 글자씩 순차적으로 읽는다
  • 피연산자는 출력한다
  • 연산자는 Stack 에 쌓는다
  • 다른 연산자를 만난 경우
    • 우선순위가 높은 것을 출력하고 아닌 것은 Stack에 쌓는다
    • 같은 우선순위를 가진 경우, Stack에 쌓인 연산자를 꺼내 출력한다
  • 중괄호를 만난 경우
    • 여는 괄호는 Stack에 쌓는다
    • 닫는 괄호를 만날때까지 기호를 쌓고, 만난 경우 연산기호를 출력한다

스택의 응용 - 후위 표기법 연산

• 목표
  • 중위 표현식 을 후위 표현식으로 바꾼다
  • A * B + C → A B * C +
  • A + B * C → A B C * +
• 방법
  • 수식을 왼쪽부터 시작해서 오른쪽으로 차례대로 읽어들이면서
  • 피연산자가 나타나면, 스택에 넣어 둔다.
  • 연산자가 나타나면, 스택에 들어 있는 피연산자를 두 개 꺼내어 연산을 적용하고, 그 결과를 다시 스택에 넣어 둔다.

---

공부하며 어려웠던 내용

 

Python List 의 append 함수 동작방식

- 시스템에 더 큰 메모리 공간을 할당한 뒤, 값을 새로운 메모리에 복사한다. (기존 메모리 공간은 해제)
- append 메서드를 사용할 때마다 재할당, 복사를 수행해 메모리적으로 비효율적일 수 있다.

- 다만 List의 크기가 작은 경우 큰 차이가 나지 않으며, 크기가 매우 큰 경우 미리할당하는 것이 좋은 방법일 수 있다.