1. Array와 LinkedList
(1) Array 특징
- 크기가 정해진 데이터의 공간. 한 번 정해지면 바꿀 수 없음
- 각 원소에 즉시 접근 가능. 원소 순서는
0부터 시작하며 이를index라고 함 - 원소를
중간에 삽입/삭제하려면모든 원소를 다 옮겨야 함 - 최악의 경우 배열의 길이 N 만큼 옮겨야 하므로 O(N)의 시간 복잡도를 가짐
- 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비 효율적인 자료구조
(2) LinkedList 특징
- 리스트는 크기가 정해지지 않은 데이터의 공간
- 연결 고리(포인터)로 이어주기만 하면, 자유자재로 늘어날 수 있음
- 리스트는 특정 원소에 접근하려면 연결 고리(포인터)를 따라 탐색해야 함
- 최악의 경우에는 모든 화물 칸(노드)을 탐색해야 하므로 O(N)의 시간 복잡도를 가짐
- 리스트는 원소를
중간에 삽입/삭제하기 위해서 앞 뒤의 연결 고리(포인터)만 변경하면 됨 - 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있음
(3) 비교
| 경우 | Array | LinkedList |
|---|---|---|
| 특정 원소 조회 | O(1) | O(N) |
| 중간에 삽입 삭제 | O(N) | O(1) |
| 데이터 추가 | 데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 함 | 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다. |
| 정리 | 데이터에 접근하는 경우가 빈번하다면 Array를 사용하자 | 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다. |
(4) Python의 배열[]은 List인가 Array인가
- Python의 List는 Array로 구현되어 있다.
- 동적 배열을 사용해서, 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계
- Python의 배열은 LinkedList로 사용 가능하고, Array로도 사용 가능한 효율적인 자료구조
2. 클래스 (Class)
- 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념
{객체 : 세상에 존재하는 유일무이한 사물} - 클래스를 이용하면 연관성 있는 데이터들을 클래스 내에서 관리할 수 있으며, 다양한 객체 쉽게 생성
class 변수1:
내용
변수2 = 변수1()
(1) 생성자 ( Constructor)
- 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있음
- 파이썬의 생성자 함수 이름 :
__init__으로 고정 - 생성자는 생성시에 호출되는 함수
self는 객체 자기 자신을 가리킴. 따라서 파라미터를 따로 넣을 필요 없이 그냥 호출 하면 됨
class Person:
def __init__(self):
print("hello", self)
person_1 = Person() # hello <__main__.Person object at 0x7fa868038760>self를 사용하면 객체에 데이터를 쌓을 수 있음self.name에param_name을 저장하겠다는 건, 그 객체의name이라는 변수에 저장된다는 의미
class Person:
def __init__(self, param_name):
print("hello", self)
self.name = param_name
person_1 = Person("solrasido") # hello <__main__.Person object at 0x7fe600190760>
print(person_1.name) # solrasidoPerson이라는 클래스에 함수 추가- 클래스 내부의 함수는
메소드(Method)라고 한다.
class Person:
def __init__(self, param_name):
print("hello", self)
self.name = param_name
# talk라는 함수 추가 (클래스 내부에 있는 함수이므로 '메소드'라고 한다.)
def talk(self):
print('안녕하세요, 저는', self.name, "입니다.")
person_1 = Person("solrasido") # hello <__main__.Person object at 0x7fe600190760>
print(person_1.name) # solrasido
person_1.talk() # 안녕하세요, 저는 solrasido 입니다.3.LinkedList 구현 (1)
(1) 링크드 리스트 'append' 함수 만들기
- 링크드 리스트 모양
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]- 노드(화물칸)에 필요한 정보
- 칸에 있는 데이터
- 다음 칸이 무엇인지
- 두 가지 데이터를 가지고 있어야 하니
클래스를 이용함- 우선 클래스의 생성자에
data를 인자로 받아서self.data에 저장 - 현재 다음 이어진 노드가 없기 때문에
self.next에는None을 저장
- 우선 클래스의 생성자에
class Node:
def __init__(self, data): # 클래스 생성 생성자에 data를 넣음
self.data = data # data를 self.data에 저장
self.next = None # 다음 노드가 없기 때문에 self.next에 None을 저장
node = Node(3) # 현재는 next가 없어 하나의 노드만 존재
print(node) # <__main__.Node object at 0x7fde90190760>
print(node.data) # 3- 노드 생성 및 연결
class Node:
def __init__(self, data): # 클래스 생성 생성자에 data를 넣음
self.data = data # data를 self.data에 저장
self.next = None # 다음 노드가 없기 때문에 self.next에 None을 저장
first_node = Node(5) # 현재 next 가 없이 하나의 노드만 있음 [5]
second_node = Node(12) # [12]를 들고 있는 노드 생성
first_node.next = second_node # [5]의 next를 [12]로 지정 [5] -> [12]
print(first_node.data) # 5
print(second_node.data) # 12
print(first_node.next.data) # 12- LinkedList 클래스 만들기
- LinkedList는
head node만 들고 있음 - 기차 처럼
맨 앞 칸만 저장해둠 - 다음 칸을 보기 위해서는
next를 통해 다음 노드 접근
- LinkedList는
- 정리
- LinkedList는
self.head에 시작하는 노드 저장 - 다음 노드를 보기 위해서는 각 노드의
next를 조회해서 찾아가야 함
- LinkedList는
class Node:
def __init__(self, data): # 클래스 생성 생성자에 data를 넣음
self.data = data # data를 self.data에 저장
self.next = None # 다음 노드가 없기 때문에 self.next에 None을 저장
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head에 클래스 Node 연결
linked_list = LinkedList(5) # 현재 링크드 리스트에는 5만 존재
print(linked_list.head.data) # 5가 출력된다- LinkedList의 맨 뒤에 새로운 노드를 붙이는
append함수 만들기- 현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하기 위해서는
가장 맨 뒤의 노드까지가야함
- 현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하기 위해서는
- 맨 뒤의 노드까지 가는 방법
cur
head
[3] -> [5] -> [6] -> [8]
# head를 따라서 이동
# head는 변경이 불가하여, 'cur'이라는 변수 이용
{cur = this.head}
cur
[3] -> [5] -> [6] -> [8]
{cur = cur.next}
cur
[3] -> [5] -> [6] -> [8]
{cur = cur.next}
cur
[3] -> [5] -> [6] -> [8]
# 맨 뒤의 노드까지 라는 것은 cur.next가 None이라는 것
# 맨 마지막 노드는 다음 노드가 없어 아무것도 가리키지 않음(2) 링크드 리스트 모든 원소 출력
class Node:
def __init__(self, data): # 클래스 생성 생성자에 data를 넣음
self.data = data # data를 self.data에 저장
self.next = None # 다음 노드가 없기 때문에 self.next에 None을 저장
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head에 클래스 Node 연결
def append(self, value): # LinkedList 가장 끝에 있는 노드에 새로운 노드 연결
cur = self.head
while cur.next is not None: # cur의 다음이 끝에 갈 때 까지 이동
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head # head에 저장되어있는 노드를 cur 이라는 변수에 담고
while cur is not None: # cur의 다음이 끝에 갈 때 까지 출력. (None이 아닐 때까지)
print(cur.data)
cur = cur.next
linked_list = LinkedList(5) # 5
linked_list.append(12) # 5 -> 12
linked_list.append(8) # 5 -> 12 -> 8
linked_list.print_all()3.LinkedList 구현 (2)
(1) 링크드 리스트 원소 찾기 / 원소 추가
- 링크드 리스트에서 index번째 원소를 반환하시오
class Node:
def __init__(self, data): # 클래스 생성 생성자에 data를 넣음
self.data = data # data를 self.data에 저장
self.next = None # 다음 노드가 없기 때문에 self.next에 None을 저장
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head에 클래스 Node 연결
def append(self, value): # LinkedList 가장 끝에 있는 노드에 새로운 노드 연결
cur = self.head
while cur.next is not None: # cur의 다음이 끝에 갈 때 까지 이동
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head # head에 저장되어있는 노드를 cur 이라는 변수에 담고
while cur is not None: # cur의 다음이 끝에 갈 때 까지 출력. (None이 아닐 때까지)
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head # head에 저장되어 있는 노드를 node라는 변숭레 담고
count = 0 # count라는 인덱스를 저장하기 위한 변수를 저장 초기값 0
while count < index: # count가 index가 될 때까지 (이 때 while 문 내부에서 1씩 더해주니까 작을떄까지로 조건을 넣는다)
node = node.next # node의 next 값을 node에 대입하고
count += 1 # count를 증가 (count가 index가 아닐 때까지 반복)
return node # node 반환
linked_list = LinkedList(5) # 5
linked_list.append(12) # 5 -> 12
linked_list.append(8) # 5 -> 12 -> 8
linked_list.print_all()
print(linked_list.get_node(0).data) # 인덱스 0 의 원소 5 출력
항상 처음 세웠던 목표 처럼