Data Structure
- 현실세계의 데이터를 어떻게 프로그래밍적으로 표현할 수 있는지
- 거대한 데이터를 효과적으로 관리하는 것
ex) tree, set, graph
Array, 배열
여러 데이터를 하나의 이름으로 그룹핑하여 관리하기위한 데이터스트럭쳐
value, index, element
list
리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐
파이썬과 같은 스크립트 언어에서는 배열과 리스트를 융합하여 하나의 리스트 제공
반면 자바는 array list, linked list 두가지를 명확히 구분하여 사용자가 선택할 수 있게 함
array list는 인덱스를 이용해 데이터를 가져오는 작업에,
linked list는 삽입/삭제 작업에 효과적이다.
Array List
-
인덱싱
시간복잡도 : O(1)
왜냐하면 list는 논리적 저장순서와 물리적 저장순서가 같다. -
삽입, 삭제
시간복잡도 : O(N)
왜냐하면 리스트는 순서대로 저장되어있기때문에 하나의 원소를 삽입/삭제할 시에 원래의 배열이 깨지게 되고, 빈공간을 마련하기위해 혹은 빈공간을 채우기위해 원소를 shift해야하기 때문이다.
Linked List
한 요소마다 다음 요소를 가리켜서 정보의 위치를 나타내며 저장한다.
Array List vs Linked List
둘의 저장방식을 빌딩에 위치하는 회사의 비유로 생각할 수 있다.
array list는 리스트의 모든 요소가 모두 연결되어 저장되어야한다. 따라서 직원수가늘어나면 더 넓은 공간을 가지는 다른 건물로 옮겨서 모든 직원이 같은 층수에 위치해야한다.
linked list는 리스트의 모든 요소가 한 층에 있을 필요가 없다. 따라서 직원이 늘어난다해도 모든 직원이 다른 건물로 옮길 필요가 없다.
하지만 특정 인덱스의 직원을 찾기위해선 첫번째 직원한테 다음 직원의 위치를 물어보며 여러번 물어 물어 찾아가야 한다.
그렇기에
array list는 인덱스를 이용해 데이터를 가져오는 작업에,
linked list는 삽입/삭제 작업에 효과적이다.
