자료구조란?
- 자료구조 란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법
자료구조 분류
- Primitive Data Structure(단순구조): 프로그래밍에서 사용되는 기본 데이터 타입(Sring,float 등)
- Non-Primtive Data Sturcture(비단순 구조): 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조.
- Linear Data Structure(선형구조): 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
- Non-Linear Data Structure(비선형구조): 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
Array 자료구조
- 순차적(ordered)으로 데이터를 저장
- 주로 서로 연결된 데이터들을 순차적 으로 저장할때 사용
- 삽입(insertion) 순서대로 저장(즉, 새로 삽입되는 요소는 array의 새로운 꼬리가 된다)
- 이미 생성된 리스트도 수정 가능(mutable).
- 동일한 값도 여러번 삽입 가능
Array 내부구조
- 실제 메모리 상에서 순차적으로 저장
- 순차적으로 번호를 지정(index 개념)
Array 단점
- Removing Elements
항상 메모리가 순차적으로 이어져있어야 하기 때문에, 요소를 삭제하면 삭제된 요소로 부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동, 배열에서 요소를 삭제하는 것은 다른 자료구조들에 비해 느릴 수 있다는 뜻
맨뒤가 아닌 맨앞, 혹은 중간 값을 삭제하면 칸 이동이 발생하기에 느린 오퍼레이션
- Array Resizing
처음 생성될때 어느정도 메모리를 미리 할당(pre-allocation)
처음에 잡아놓은 메모리 이상으로 요소들이 많아지면 resizing을 필요(메모리 할당 더 필요)
그리고 추가적으로 할당된 메모리 또한 순차적이여야 하기에 resizing은 상대적으로 시간이 오래걸리는 operation
Array의 사용처
- 순차열적인 데이터를 저장할때
- 어떠한 특정 요소를 빠르게 읽어야 할때
- 데이터의 사이즈가 급변하게 자주 변하지 않을때
- 요소를 자주 삭제해야 하지 않을때
Stack & Queue
Stack - LIFO(Last In First Out)
- 데이터 저장은 push
- 데이터 리드는 pop(읽어 드림과 동시에 삭제)
- 사용처
프로그램에서 함수 호출 기록을 stack으로 저장
Web browser 내역 혹등 내역인데 최신 내역이 먼저 나와야 하는 경우
Queue - FIFO(First In First Out)
- 사용처
맛집 예약 시스템
OS 프로세스 스케쥴링 시스템 (priority queue 사용)
트리
-
Node : 트리 구조의 교점
Node가 데이터를 가지고 있고 또한 자식 노드를 가지고 있습니다. 트리 자료구조는 노드를 기본으로 구성된 -
Root Node : 트리 구조의 가장 위 노드, 즉 시작점이 되는 노드
-
Tree 구조는 데이터의 저장의 의미 보다는 저장된 데이터를 더 효과적으로 탐색
-
이진 트리는 검색을 효율적이며 원하는 값을 찾을 때까지, 현재 node의 값이 원하는 값보다 크면 왼쪽으로, 작으면 오른쪽 으로 움직임
-
일반 list는 검색이 O(N)인데에 비해 이진 트리는 O(log N) 이므로 리스트 보다 검색이 훨씬 효율적
Front End. Dev