Array & Linked List
▶️ Array (배열)
캡슐호텔이라고 생각하면 편하다. 초기화를 하고 나면 정형화된 공간이 되어서 삽입/삭제가 어려우나 원소 하나하나를 찾아갈 수 있는게 즉각적인 것이 특징.
우리가 앞서 배웠던 input = [1,2,3,4,5] 이 것이 배열이다. 배열은 한 번 초기화 되고 나면 삽입/삭제가 어렵다.
맨 끝의 5를 2번 자리에 위치하게끔 하려면 5와 4 / 5와 3 / 5와 2 이렇게 여러 번 변수를 옮겨야 한다.
input = [1,2,3,5,4]
input = [1,2,5,3,4]
input = [1,5,2,3,4]
만약 6을 삽입하고 싶다면 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조이다. 최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가진다.
▶️ Linked List (링크드 리스트)
기차라고 생각하면 편하다. 칸마다 연결 고리로 연결 되어있고, 이 연결 고리를 이용하여 중간에 다른 칸을 삽입하거나 삭제하기 용이한 것이 특징.
리스트는 크기가 정해지지 않은 데이터의 공간으로 연결 고리로 이어 주기만 하면, 자유자재로 늘어날 수 있다. 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 하며, 최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 부른다. 그리고 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.
| Array | LinkedList | |
| 특정 원소 조회 | O(1) | O(N) |
| 중간에 삽입/삭제 | O(N) | O(1) |
| 데이터 추가 | 데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다 | 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다 |
| 장점 | 정리 데이터에 접근하는 경우가 빈번할 때 이용 | 삽입과 삭제가 빈번할 때 이용 |
🚨한 걸음 더!
Python의 list 는 array로 구현되어 있기 때문에 append 메서드를 이용하여 편하게 데이터를 추가할 수 있게 되어있다. 이때 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어 있다. 따라서 Python의 Array 링크드 리스트와 배열 두가지의 장점을 다 가지고 있는 효율적인 자료 구조라고 생각하면 된다.
Class
분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념
▶️ 여기서 객체란?
세상에 존재하는 유일무이한 사물
class Person:
pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미입니다!
person_1 = Person() #()는 생성자
print(person_1) # <__main__.Person object at 0x000001FC66B586D0>
person_2 = Person()
print(person_2) # <__main__.Person object at 0x000001FC66B58190>이렇게 클래스를 만들고, 생성자로 불러올 수 있다.
class Person:
def __init__(self):
print("i am created!", self)
# constructor를 생성하거나, 내부 함수를 이용할 때 self를 이용해 자기 자신을 인자로 넘겨준다.
# 생성자 함수의 이름은 __init__ 으로 고정되어 있다, 즉 def __init__(self)가 클래스를 생성한다는 의미니까
# 클래스가 생성될 때 print문이 실행되게끔 짜여진 코드이다.
person_1 = Person() # ()는 생성자
print(person_1) # <__main__.Person object at 0x000001FC66B586D0>
person_2 = Person()
print(person_2) # <__main__.Person object at 0x000001FC66B58190>
여기서 self 는 객체 자기 자신을 가리킨다. 따라서, 파라미터를 따로 넣어주실 필요없이 그냥 호출하시면 알아서 self에 자기자신을 넣는다. 그렇게 하면 주석처리 한 것 처럼 자기 자신의 주소값이 출력된다.
class Person:
def __init__(self, param_name):
print("i am created!", self)
self.name = param_name
# param_name이라는 새로운 파라미터를 이용해서 함수 코드를 짠 것
# 이렇게 하면 name을 호출했을 때 param_name으로 받은 인자 값이 출력된다.
person_1 = Person("김남준")
print(person_1) # <__main__.Person object at 0x000001FC66B586D0>
print(person_1.name) # 김남준
person_2 = Person("김석진")
print(person_2) # <__main__.Person object at 0x000001FC66B58190>
print(person_2.name) # 김석진
파라미터 추가
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) # <__main__.Person object at 0x000001FC66B586D0>
print(person_1.name) # 김남준
person_1.talk() # 안녕하세요, 제 이름은 < 김남준 > 입니다.
person_2 = Person("김석진")
print(person_2) # <__main__.Person object at 0x000001FC66B58190>
print(person_2.name) # 김석진
person_2.talk() # 안녕하세요, 제 이름은 < 김석진 > 입니다.
클래스 내부에 메서드 추가
모던 자바 : ver8이후 나온 함수형 패러다임
틀은 객체지향으로 짜고 해당 메소드나 사용 방식을 FP로 짜는 건가?