Array & Linked List
Array(배열)
-. 배열은 크기가 정해진 데이터의 공간, 정해지면 바꿀 수 없다.
배열은 각 원소에 직시 접근할 수 있다.
-. 원소의 순서는 0부터 시작하고 이것을 인덱스 라고 부른다.
-. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있다는 의미. O(1) 내에 접근할 수 있다.
rooms = ["미연", "민니", "소연", "우기", "슈화"]-. 배열은 만약 원소를 중간에 삽입/삭제를 하려면 모든 원소를 다 옮겨줘야한다. O(N)의 시간 복잡도를 가진다.
-. 원소를 새로 추가하려면 새로운 공간을 할당해야 하므로 비효율적이다.
Linked List(링크드 리스트)
-. Linked List와 List는 혼용하여 사용 가능
-. 크기가 정해지지 않은 데이터의 공간. 연결 고리로 이어주기만 하면 크기가 바뀔 수 있다.
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]-. List는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 하므로, O(N)의 시간 복잡도를 가진다.
-. 위에 예시에서 화물칸을 노드, 연결 고리를 포인터 라고 부른다.
-. 리스트는 원소 중간에 삽입/삭제를 하기 위해 앞,뒤의 포인터만 변경해주면 되기 때문에, O(1)의 시간 복잡도를 갖는다.
요약하자면....
스파르타코딩클럽 2주차 강의자료
클래스
-. 분류, 집합, 같은 속성과 기능을 가진 객체를 총칭하는 개념
-. ex) 클래스가 사람이라면, 객체는 유재석, 박명수
클래스가 동물이라면, 객체는 강아지, 고양이
class Person: # Person 이라는 class를 정의하겠다, 밑에는 class에 대한 내용을 작성
pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미입니다!, 빈 class만 만들어 놓겠다.
person_1 = Person() # <- 여기있는 ()는 constructor, 생성자 라고 한다.
print(person_1) # <__main__.Person object at 0x1090c76d0>
person_2 = Person()
print(person_2) # <__main__.Person object at 0x1034354f0>:
-. person_1이란 변수에 Person()이란 클래스의 객체가 생성되었다.
-. Person object at 0x1090c76d0 -> Person이란 객체에 주소값으로 분류
-. constructor(생성자) : 객체를 생성할 때 쓰는 함수를 의미, 생성자를 설정하기 위해서는 __init 이라는 함수를 만들어야 한다.
-. 클래스 내부의 함수는 메소드 라고 한다.
생성자에 데이터를 저장하기 위해 파라미터를 추가
파라미터 : 매개변수를 뜻함
def 함수이름(매개변수1, 매개변수2):
코드class Person:
def __init__(self, param_name): # <- 객체를 생성하기 위해 __init이라는 함수를 사용, self는 생성자를 생성하거나 내부에 있는 함수를 만들 때 인자에 자기 자신을 넘겨준다.
print("i am created!", self)
self.name = param_name # param_name 이라는 데이터를 생성자에 저장하기 위해 self.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 0x7ff3980467c0>
유재석
<main.Person object at 0x7ff3980467c0>
안녕하세요, 제 이름은 유재석 입니다.
i am created! <main.Person object at 0x7ff3b8108610>
박명수
<main.Person object at 0x7ff3b8108610>
안녕하세요, 제 이름은 박명수 입니다.
링크드 리스트 구현
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]: 링크드 리스트의 자료 구조
노드에는 두 가지 정보가 필요하다.
1. 칸에 있는 데이터, 노드 데이터 (self.data)
2. 다음 칸이 뭔지, 포인터 (self.next)
이 두가지 데이터를 클래스로 묶는다.
class Node: # Node라는 클래스를 만든다
def __init__(self, data): # 여기서의 data는 파라미터
self.data = data # 여기서의 data는 저장되는 변수
self.next = None # [3] -> None
# self.next에 다음 노드를 생성하면 된다
# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]first_node = Node(5) # 현재는 next 가 없이 하나의 노드만 있습니다. [5]
second_node = Node(12) # [12] 를 들고 있는 노드를 만듭니다.
first_node.next = second_node # 그리고, [5]의 next 를 [12]로 지정합니다. [5] -> [12]: .next를 사용하여 포인터로 노드를 연결해준다.
-> 이런식으로 반복하게된다면 너무 번거로움
이 때, 링크드 리스트 라는 클래스를 만든다.
링크드 리스트는 head node만을 들고있다.(기관실만 가지고있다.)
다음 노드를 확인하기 위해선 next를 통해 다음 노드로 접근해야한다.
1) LinkedList는 self.head에 시작하는 노드만들 저장한다.
2) 다음 노드를 보기 위해서는 각 노드의 next를 조회해서 찾아가야 한다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node = Node(3)
print(node): <main.Node object at 0x7fc8501277c0>
마지막 줄에 print(node.data)로 데이터를 뽑아내야 '3'이라는 값이 출력된다.
