jupyter/3-3.4 ListSorted&Iterator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "먼저 알 것은 성경의 모든 예언은 사사로이 풀 것이 아니니 예언은 언제든지 사람의 뜻으로 낸 것이 아니요 오직 성령의 감동하심을 받은 사람들이 하나님께 받아 말한 것임이라 (벧후1:20-21)\n",
    "\n",
    "-------\n",
    "<center><img src=\"https://github.com/idebtor/DSpy/blob/6b3676c3de29f85d2e7f30679676d1fd96d88b17/images/WelcomeToDataStructures.jpg?raw=true\" width=1000></center>\n",
    "\n",
    "__NOTE:__ The following materials have been compiled and adapted from the numerous sources including my own. Please help me to keep this tutorial up-to-date by reporting any issues or questions. Send any comments or criticisms to `idebtor@gmail.com` Your assistances and comments will be appreciated.\n",
    "\n",
    "--------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b style=\"font-size:30px\">  Chapter 3. Linear Data Structures (선형 자료구조)</b>\n",
    "\n",
    ": 선형 자료구조란 무엇인가 (스택,큐,리스트 등)  \n",
    "\n",
    "--------------\n",
    "제 3장에서는 선형 자료구조에 대해 알아봅니다. 선형 자료구조란 무엇이며, 자료구조에 사용되는 대표적인 선형 자료구조들을 배우고 간단한 실습을 통해 구현해보며 익히게 됩니다. 자료구조의 기초가 되며, 이후 운영체제, 알고리즘, 네트워크 등 모든 영역에 활용되는 것 이므로 적극적인 자세로 재밌게 배우면 좋겠습니다!\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 리스트\n",
    "\n",
    "1.1. 정렬된 링크드 리스트 추상자료형  \n",
    "1.2. 정렬된 링크드 리스트 구현"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 정렬된 링크드 리스트 추상자료형\n",
    ": 정렬된 링크드 리스트 추상자료형의 구조와 메서드를 배웁니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이번엔 리스트 중에서 정렬된 링크드 리스트에 대해 배워보도록 하겠습니다. 이전 페이지에서 사용된 성적 예시를 사용한다면, 정렬된 링크드 리스트에서는(오름차순) 17, 26, 31, 54, 77, 93으로 이루어질 것이며, 17이 가장 작은 원소이므로 맨 앞에, 93이 가장 큰 원소이므로 가장 뒤에 있게 됩니다.\n",
    "정렬된 링크드 리스트의 구조는 원소의 컬렉션으로서, 각 원소의 상대적인 위치가 그 특징에 따라 정해지는 구조를 갖습니다. 정렬된 링크드 리스트에서 사용되는 연산은 다음과 같은 것들이 있습니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `ListSorted()`: 비어있는 정렬된 링크드 리스트를 생성합니다. 별다른 파라미터를 받지 않고 빈 리스트를 반환합니다.\n",
    "* `push(item)`: 리스트의 정렬이 유지 되도록 새로운 원소를 추가합니다. 추가할 원소를 받고 값을 반환하진 않습니다.\n",
    "* `pop_front()`: 리스트의 가장 첫번째 원소를 제거하고, 제거한 값을 반환합니다. 삭제할 원소를 찾지 못하면 `None`을 반환합니다. \n",
    "* `pop_back()`: 리스트의 가장 마지막 원소를 제거하고, 그 값을 반환합니다. \n",
    "* `pop(item)`: 주어진 원소를 리스트에서 제거하고, 그 값을 반환합니다. 삭제할 원소를 찾지 못하면 `None`을 반환합니다. \n",
    "* `find(item)`: 리스트에서 원하는 원소를 찾습니다. 찾고싶은 원소를 받아 리스트에 있는지 참/거짓 값으로 반환합니다.\n",
    "* `is_empty()`: 리스트가 비어있는지 확인합니다. 별다른 파라미터를 받지 않고 참/거짓 값을 반환합니다.\n",
    "* `size()`: 리스트에 있는 원소의 갯수를 확인합니다. 정수값을 반환합니다.\n",
    "* `index(item)`: 리스트에서 해당 원소의 위치를 찾아 인덱스를 반환합니다. 해당 원소를 찾지 못하면 `None`을 반환합니다. \n",
    "* `remove(pos)`: 리스트에서 특정 위치의 원소를 제거하고 그 값을 반환합니다. 삭제할 원소를 찾지 못하면 `None`을 반환합니다. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 정렬된 링크드 리스트 구현\n",
    ": 파이썬으로 정렬된 링크드 리스트를 직접 구현해봅니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "정렬된 링크드 리스트를 구현하기 위해선, 원소들이 특정 특성을 기준으로 상대적인 위치를 갖는다는 것을 염두해둬야 합니다. 시험점수 예제(17,26,31,54,77,93)를 연결된 구조로 표시하면 그림 1과 같을 것입니다. 이번에도 마찬가지로, 노드와 연결된 구조를 사용하는 것은 여러 원소의 상대적인 위치를 나타내는 것에 가장 이상적인 방식입니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><img src=\"https://github.com/idebtor/DSpy/blob/main/images/chap3/ch3-32.jpg?raw=true\" width=\"600\" title=\"Figure 1. An Sorted Linked List\"></center>\n",
    "<center>그림 1. 정렬된 링크드 리스트의 예<center><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "정렬된 링크드 리스트인 `ListSorted` 클래스를 구현하기 위해선, 앞서 `ListUnsorted`를 구현한 것과 비슷한 방식을 사용하겠습니다. 이번에도 마찬가지로, 비어있는 리스트는 head의 참조값이 None을 갖게 될 것입니다(목차 1 참고)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 목차 1\n",
    "class ListSorted:\n",
    "    def __init__(self):\n",
    "        self.head = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "정렬된 링크드 리스트의 메서드 중 `is_empty`와 `size` 메서드는 단순히 노드의 갯수를 다루기 때문에 이전에 구현한 코드를 그대로 사용할 수 있습니다. 또한, `remove` 메서드 역시 특정 원소를 찾아 제거하는 것은 동일하기 때문에 이전 코드를 그대로 사용할 수 있을 것입니다. 따라서, 정렬된 링크드 리스트의 메서드 중 남은 메서드는 `find`와 `push`이며, 이 두 메서드는 수정이 필요합니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "언뜻 보기엔 `find` 메서드도 `ListUnsorted` 링크드 리스트와 마찬가지로 같은 알고리즘으로 구현이 가능하다는 생각이 들것입니다. 사실 그것이 맞습니다. 노드를 차례대로 탐색(traverse)하며 해당 데이터가 우리가 찾는 데이터인지 확인하는 것이기 때문입니다. 하지만 정렬된 링크드 리스트에서는 이를 더 효율적으로 구현할 수 있습니다. 정렬된 링크드 리스트는 특정한 특징으로 원서가 나열되었기 때문에, 우리가 특정 값을 찾으려고 할 때, 그 탐색 범위가 줄어들 수 있습니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "예를 들어, 시험점수 예제에서 45라는 값을 찾으려고 한다고 가정합시다(그림 2 참고). 리스트를 head에서부터 탐색하는 가운데, 찾고자하는 데이터 값과 비교대상이 되는 노드의 값은 점진적으로 커질 것입니다. 따라서, 어느 순간 노드의 데이터 값이 우리가 찾고자하는 데이터 값과 일치하거나 그보다 클 경우, 이후 노드들은 무조건 일치할 수 없기 때문에 탐색을 멈출 수 있게 됩니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><img src=\"https://github.com/idebtor/DSpy/blob/main/images/chap3/ch3-33.jpg?raw=true\" width=\"600\" title=\"Figure 2. Searching an Sorted Linked List\"></center>\n",
    "<center>그림 2. 정렬된 링크드 리스트의 탐색 예<center><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "목차 2는 `find` 메서드의 파이썬 구현을 나타냅니다. 앞서 설명한 새로운 기능의 추가는 단순히 `stop`이라는 불리언 변수를 추가하여 해결할 수 있습니다. 탐색 중 노드의 데이터 값이 찾고자하는 값보다 크게 된다면, `stop`을 True로 바꾸어 탐색을 중지시킬 수 있습니다. 나머지 코드의 구현은 이전과 동일합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 목차 2\n",
    "def find(self,item):\n",
    "    current = self.head\n",
    "    found = False\n",
    "    stop = False\n",
    "    while current != None and not found and not stop:\n",
    "        if current.get_data() == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if current.get_data() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                current = current.get_next()\n",
    "\n",
    "    return found"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "정렬된 링크드 리스트의 구현 중 가장 신경을 많이 써야하는 메서드는 `push`입니다. 이전에 배운 `Listunsorted` 리스트에서는 노드의 추가가 가장 쉬운 부분, 즉 head에서 이루어졌지만, 정렬된 링크드 리스트의 경우 그 정렬을 보존해야하기 때문에 추가를 하는 위치가 굉장히 중요합니다. 따라서, 데이터의 특성을 고려하여, 기존 리스트에서 추가하기에 적합한 위치를 찾고, 그곳에 정확히 노드를 추가해야합니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "시험 점수 예제에서 31이라는 값을 추가한다고 가정해봅시다. 이때, `push`메서드는 적절한 위치인 26과 54 사이에 31을 넣어야 할 것입니다. 그림 3은 이 과정을 그림으로 나타낸 것입니다. 적절한 위치를 찾는 과정에서, 노드의 값이 추가하는 값보다 크거나 마지막 노드인 경우 탐색을 멈추어야합니다. 이 경우, 31보다 큰 54를 마주할 때 탐색을 멈출 것입니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><img src=\"https://github.com/idebtor/DSpy/blob/main/images/chap3/ch3-34.jpg?raw=true\" width=\"600\" title=\"Figure 3. Adding an Item to an Sorted Linked List\"></center>\n",
    "<center>그림 3. 정렬된 링크드 리스트의 노드 추가 예시<center><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "목차 3은 `push` 메서드를 파이썬으로 구현한 것입니다. `ListUnsorted` 구현과 같이, 두개의 참조 변수 `previous`와 `current`를 사용 할 것입니다. 먼저 current 변수를 사용하여 탐색을 할 때, 추가하려는 데이터 값과 노드의 값을 비교하여 탐색을 계속할지, 중단할지 결정하게됩니다. 탐색이 중단되면 그 위치에 새로운 노드를 추가하게 됩니다.  \n",
    "\n",
    "새로운 노드의 추가 과정은 그림 3과 같이 2 단계로 이루어집니다. 추가할 데이터를 담은 새로운 노드를 생성한 후, 이전 노드와 새로 만든 노드의 링크를 수정하여 추가를 합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 목차 3\n",
    "def push(self,item):\n",
    "    current = self.head\n",
    "    previous = None\n",
    "    stop = False\n",
    "    while current != None and not stop:\n",
    "        if current.get_data() > item:\n",
    "            stop = True\n",
    "        else:\n",
    "            previous = current\n",
    "            current = current.get_next()\n",
    "\n",
    "    temp = Node(item)\n",
    "    if previous == None:\n",
    "        temp.set_next(self.head)\n",
    "        self.head = temp\n",
    "    else:\n",
    "        temp.set_next(current)\n",
    "        previous.set_next(temp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`ListSorted()` 클래스에서 현재까지 다룬 내용을 구현한 코드는 다음과 같습니다. 나머지 메서드는 여러분이 직접 추가해보시길 바랍니다. `ListUnsorted` 리스트와 달리, `ListSorted()`에서 동일한 메서드가 구현될지 고민해보고 구현해보시길 바랍니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self._data = data\n",
    "        self._next = None\n",
    "\n",
    "    def get_data(self):\n",
    "        return self._data\n",
    "    \n",
    "    def set_data(self, data):\n",
    "        self._data = data\n",
    "\n",
    "    def get_next(self):\n",
    "        return self._next\n",
    "\n",
    "    def set_next(self, next):\n",
    "        self._next = next\n",
    "\n",
    "\n",
    "class ListSorted:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.get_data() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.get_data() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.get_next()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def push(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.get_data() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.get_next()\n",
    "\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.set_next(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.set_next(current)\n",
    "            previous.set_next(temp)\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.get_next()\n",
    "\n",
    "        return count\n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    mylist = ListSorted()\n",
    "    mylist.push(31)\n",
    "    mylist.push(77)\n",
    "    mylist.push(17)\n",
    "    mylist.push(93)\n",
    "    mylist.push(26)\n",
    "    mylist.push(54)\n",
    "\n",
    "    print(mylist.size())      # 6\n",
    "    print(mylist.search(93))  # True\n",
    "    print(mylist.search(100)) # False    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterable & Iterator\n",
    "\n",
    "- **Iterable**은 반복 가능한 객체를 말합니다. \n",
    "    - 예를 들면, 파이썬 타입들 중에서 list, dict, set, str, bytes, tuple, range 타입의 객체들은 iterable합니다. \n",
    "    - iterable한 객체는 for loop에서 하나씩 값을 꺼낼 때 활용됩니다. \n",
    "    - 물론, 사용자가 만들어 내는 클래스도 iterable한 객체를 생성할 수 있도록 코딩해야 할 때가 있습니다. 그렇게 하려면, 클래스는 반드시 __iter__() 메소드를 구현해야 합니다. \n",
    "    - 아래와 같이 내장함수 `dir()`로 사용하여 객체가 가지고 있는 매직 매소드를 살펴보면, `__iter__`가 존재하는 것을 알 수 있습니다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']\n"
     ]
    }
   ],
   "source": [
    "alpha = ['a', 'b', 'c']\n",
    "print(dir(alpha))            # __iter__() must exist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Iterator**는 클래스 객체를 말하며, 값을 차례대로 꺼낼 수 있는 객체를 Iterator라고 부릅니다.  \n",
    "    - iterator는 iterable한 객체를 파이썬 내장함수 즉 `iter()` 또는 iterable한 객체의 메소드 즉 `__iter__()` 메소드로 객체를 생성할 수 있습니다.  \n",
    "    - 그러므로, Iterator에는 다음 값을 반환할 수 있는 `__next__` 메소드가 반드시 있어야 합니다. \n",
    "    - 아래와 같이 내장함수 `dir()`로 사용하여 객체가 가지고 있는 매직 매소드를 살펴보면, `__iter__`와 `__next__`가 존재하는 것을 알 수 있습니다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__length_hint__', '__lt__', '__ne__', '__new__', '__next__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setstate__', '__sizeof__', '__str__', '__subclasshook__']\n"
     ]
    }
   ],
   "source": [
    "it = iter(['a', 'b', 'c'])\n",
    "print(dir(it))             # __iter__() and __next__() must exist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iteratable 객체로 iterator를 만들기 \n",
    "- Iterable 객체는 iterator를 만들 수 있는 `__iter__()` 메소드를 반듯이 가지고 있어서, 이를 이용하면, iterator를 만들수 있습니다. \n",
    "- 또한 파이썬 내장함수 `iter()`를 사용해도 iterator 객체를 만들수 있습니다. \n",
    "- 또한 파이썬 내장함수 `next()`를 통해 iterator에서 하나씩 값을 꺼내 올 수 있습니다\n",
    "- 더이상 가져올 값이 없을 경우에는 `StopIteration` 이라는 예외가 발생합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'list_iterator'>\n",
      "['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__length_hint__', '__lt__', '__ne__', '__new__', '__next__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setstate__', '__sizeof__', '__str__', '__subclasshook__']\n"
     ]
    }
   ],
   "source": [
    "# list 객체로 iterator 만들기 \n",
    "alpha = ['a', 'b', 'c']\n",
    "it_alpha = alpha.__iter__()       # ialpha = iter(alpha)  \n",
    "print(type(it_alpha))\n",
    "print(dir(it_alpha)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 위와 같이 내장함수 `dir()`로 객체가 가지고 있는 매직 매소드를 살펴보면, `__iter__`와 `__next__`가 존재하는 것을 알 수 있습니다. \n",
    "- 이를 사용하여 iterable 객체에서 값들을 꺼내올 수 있으며, iterable객체에 존재하지 않는 값을 꺼내려고 하면, 아래와 같이  `StopIteration` 오류가 나타납니다.   \n",
    "\n",
    "```\n",
    "------------------------------------------------------------\n",
    "StopIteration              Traceback (most recent call last)\n",
    "~\\AppData\\Local\\Temp/ipykernel_15488/1959682419.py in <module>\n",
    "      4 print(next(ialpha))\n",
    "      5 print(next(ialpha))\n",
    "----> 6 print(next(ialpha))         # StopIteration occurs\n",
    "\n",
    "StopIteration: \n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "c\n"
     ]
    },
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_42444/3659533354.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mit_alpha\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mit_alpha\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mit_alpha\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m         \u001b[1;31m# StopIteration occurs\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "alpha = ['a', 'b', 'c']\n",
    "it_alpha = iter(alpha)        # ialpha = alpha.__iter__(alpha)\n",
    "print(next(it_alpha))         # iterator works here\n",
    "print(next(it_alpha))\n",
    "print(next(it_alpha))\n",
    "print(next(it_alpha))         # StopIteration occurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 이런 예외처리를 이용하여 아래와 같이 코딩할 수 있습니다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "c\n",
      "Success\n"
     ]
    }
   ],
   "source": [
    "alpha = ['a', 'b', 'c']\n",
    "it_alpha = iter(alpha)\n",
    "while True:\n",
    "    try:\n",
    "        item = next(it_alpha)\n",
    "        print(item)\n",
    "    except StopIteration:\n",
    "        break\n",
    "print(\"Success\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "파이썬의 for문은 내부적으로  `__iter__` 메소드 이용하여 Iterator를 생성하여 동작합니다. 예를들어 리스트를 순회하는 for문이라 하면, 해당 리스트(iterable)객체로부터 Iterator를 생성한 다음 `__next__` 메소드를 이용해 순회를 도는 방식입니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Range 클래스 생성 예제: Iterator and Iterable\n",
    "\n",
    "1.  먼저 Range 클래스를 정의할 때 `__next__` 메소드를 구현하고, next() 메소드가 작동하는지 확인합니다.\n",
    "1.  `__iter__` 메소드를 추가하여 Iterable한 객체를 생성할 수 있도록 하고, iterable한지 확인합니다. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterator Range 클래스 생성하기\n",
    "Iterator 클래스에는 다음 값을 반환할 수 있는 `__next__` 메소드가 반드시 있어야 합니다. \n",
    "- 우선 Iterator 클래스를 먼저 만듭니다.\n",
    "\n",
    "    - `__init__` 메소드를 통해 입력받은 값(end)을 저장하고, \n",
    "    - `__iter__` 메소드에서는 Iterator객체를 반환하도록 구현합니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Sample Run__\n",
    "```\n",
    "if __name__ == \"__main__\":\n",
    "    nums = Range(1, 4)\n",
    "    print(next(nums))\n",
    "    print(next(nums))\n",
    "    print(next(nums))\n",
    "    #print(next(nums))   # This should invoke StopIteration exception     \n",
    "```\n",
    "__Expected Output__\n",
    "```\n",
    "1\n",
    "2\n",
    "3\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class Range:\n",
    "    def __init__(self, start, end):\n",
    "        self.value = start\n",
    "        self.end = end\n",
    "    \n",
    "    def __next__(self):              # this makes iterator object        \n",
    "        if self.value >= self.end:  \n",
    "            raise StopIteration\n",
    "        current = self.value\n",
    "        self.value += 1\n",
    "        return current\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = Range(1, 3)\n",
    "    print(next(nums))\n",
    "    print(next(nums))\n",
    "    print(next(nums))       \n",
    "    #print(next(nums))   # This should invoke StopIteration exception"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterable Range 클래스 생성하기\n",
    "\n",
    "위의 Range가 만들어 내는 객체는 아직 iterable 하지 않습니다. 그렇게 때문에 다음 코드는 실패합니다. \n",
    "\n",
    "__Sample Run:__\n",
    "```\n",
    "for num in nums:\n",
    "    print(num)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Expected Output:__\n",
    "```\n",
    "-------------------------------------------------------------------\n",
    "TypeError                         Traceback (most recent call last)\n",
    "~\\AppData\\Local\\Temp/ipykernel_27784/2341063223.py in <module>\n",
    "----> 1 for num in nums:\n",
    "      2     print(num)\n",
    "\n",
    "TypeError: 'Range' object is not iterable\n",
    "```\n",
    "\n",
    "이제 위의 클래스에 `__iter__()`를 추가함으로 iterable한 객체를 생성하도록 합니다. 그러므로 for loop에서도 사용할 수 있고, 파이썬 내장함수 `sum()`을 활용할 수 있습니다. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Sample Run__\n",
    "```\n",
    "    nums = Range(1, 6)\n",
    "    print(next(nums))               # iterator works here\n",
    "    print(next(nums))\n",
    "    print(next(nums))\n",
    "    \n",
    "    for num in nums:                # iterable works here \n",
    "        print(num, end=' ')\n",
    "    print()\n",
    "    \n",
    "    nums = Range(1, 6)\n",
    "    print('sum =', sum(nums))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Expected Output__\n",
    "```\n",
    "1\n",
    "2\n",
    "3\n",
    "4 5 \n",
    "sum = 15\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4 5 \n",
      "sum = 15\n"
     ]
    }
   ],
   "source": [
    "class Range:\n",
    "    def __init__(self, start, end):\n",
    "        self.value = start\n",
    "        self.end = end\n",
    "    \n",
    "    def __next__(self):              # this makes iterator object        \n",
    "        if self.value >= self.end:  \n",
    "            raise StopIteration\n",
    "        current = self.value\n",
    "        self.value += 1\n",
    "        return current\n",
    "    \n",
    "    def __iter__(self):              # this makes iterable object\n",
    "        return self\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = Range(1, 6)\n",
    "    print(next(nums))               # iterator works here\n",
    "    print(next(nums))\n",
    "    print(next(nums))\n",
    "    \n",
    "    for num in nums:                # iterable works here \n",
    "        print(num, end=' ')\n",
    "    print()\n",
    "    \n",
    "    nums = Range(1, 6)\n",
    "    print('sum =', sum(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generator \n",
    "\n",
    "Generator는 여러 개의 데이터를 미리 만들어 놓지 않고 필요할 때마다 즉석해서 하나씩 만들어낼 수 있는 객체를 의미합니다. \n",
    "- 그래서, 이를 구현할 때는, 즉시 결괏값을 반환하는`return` 대신에 필요할 때마다(함수를 호출을 받을 때마다) 반환할 수 있는 `yield`라는 키워드를 사용합니다. \n",
    "- yield는 양보하다라는 뜻도 있습니다. yield를 사용하면 결괏값을 함수 바깥(caller)으로 전달하면서 코드 실행을 함수 바깥에 양보합니다. 따라서 yield는 현재 함수를 잠시 중단하고 함수 바깥의 코드가 실행되도록 만듭니다. 그리고, 바깥(caller)에서 실행이 끝나고 다시 들어오면, 그 자리에서 다시 실행을 계속 진행합니다. \n",
    "- Generator **함수**는 `__iter__()`와 `__next__()`를 자동적으로 만들어 주는 역할을 합니다. \n",
    "- 그러므로, Generator **함수**는 `__iter__()`와 `__next__()` 메소드를 정의하지 않고도 그러한 모든 기능할 수 있습니다. \n",
    "- Generator는 함수인 것에 유의하십시오. \n",
    "- Generator는 메모리의 효율적인 사용과 실행 속도 면에서 상당히 나은 경우들이 있습니다.\n",
    "\n",
    "다음 `grange()`함수는 위에서 만든 `Range` 클래스와 같은 작업을 하지만, 훨씬 더 간단한 코드로 가능합니다"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generator range\n",
    "def grange(start, end):\n",
    "    pass\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "        \n",
    "    nums = grange(5, 10)\n",
    "    print(next(nums))           # iterator works here\n",
    "    print(next(nums))\n",
    "    print(next(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generator를 활용하면, 끝나는 조건을 체크않도록 하여, 다음과 같이 끝나지 않고 계속 숫자를 발생할 수 있게 만들수 있습니다. 아래 코드에서 테스트 할 때는 무한 루프를 방지하기 위해 임의로 100까지만 진행합니다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generator\n",
    "def igrange(start):             # no end parameter - infinite generator\n",
    "    pass\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    nums = igrange(1)\n",
    "    print(nums)\n",
    "    for num in nums:\n",
    "        print(num, end = ' ')\n",
    "        if num == 100:\n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise: \n",
    "\n",
    "## Iterable and iterator 만들기\n",
    "아래와 같이 주어진 코드가 작동될 수 있도록 클래스 `Words`를 정의하십시오. 이 문제는 입력으로 주어진 여러 단어로 구성된 문장을 한 단어씩 분리하여 출력하는 클래스를 만들 때 필요한 iterator와 iterable을 만드는 것입니다. \n",
    "\n",
    "__힌트__   \n",
    "- 입력은 여러 단어로 구성된 문장을 단어별로 분리할 때는 string 메소드인 split()함수를 사용합니다. \n",
    "- 클래스의 속성으로 `words`를 추가하고, split()으로 분리한 단어 리스트를 저장합니다. \n",
    "- 클래스의 속성으로 `index`를 추가하고, 단어 리스트를 반복하여 꺼낼 때 사용합니다.  \n",
    "\n",
    "__Sample Run:__\n",
    "```\n",
    "if __name__ == '__main__':\n",
    "    words = Words('God is good all the time')\n",
    "    for word in words:                      # iterable works here\n",
    "        print(word, end = ' ')\n",
    "    print()\n",
    "    \n",
    "    words = Words('Know God, Make Him Known')\n",
    "    print(next(words))                      # iterator works here\n",
    "    print(next(words))\n",
    "    print(next(words))\n",
    "```\n",
    "    \n",
    "__Expected Output:__\n",
    "```\n",
    "<__main__.Words object at 0x000002B54A484E80>\n",
    "God \n",
    "is \n",
    "good \n",
    "all\n",
    "the \n",
    "time \n",
    "Know\n",
    "God,\n",
    "Make\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Words:\n",
    "    def __init__(self, sentence):\n",
    "        pass\n",
    "    \n",
    "    def __iter__(self):                     # to be iterable\n",
    "        pass\n",
    "    \n",
    "    def __next__(self):                     # to become an iterator\n",
    "        pass\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    words = Words('God is good all the time')\n",
    "    print(words)\n",
    "    \n",
    "    for word in words:                      # iterable works here\n",
    "        print(word, end = ' ')\n",
    "    print()\n",
    "    \n",
    "    words = Words('Know God, Make Him Known')\n",
    "    print(next(words))                      # iterator works here\n",
    "    print(next(words))\n",
    "    print(next(words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generator 만들기\n",
    "\n",
    "아래와 같이 주어진 코드가 작동될 수 있도록 클래스 `Words`를 정의하십시오. 이 문제는 입력으로 주어진 여러 단어로 구성된 문장을 한 단어씩 분리하여 출력하는 클래스를 만들 때 필요한 iterator와 iterable을 만드는 것입니다. \n",
    "\n",
    "__힌트__   \n",
    "- 입력은 여러 단어로 구성된 문장을 단어별로 분리할 때는 string 메소드인 split()함수를 사용합니다. \n",
    "- 클래스의 속성으로 `words`를 추가하고, split()으로 분리한 단어 리스트를 저장합니다. \n",
    "- 클래스의 속성으로 `index`를 추가하고, 단어 리스트를 반복하여 꺼낼 때 사용합니다.  \n",
    " \n",
    "__Sample Run:__\n",
    "```\n",
    "if __name__ == '__main__':\n",
    "    words = Words('God is good all the time')\n",
    "    for word in words:                      # iterable works here\n",
    "        print(word)\n",
    "    \n",
    "    words = Words('Know God, Make Him Known')\n",
    "    print(next(words))                      # iterator works here\n",
    "    print(next(words))\n",
    "    print(next(words))\n",
    "``` "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Expected Output:__\n",
    "```\n",
    "<generator object words at 0x000002B54A481270>\n",
    "God \n",
    "is \n",
    "good \n",
    "all\n",
    "the \n",
    "time \n",
    "Know\n",
    "God,\n",
    "Make\n",
    "Him\n",
    "Known\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def words(sentence):\n",
    "    pass\n",
    "        \n",
    "if __name__ == '__main__':\n",
    "    mywords = words('God is good all the time')\n",
    "    print(mywords)\n",
    "    \n",
    "    for word in mywords:    # iterable works here\n",
    "        print(word)\n",
    "        \n",
    "    mywords = words('Know God, Make Him Known')\n",
    "    print(next(mywords))    # iterator works here\n",
    "    print(next(mywords))\n",
    "    print(next(mywords))\n",
    "    print(next(mywords))\n",
    "    print(next(mywords))\n",
    "    # print(next(mywords))  # works like iterator, produces StopIterator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ListSorted의 `__iter__()`와 `__next__()` 구현하기 \n",
    "\n",
    "우리가 앞에서 만든 ListSorted 클래스에 `__iter__()` 메소드와 `__next__()`를 구현함으로 ListSorted 클래스의 객체가 iterable하고, 또한 iterator로 사용할 수 있도록 합니다. \n",
    "\n",
    "__힌트__\n",
    "- Iteration의 시작은 ListSorted의 head에서 하고, Iteration의 끝은 None이 나오면 끝으로 합니다. \n",
    "- Iteration을 할 때, 현재의 Node의 위치를 기억(저장)하기 위해 `current` 속성(멤버)을 `__iter__()`메소드 에서 도입하고, `self.head`로 초기화합니다. (`current`속성을 `__init__()`에 정의할수도 있지만, 이 속성은 `__next__`에서 사용할 것임으로 `__iter__()`에서 정의하는 것이 더 바람직할 것입니다.)\n",
    "\n",
    "__Sample Run:__\n",
    "```\n",
    "if __name__ == \"__main__\":\n",
    "    mylist = ListSorted()\n",
    "    mylist.push(31)\n",
    "    mylist.push(77)\n",
    "    mylist.push(17)\n",
    "    mylist.push(93)\n",
    "\n",
    "    print(mylist.size())      # 6\n",
    "    print(mylist.search(93))  # True\n",
    "    print(mylist.search(100)) # False\n",
    "    \n",
    "    for item in mylist:\n",
    "        print(item, end = ' ')\n",
    "    print()\n",
    "        \n",
    "    print('sum =', sum(mylist))\n",
    "    \n",
    "    it = iter(mylist)\n",
    "    print(next(it))\n",
    "    print(next(it))\n",
    "```\n",
    "\n",
    "__Expected Output:__\n",
    "```\n",
    "4\n",
    "True\n",
    "False\n",
    "17 31 77 93 \n",
    "sum = 218\n",
    "17\n",
    "31\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self._data = data\n",
    "        self._next = None\n",
    "\n",
    "    def get_data(self):\n",
    "        return self._data\n",
    "    \n",
    "    def set_data(self, data):\n",
    "        self._data = data\n",
    "\n",
    "    def get_next(self):\n",
    "        return self._next\n",
    "\n",
    "    def set_next(self, next):\n",
    "        self._next = next\n",
    "\n",
    "\n",
    "class ListSorted:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.get_data() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.get_data() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.get_next()\n",
    "\n",
    "        return found\n",
    "\n",
    "    def push(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.get_data() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.get_next()\n",
    "\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.set_next(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.set_next(current)\n",
    "            previous.set_next(temp)\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.get_next()\n",
    "        return count\n",
    "    \n",
    "    def __iter__(self):               # to be iterable\n",
    "        pass\n",
    "    \n",
    "    def __next__(self):               # to become an iterator\n",
    "        pass\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    mylist = ListSorted()\n",
    "    mylist.push(31)\n",
    "    mylist.push(77)\n",
    "    mylist.push(17)\n",
    "    mylist.push(93)\n",
    "\n",
    "    print(mylist.size())      # 6\n",
    "    print(mylist.search(93))  # True\n",
    "    print(mylist.search(100)) # False\n",
    "    \n",
    "    for item in mylist:\n",
    "        print(item, end = ' ')\n",
    "    print()\n",
    "        \n",
    "    print('sum =', sum(mylist))\n",
    "    \n",
    "    it = iter(mylist)\n",
    "    print(next(it))\n",
    "    print(next(it))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이번 시간은 링크드 리스트를 통해 정렬이 없는 링크드 리스트와 정렬된 링크드 리스트 추상자료형에 대해 배웠습니다. 링크드 리스트는 데이터 영역과 링크 영역을 나누어 정보를 저장하는 노드의 연결로 이루어지며, 이를 통해 다양한 형태로 저장 및 연산을 할 수 있습니다. 오늘 배운 내용을 혼자 프로그래밍하여 익히면 좋겠습니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "- Linked Lists, [Here](https://runestone.academy/ns/books/published//pythonds3/BasicDS/Lists.html)\n",
    "- The Ordered List Abstract Data Type¶, [Here](https://runestone.academy/ns/books/published//pythonds3/BasicDS/TheOrderedListAbstractDataType.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------\n",
    "먼저 알 것은 성경의 모든 예언은 사사로이 풀 것이 아니니 예언은 언제든지 사람의 뜻으로 낸 것이 아니요 오직 성령의 감동하심을 받은 사람들이 하나님께 받아 말한 것임이라 (벧후1:20-21)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  },
  "toc-autonumbering": true,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}