✏️ 오늘 학습한 내용

1. Linked List
2. Doubly Linked List
3. Stack

---

🔎 Linked List

1) Node의 구성

• Data
• Link(next)

2) 일반적인 LinkedList의 구성

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

3) Array vs Linked List

	Array	Linked List
저장 공간	연속한 위치	임의의 위치
특정 원소 지칭	O(1)	O(N)

4) Single Linked List의 시간 복잡도

	시간 복잡도
access	O(N)
search	O(N)
insert	O(1)
delete	O(1)

Linked List의 장점은 삽입과 삭제가 유연하다는 것이지만,
Single Linked List의 경우, 접근 후에 삽입 혹은 삭제를 진행할 수 있으므로
결국 현실적인 시간복잡도는 O(N)이다.

---

🔎 Doubly Linked List

1) Doubly Linked List의 구조

단방향으로만 연결했던 Single Linked List와 달리 양방향으로 노드를 연결한 구조

2) Doubly Linked List의 시간 복잡도

	시간 복잡도
access	O(N/2) == O(N)
search	O(N/2) == O(N)
insert	O(1)
delete	O(1)

이전 노드로의 포인터가 추가되어 사실 탐색의 시간을 절반으로 줄일 수 있게 되었으나,
결국, Big O 표기법에 의하면 O(N)이다.

3) Single Linked List 간 차이

• 탐색, 접근의 유연성이 훨씬 좋아짐.
• 추가 포인터로 인한 더 많은 메모리가 요구됨.

4) 구현

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
        
    # 순회
    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

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

	# pos 번째의 노드 반환
    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
        
    # 노드 추가
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
        
    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

    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)
        
    # 노드 삭제
    def popBefore(self, next):
        curr = next.prev
        data = curr.data
        next.prev = curr.prev
        curr.prev.next = curr.next
        self.nodeCount -= 1
        return data
        
    def popAfter(self, prev):
        curr = prev.next
        data = curr.data
        prev.next = curr.next
        curr.next.prev = curr.prev
        self.nodeCount -= 1
        return data

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

---

🔎 Stack

1) Stack의 구조

• 자료를 보관할 수 있는 선형 구조
• LIFO(Last In First Out) : 마지막에 넣은 것을 먼저 빼는 방식

2) 발생 가능한 오류

• Stack Overflow : 범위를 초과해서 원소를 넣을 때 발생
• Stack Underflow : 비어있는 스택에서 원소를 꺼내려할 때 발생

3) 구현

• Array -> Stack

  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]

• Doubly Linked List -> Stack

  from doublylinkedlist import DoublyLinkedList
  from doublylinkedlist import Node

  class LinkedListStack:

      def __init__(self):
          self.data = DoublyLinkedList()

      def size(self):
          return self.data.getLength()

      def isEmpty(self):
          return self.size() == 0

      def push(self, item):
          node = Node(item)
          self.data.insertAt(self.size() + 1, node)

      def pop(self):
          return self.data.popAt(self.size())

      def peek(self):
          return self.data.getAt(self.size()).data