<배운 내용>
- 클래스란?
- 클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념
- 객체란 세상에 존재하는 유일무이한 사물
| 클래스 |
객체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
- 헤드 노드부터 시작해서 링크드리스트에 있는 노드들을 차례대로 출력해주는 함수
