자료구조/알고리즘 2주차 (1강~6강)

마이구미+ 2023. 4. 19. 18:41

<배운 내용>

- 클래스란?

클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념
객체란 세상에 존재하는 유일무이한 사물

예시

클래스	객체1	객체2
꽃	개나리	벚꽃
자동차	싼타페	모닝

같은 속성과 기능을 가진 객체들을 묶는 게 클래스

코드 예시

class Person:
    def __init__(self, param_name): # 객체가 생성되면 실행되는 함수
        print("i am created!", self)
        self.name = param_name

    def talk(self):
        print("안녕하세요, 제 이름은", self.name, "입니다")

person_1 = Person("유재석")
print(person_1.name)
print(person_1)
person_1.talk()

person_2 = Person("박명수")
print(person_2.name)
print(person_2)
person_2.talk()

# 출력화면
# i am created! <__main__.Person object at 0x0000013A66B78150>
# -> person_1 = Person("유재석")로 객체 생성 후 __init__ 함수 실행
# 유재석 -> pirnt(person_1.name) 실행
# <__main__.Person object at 0x0000013A66B78150> -> print(person_1) 실행
# 안녕하세요, 제 이름은 유재석 입니다 -> person_1.talk() 실행

# i am created! <__main__.Person object at 0x0000013A66B78310>
# -> person_2 = Person("박명수")로 객체 생성 후 __init__ 함수 실행
# 박명수 -> pirnt(person_2.name) 실행
# <__main__.Person object at 0x0000013A66B78310> print(person_2) 실행
# 안녕하세요, 제 이름은 박명수 입니다 -> person_2.talk() 실행

- Array vs LinkedList

LinkedList는 그냥 List로 불리기도 함
차이점

경우	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입/삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 함	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 됨
정리	데이터에 접근하는 경우가 빈번하다면 Array를 이용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다

파이썬의 list는 array로 구현되어 있음
그렇지만 파이썬의 배열은 LinkedList로 쓸 수도 있고 array로도 쓸 수 있게 만든 효율적인 자료구조라고 함

<코드 분석하기>

- Node 클래스

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

node 라는 변수에 Node(3)을 선언하면 node라는 하나의 노드가 생성됨
노드의 데이터값에는 3이 들어가고, 이 노드가 가리키는 값은 없음
링크드리스트의 마지막 노드는 가리키는 값이 없기 때문

- LinkedList 클래스

전체 코드에서는 LinkedList 클래스 안에 __init__, append, print_all, get_node, add_node, delete_node 함수가 쭈르륵 붙어있지만 편의상 함수 하나씩 첨부함

init 함수

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

linked_list 라는 변수에 LinkedList(3)을 선언하면 linked_list라는 하나의 링크드리스트가 생성됨
이 클래스는 생성될 때 노드 1개를 생성하고 해당 노드를 링크드리스트의 헤드로 지정함
현재 linked_list는 [3] -> None (노드가 1개인 링크드리스트임)

append 함수

class LinkedList:
    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

링크드리스트 마지막에 노드를 추가하는 함수
linked_list.append(5)를 하면 먼저 cur 이라는 변수에 해당 링크드리스트의 헤드 노드를 넣음
헤드 노드부터 시작해서 노드의 포인터가 None이 될 때까지 cur 변수값을 다음 노드로 쭉쭉 변경시킴
노드의 포인터가 None 이라는 것은 링크드리스트의 마지막 노드라는 뜻
마지막 노드의 next(포인터) 값에 추가할 노드 [5]를 넣음
현재 linke_list에는 [3] 뿐이니 while문을 바로 빠져나와 [3]의 next값이 [5]가 됨
현재 linked_list는 [3] -> [5]

get_node 함수

class LinkedList:
    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

몇 번째 인덱스에 어떤 노드가 있는지 찾는 함수
node 라는 변수에 링크드리스트의 첫 번째 값인 헤드 노드를 넣어줌
count는 0부터 시작
count가 index와 같아질 때까지 while문이 돌아감
while문이 한 번 돌 때마다 node 라는 변수는 다음 값을 계속 넣어주고, count도 1씩 증가함
인덱스가 1인 노드를 찾는 경우 while문이 한 번 돌아가서 node 라는 변수에는 헤드 노드의 다음 노드가 담김
현재 linked_list에서 1번째 인덱스에 어떤 노드가 있는지 알고 싶을 때 linked_list.get_node(1) 로 찾으면 됨
print(linked_list.get_node(1))로 하면 노드의 주소가 나오고 해당 노드에 어떤 데이터가 있는지 알고 싶으면 print(linked_list.get_node(1).data) 하면 됨
현재 linked_list는 [3] -> [5]
print(linked_list.get_node(1).data) 하면 5가 출력됨
인덱스가 0인 노드를 찾는 경우 while문이 돌지 않고 헤드 노드가 node에 담겨서 반환됨

add_node 함수

class LinkedList:
    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

링크드리스트에 특정 인덱스에 노드를 추가하는 함수
new_node 라는 변수에 원하는 데이터 값을 담은 노드를 생성함
index가 0인 경우는 헤드 노드를 교체하고 싶다는 말
새로운 노드의 포인터를 현재 헤드 노드로 지정한 후에 현재 헤드 노드를 새로운 노드로 바꾸면 됨
index가 0이 아닌 경우는 헤드 노드가 아닌 중간 또는 마지막 자리에 새로운 노드를 넣겠다는 뜻
node 라는 변수에 원하는 자리의 이전 자리에 있는 노드를 담아줌
next_node 라는 변수에 이전 노드가 원래 다음에 가리키고 있던 노드를 담아줌(임시 저장)
node의 포인터(node.next)가 새로운 노드(new_node)를 가리키게 함
새로운 노드의 포인터(new_node.next)는 아까 담아둔 원래 다음 노드였던 그 노드(next_node)를 담아줌
linked_list.add_node(1, 6) 하면 인덱스 1에 6이 들어가고 원래 인덱스 1 자리에 있던 5는 6 다음으로 바뀜
현재 linked_list는 [3] -> [6] -> [5]

delete_node 함수

class LinkedList:
    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return

        node = self.get_node(index - 1)
        node.next = node.next.next

링크드리스트의 특정 인덱스에 있는 노드를 삭제하는 함수
헤드 노드를 삭제하는 경우 인덱스는 0, 현재 헤드 노트가 가리키는 다음 값을 헤드로 변경함
그 외 인덱스의 노드를 삭제하는 경우, node 라는 변수에 해당 인덱스가 위치한 노드의 직전 노드를 담음
그 직전 노드의 포인터(node.next)를 다음 노드가 가리키는 값으로 변경해줌(node.next.next)
node.next.next의 값은 삭제하고자 하는 인덱스 자리에 있는 노드 바로 다음 노드임
linked_list.delete_node(1) 을 한다면 인덱스 0 자리에 있는 [3]의 포인터가 [6]에서 [5]로 변경됨
현재 linked_list는 [3] -> [5]

print_all 함수

class LinkedList:
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

헤드 노드부터 시작해서 링크드리스트에 있는 노드들을 차례대로 출력해주는 함수

저작자표시 (새창열림)