자료 구조란

● 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들

● 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨

● 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음

● 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 함으로 자료구조에 대한 이해가 중요함

​

​

※ 자료구조에는 어떤 것들이 있나?

​

​

한 줄로 자료를 관리하기 (선형 자료구조)

​

● 배열 (Array) : 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음

-1 2 3 4 5 중에 3이 빠지게되면 4가 3이 되고 5가 4가 되는식으로 빠진 구멍을 뒤에서 차례대로 메우게된다.

  자료를 등록해두고 서치를 할때 유용

​

● 연결 리스트 (LinkedList) : 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음

  -물리적위치와 상관없이 추가나 삭제가 일어날 경우 자신의 뒤에 어떤 것이 있는지만 지정해두면 되기때문에

   빈번한 추가나 삭제가 일어날 경우에 유용하다

​

​

리스트에 자료 추가하기

​

​

​

​

● 스택 (Stack) : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First Out) 후입선출

​

​

​

​

​

● 큐 (Queue) : 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out) 선입선출

​

​

​

​

​

​

트리 (Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조 (비선형 자료구조)​

​

​

● 이진 트리 (binary tree) : 부모노드에 자식노드가 두 개 이하인 트리

​

​

● 이진 검색 트리 (binary search tree)

ex) 현대자동차의 여러 계열의 계열사로부터 납품받고 발주할때 

    ->여러 방대한 데이터를 종합해 검색을 할때 이진트리구조를 사용

​

​

예) [23, 10, 28, 15, 7, 22, 56] 순으로 자료를 넣을때

23- 1댑스

10 48 - 2댑스

7 15 56 - 3댑스

22 -4댑스

​