뒤돌아보기

• Linked List를 이용해서 stack 구현

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

string "Node"로 type hint를 사용한 이유는? https://wschoi.tistory.com/36 참고

class Stack:
    def __init__(self):
        self.last = None

stack = Stack()

• self.last 속성을 이용해 stack의 push, pop () 메소드 구현

Push 메소드

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data) # here
        new_node.next = self.last
        self.last = new_node

stack = Stack()
stack.push(1)

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last # here
        self.last = new_node

stack = Stack()
stack.push(1)

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node # here

stack = Stack()
stack.push(1)

• last 포인터가 새로운 node를 가리킴

push() 메소드를 한번 더 호출하면?

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data) # here
        new_node.next = self.last
        self.last = new_node

stack = Stack()
stack.push(1)
stack.push(2) # push 한번 더 호출

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last # here
        self.last = new_node

stack = Stack()
stack.push(1)
stack.push(2)

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node # here

stack = Stack()
stack.push(1)
stack.push(2)

• last 포인터를 새로 추가된 노드를 가리키도록 업데이트

Pop 메소드

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node

    def pop(self):
        data = self.last.data # here
        self.last = self.last.next
        return data

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # here

class Stack:
    def __init__(self):
        self.last = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node

    def pop(self):
        data = self.last.data
        self.last = self.last.next # here
        return data

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 2

• last 포인터를 업데이트
• 마지막으로 data를 반환

본 글에서는 이전 Linked List 글에서 언급한 Node를 구현. 

최대한 간단히 Node 클래스만을 이용해서 어떻게 node들이 연결될 수 있는지에 대해 설명.

Node 클래스 정의

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

다음의 2가지 인스턴스 속성을 가짐

(1) 값을 저장하는 data

(2) 다음 Node를 가리키는 next

여러 개의 노드를 생성 후 서로 연결

1. 3개의 Node 인스턴스 생성

first  = Node(1)
second = Node(2)
third  = Node(3)

2. first 노드의 next에 second 노드 인스턴스 할당

first.next = second

first.next 에 second 를 할당하면 진짜 first 노드가 second 노드와 연결된게 맞는지 확인하는 방법

print(type(first.next))  # <class '__main__.Node>

# first노드의 next를 통해서 second 노드의 값에 접근 가능
print(first.next.data)  # 2

first 노드의 next를 통해 second 노드의 data에 접근 가능

3. second 노드의 next에 third 노드 할당

second.next = third

본 글에서는 Node들의 연결을 통해 한 노드에서 다른 노드에 접근가능함을 보여주는 내용이었음. 

배열 대비 Linked List의 장점은 1) dynamic size 2) 삽입/삭제가 쉬움 인데 위의 내용을 통해 node를 계속 추가함으로써 dynamic size의 장점은 보여주었고 다음 글에서 삽입/삭제에 대한 내용을 다룸.

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조.

리스트라는 자료구조는 구현 방법에 따라 크게 2가지로 나뉨

1. 순차 리스트 (Array list) : 배열을 기반으로 구현된 리스트
2. 연결 리스트 (Linked list) : 메모리의 동적 할당을 기반으로 구현된 리스트

본 글에서는 연결 리스트에 대해 다룸.

미리 정해진 크기(위 그림에서는 노란색 9칸) 에 순차적으로 저장되는 Array List와 달리,
Linked List는 미리 공간의 크기가 정해져있지 않고, 물리적으로 떨어져 있음.

그렇기 떄문에 서로를 연결할 수 있는 방법이 필요.

위 그림에서 노란색 점 하나하나가 아래 그림 linked list 의 Node와 대응됨. Node는 linked list에서 각각의 원소를 의미.

그럼 아래 그림에서 Node1과 Node2는 어떻게 연결할까?

각각의 Node는 data와 next 라는 속성을 가짐.

data에는 값이 저장되고, next는 다음에 가리키는 Node에 대한 정보가 들어가 있음. 이를 참조하면 다음 Node에 접근 가능.

특별히 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 함.