📖 오늘의 학습

• 자료구조 : 연결리스트, 양방향 연결리스트, 스택

---

자료구조

1. 연결리스트 (Linked list)

• 삽입과 삭제가 쉽고 빠르게 이루어진다.
• 단, 인덱스로 위치를 찾으려면 그 인덱스까지 탐색해야하므로 탐색에는 비효율적
  -> 변형된 연결리스트를 사용하고 새로운 method를 생성
• 거꾸로 가지는 못함
  -> 이를 보완하기 위한 것 : 양방향 연결리스트(Doubly linked list)

배열과 연결리스트 비교

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

연결리스트의 추상적 자료구조 만들기

• 2개의 클래스를 이용한다.
  • Node
  • LinkedList

연산 정의

1. 특정원소 참조

   • 인덱스는 왜 1부터 시작하는 것이 좋은가?
     -> 보완된 연결리스트인 양방향 연결리스트에서 dummy node를 채우고 거기에 인덱스 0을 부여하기 위함

2. 리스트 순회

   • 순서대로 노드를 방문

3. 리스트 길이 얻어내기

4. 원소 삽입

   • 빠르게 원소를 삽입, 삭제하는 것이 선형 배열에 비해 가지는 이점이다.
   • 삽입과 삭제를 위해서는 앞, 뒤의 링크를 조정해주어야 한다.
   • 맨 앞, 맨 뒤의 경우 링크의 조정을 따로 고려해야 한다.

   구현절차
   newNode가 삽입되고자 하는 pos위치의 이전에 있는 node를 prev라고 하고 이후에 있는 node를 next라고 하자.

   1. newNode의 링크를 prev의 다음 node인 next를 가리키게 한다. (prev와 newNode모두 next를 가리키고 있는 상태)
   2. prev의 링크를 newNode로 설정한다.
      (이제 prev -> newNode -> post 순서)
   3. newNode가 prev와 post 사이에 들어가서 한 개의 node가 추가되었으니 nodeCount의 갯수를 올린다.

5. 원소 삭제

   • 원소의 삽입과 마찬가지로 링크의 조정이 필요함.
     맨 앞, 맨 뒤, 중간으로 나눠서 처리
   • 유일한 노드를 삭제할 때 어떻게 해야하는가?
     - 맨 뒤의 노드를 삭제 할 경우 tail의 prev를 알아야하기 때문에 결국 순차적으로 조회가 필요함. 삽입과 달리 O(n)의 시간복잡도를 가짐

6. 두 리스트 합치기

   • 이어 붙이려는 리스트의 tail이 최종 tail이 된다.
   • 이어 붙이려는 리스트가 비어있을 경우 None이기 때문에 예외처리가 필요함

코드 구현

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

    # 1. 특정 원소 참조 - pos 번째에 있는 노드를 리턴한다
	def getAt(self, pos):
		# 연결리스트 범위에 벗어나면 None 리턴한다
		if pos <= 0 or pos > self.nodeCount:
			return None
		
		# 인덱스를 만들고 인덱스가 pos만큼 다다를때까지 순환하고 마지막 curr를 리턴한다.
		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1
		return curr
        
   # 2. 리스트 순회     
   def traverse(self):
        tlist = []
        if self.nodeCount == 0: return tlist
        curr = self.head
        while True:
            # 노드 자체가 아니라 노드의 데이터를 넣어야한다...
            tlist.append(curr.data) 
            curr = curr.next
            if curr is None:
                break
        return tlist
        
   # 4. 원소 삽입
   def insertAt(self, pos, newNode):
       # pos가 가리키는 위치에 NewNode를 삽입, 성공과 실패에 따라 True나 False를 리턴

       # pos의 범위가 유효한지 체크
       if pos < 1 or pos > self.nodeCount + 1:
           return False

       # 맨 앞에 놓는 경우
       if pos == 1:
           newNode.next = self.head
           self.head = newNode
       # 맨 뒤에 놓는 경우
       elif pos == nodeCount + 1:
           self.tail.next = newNode
           self.tail = newNode
       else:
           prev = getAt(pos -1)
           newNode.next = prev.next
           prev.next = newNode

       self.nodeCount += 1
       return True
       
   # 5. 원소 삭제    
   def popAt(self, pos):
       if pos < 1 or pos > self.nodeCount:
           raise IndexError
       curr = None
       if pos == 1:
           curr = self.head
           if self.nodeCount == 1:
               self.head = None
               self.tail = None
           else:
               self.head = self.head.next
       else:
           prev = self.getAt(pos - 1)
           curr = prev.next
           prev.next = curr.next
           if pos == self.nodeCount:
               self.tail = prev
       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       

이와 같이 구현한 연결리스트는 인덱스로 위치를 찾으려면 그 인덱스까지 탐색해야하므로 탐색에는 비효율적이므로 보완하기 위한 변형된 연결리스트를 생성한다.

조금 변형된 연결리스트

• 새로운 메서드 생성 : insertAfter(prev, newNode), popAfter(prev)
  인덱스를 알려주는 것이 아니라 node를 지정하여 알려줌으로써 선형탐색하지 않아도 됨
  - 여기서 생기는 문제 = 맨 앞에는 어떻게 ?
  이를 위해 변형된 연결리스트를 생성함
  - 맨 앞에 dummy node를 추가한 형태
• 삽입, 삭제를 위한 탐색을 효율적으로 하기 위함

코드 구현

class Node:

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


class LinkedList:

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


	def __repr__(self):
		if self.nodeCount == 0:
			return 'LinkedList: empty'

		s = ''
		curr = self.head
		while curr.next:
			curr = curr.next
			s += repr(curr.data)
			if curr.next is not None:
				s += ' -> '
		return s


	def getLength(self):
		return self.nodeCount


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


	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


	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)


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

2. 양방향 연결리스트 (Doubly linked list)

• 말그대로 노드의 양방향으로 연결되어 있다.
• next 뿐만 아니라 prev 도 알 수 있어 더 효율적으로 삽입, 삭제가 가능하다
• 하지만 삽입, 삭제하는 연산에서 앞, 뒤의 링크를 조정해줘야해서 조금 번거롭다.
• 시스템의 운영체제에서 주로 활용됨 ex) 아이폰의 실행중인 앱
• 맨 앞과 맨 뒤에 dummy 노드를 추가한다

연산 정의

1. 리스트 순회
2. 원소 삽입
3. 원소 삭제
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 reverse(self):
        result = []
        if self.nodeCount == 0: return result
        curr = self.tail.prev
        while curr.prev:
            result.append(curr.data)
            curr = curr.prev
        return result

    # k번째 노드 반환
    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

    # prev 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

    # pos번째에 새로운 노드 추가 (insertAfter를 활용)
    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)

    # next 노드 뒤에 새로운 노드 추가
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    # prev노드 다음 노드를 삭제하고 그의 값을 반환
    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

   # next노드 이전 노드를 삭제하고 그의 값을 반환
    def popBefore(self, next):
        curr = next.prev
        prev = curr.prev
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

    # pos위치의 노드를 삭제하고 그의 값을 반환 
    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos - 1)
        return self.popAfter(prev)
   
    # 주어진 리스트를 이어붙인다
    def concat(self, L):
        prev = self.tail.prev
        next = L.head.next
        prev.next = next
        next.prev = prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount

3. 스택 (Stack)

• LIFO (Last-in First-out) 후입선출 구조, 맨 마지막에 들어간게 먼저 나온다
• 원소를 넣고(push) 꺼낸다(pop)

스택의 응용

• 수식의 중위 표기법을 후위 표기법으로 변환, 계산
• 수식을 하나씩 읽어가면서 중위 표기법을 후위 표기법으로 변환한다.

코드구현

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]


def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens


def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []
    
    for t in tokenList:
        if t == '(':
            opStack.push(t)
        elif t == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        elif type(t) is int:
            postfixList.append(t)
        else:
            while not opStack.isEmpty() and prec[opStack.peek()] >= prec[t]:
                postfixList.append(opStack.pop())
            opStack.push(t)
        
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
        
    return postfixList


def postfixEval(tokenList):
    opStack = ArrayStack()
    for t in tokenList:
        if type(t) is int:
            opStack.push(t)
        else:
            right = opStack.pop()
            left = opStack.pop()
            val = 0
            if t == '+':
                val = left + right
            elif t == '-':
                val = left - right
            elif t == '*':
                val = left * right
            elif t == '/':
                val = left / right
            opStack.push(val)
    return opStack.pop()

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val

---

📝 주요메모사항

---

😵 공부하면서 어려웠던 내용

연결리스트 원소 삭제 메소드 구현

• 원소 삽입과는 인덱스 유효 구간이 다르므로 유일하게 있는 원소를 삭제하려고 할 때 head, tail의 링크를 조정해주는게 까다로웠음