📍 Array & Linked List
1. array
- 배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없음!
- 배열은 각 원소에 즉시 접근할 수 있다. (= 상수 시간(O(1)) 내에 접근할 수 있음)
- 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 합니다.
(최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가진다)
>> 원소를 삽입, 삭제 할 때는 비효율적, 찾을 때 유용!
2. Linked List
- 리스트는 크기가 정해지지 않은 데이터의 공간
연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있다. - 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색
최악의 경우에는 모든 원소를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다. - 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경
따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있음!
=> 원소를 삽입,삭제 할 때 유용, 찾기는 비교적 어려움!
💡 추가 설명
파이썬의 list 는 array로 구현되어 있고, append를 활용해 동적으로 공간을 할당할 수 있다. = 파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조다!
📍 Class
클래스는 분류, 집합 같은 속성관 기능을 가진 객체를 총칭하는 개념이다.
객체란 ?
세상에 존재하는 유일무이한 사물 ex) 클래스가 사람이면 객체는 유재석, 박명수가 될 수 있음
