Basic Data Structures

# Pythonic way to define getter/setter/deleter - @property를 쓰세요!

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

        # Note in the constructor that a node is initially created with next set to None. Since this is sometimes referred to as “grounding the node,” we will use the standard ground symbol to denote a reference that is referring to None. It is always a good idea to explicitly assign None to your initial next reference values.

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

class PythonicNode:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None

    @property
    def x(self):
        return self.data

    @x.setter
    def x(self, newdata):
        self.data = newdata

    @x.deleter
    def x(self):
        del self.data

temp = PythonicNode(93)

# getter
temp.x # 93

# setter
temp.x = 1234
temp.x # 1234

# deleter
del temp.x

class UnorderedList:
    def __init__(self):
        self.head = None

    # 이 클래스는 첫 노드에 대한 레퍼런스를 반드시 가져야 한다. (... class must maintain a reference to the first node.)
    # 그런데 이 생성자에 head가 none 인 이유는 막 생성된 리스트는 아무 노드도 없기 때문!

    def isEmpty(self):
        return self.head == None
    # 이 리스트가 있는지 없는지 보려면 head가 있는지 없는지만 보면 됨. 그래서 boolean식으로 알아봄

    def add(self, item):
        temp = Node(item)    # temp는 노드 클래스의 인스턴스여야 하고,
        temp.setNext(self.head)    # 새로운 temp가 들어오면, 원래 있던 head(None)는 temp의 next가 되고,
        self.head = temp    # temp는 새로운 head가 된다! - modify the head of the list to refer to the new node

    # 3,4번째 라인의 순서가 중요하다!
    # x.next == None 이면, x 는 이 리스트의 첫 데이터

    def size(self):
        current = self.head
        count = 0
        while current != None:    # head 가 None이 나올때까지, 끝까지 돈다.
            count = count + 1     # while loop가 도는 횟수를 센다.
            current = current.getNext()

        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()

        return found

    # head부터 차근차근 찾아나간다. 일치하지 않으면 found가 False를, 일치하면 True를 뱉어냄.

    def print_all(self):
        current = self.head
        while current != None:
            print(current.getData())
            current = current.getNext()

    def remove(self, item):    # 제거하고 싶은 노드의 앞,뒤 링크를 끊어주면 된다.
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

        # 순서는 바꿨는데, node 인스턴스는 그대로 남아있잖아? (size는 그대로 아닌가?)


    # 함께 풀어봅시다!!
    def append(self, item):    # item이 last가 되려면? 처음 들어온 아이템까지 가서 그 next에 item을 붙인다.
        temp = Node(item)
        current = self.head

        while current.getNext() != None:
            current = current.getNext()
        current.setNext(temp)

mylist = UnorderedList()
print(mylist.head)
# None

mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)
print(mylist.head)

# <__main__.Node object at 0x1045acf28>

mylist.size()
# 6

mylist.print_all()
# 54
# 26
# 93
# 17
# 77
# 31

mylist.search(17)
# True

mylist.remove(17)
mylist.print_all()
# 54
# 26
# 93
# 77
# 31

mylist.append(14923)
mylist.print_all()
# 54
# 26
# 93
# 77
# 31
# 14923

- add(item)
- remove(item)
- search(item)
- isEmpty()
- size()
- append(item)
- index(item)
- insert(pos,item)
- pop()
- pop(pos)

class OrderedList:
    def __init__(self):
        self.head = None

    def search(self, item):    # 크기의 순서가 있기 때문에 끝까지 돌지 않아도 된다.
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:    # 찾는 데이터보다 큰곳까지 왔는데도 없다면, 여긴 없다는 뜻. iteration을 stop 해도 된다.
                    stop = True
                else:
                    current = current.getNext()

        return found

    def add(self,item):   # unordered랑 다르게, 아무데나 들어가선 안되고, 크기에 맞게 들어가야한다.
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)    # 인스턴스 생성해주고,
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)    # item 보다 큰 current 는 item 뒤에 넣어주고
            previous.setNext(temp)    # item보다 작은 previous의 next 에 item을 넣어준다.

    def print_all(self):
        current = self.head
        while current != None:
            print(current.getData())
            current = current.getNext()

mylist = OrderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)

mylist.print_all()
# 17
# 26
# 31
# 54
# 77
# 93