자료구조 & 알고리즘

배열과 링크드 리스트의 장단점은?

• 배열
  장점 : 인덱스번호로 데이터의 빠른 접근이 가능한 장점이 있습니다
  단점 : 미리 최대 길이를 지정해야 하기 때문에 최대 길이 이상의 데이터 추가/삭제가 어렵습니다
• 링크드리스트
  장점 : 삽입이 간단하다 값 생성 후 포인터값만 변경해 주면 된다
  단점
  1) 항목 접근이 오래걸린다. 최대 O(n)시간이 소요
  2) 물리적으로 인접한 메모리에 있지 않다
  3) 참조포인터를 위한 메모리 공간이 낭비된다
  참조 : https://bluejake.tistory.com/44

큐의 장단점?

• 장점 : 데이터의 삽입 삭제가 빠르다
  단점 : 큐의 중간에 위치한 데이터로의 접근이 어렵다

스택의 장단점은?

• 장점 : 구조가 단순해서 구현이 쉬우며, 데이터 저장/읽기 속도가 빠릅니다
  단점 : 데이터 최대 개수를 미리 정해야 하며 사용하지 않는 공간의 낭비가 발생할 수 있습니다.
  보통 배열구조로 구현하는 것이 일반적

해시테이블의 장단점은?

• 장점
  데이터 저장/읽기 속도가 빠르다(검색 속도가 빠르다)
  키에 대한 데이터가 있는지 확인이 쉽다
• 단점
  일반적으로 저장공간이 좀더 많이 필요하다(key에 따른 value 저장)
  여러키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요합니다
• 주요 용도
  검색이 많이 필요한경우
  저장, 삭제, 읽기가 빈번한 경우
  중복확인이 쉽기 때문에 캐시 구현시 사용합니다
• 캐시 충돌 해결 알고리즘
  chaining 기법 : 개방해시 기법이라고도 하는데 해시 테이블 저장공간외의 공간을 활용하여 충돌시에 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장합니다
  linear Probing 기법 : Close Hashing 기법 중 하나로 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 입니다. 충돌이 일어나면 해당 해시 주소의 다음 주소부터 맨처음 나오는 빈공간에 저장하는 기법입니다.

이진탐색트리 장단점

• 장점 : 입력시 값에 따라 곧바로 위치가 지정되기 때문에 데이터 검색 속도가 빠르다. 따라서 숫자 값 검색이 잦을 경우에 유리하다
• 단점 : 최악의 경우에 한쪽으로만 이어질 수 있어 탐색속도가 O(n)만큼 소요될 수 있다.