cs 공부 자료구조

Array(List)의 특징, 장점, 단점

특징: 순차적으로 데이터 저장, 0부터 시작하는 index가 존재

장점: index를 사용해 특정 요소를 찾고 조작이 가능

단점: 삽입 삭제 시 시간이 걸림

차이: array는 크기 고정, arraylist는 크기 가변적이고 데이터 수정 시 메모리 재할당하기 때문에 array보다 느림

ex) 주식 차트 처럼 순차적인 정보를 저장해야 하는 경우에 매우 유용

 

LinkedList의 장점, 단점

특징: 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억

장점: array 수정할 때 비용이 든다는 점을 보완하여 삽입, 삭제가 빠름

단점: index가 없어서 원하는 위치에 한 번에 접근할 수 없음

 

Stack, Queue, Tree, Heap

Stack: 후입선출

-> 자바의 Stack 메모리 영역은 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리 할당되고 종료되면 메모리가 해제

 

Queue: 선입선출

-> OS의 스케쥴러에서 사용, 자원의 할당과 회수하기에 적합

Priority Queue: 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조, 일반적으로 완전 이진트리 형태의 힙을 이용해 구현

 

Tree: 비선형 자료구조, 계층적 관계를 표현하기에 적합

Heap: 최대/최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조, 완전이진트리

 

해시 테이블의 특징, 시간 복잡도

특징: (key, value)로 데이터를 저장하는 자료구조 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 데이터를 빠르게 검색할 수 있음

시간 복잡도: 각 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회하지만 index값이 충돌이 발생한 경우 Chanining에 연결된 리스트들까지 검색해야 하므로 O(N)까지 증가할 수 있음 

 

 

Tree에 대해서는 다음에 모아서 작성해보겠슴둥